Multiple sequence alignment

First 90 positions of a protein multiple sequence alignment of instances of the acidic ribosomal protein P0 (L10E) from several organisms. Generated with ClustalX.

Multiple sequence alignment (MSA) is the process or the result of sequence alignment of three or more biological sequences, generally protein, DNA, or RNA. These alignments are used to infer evolutionary relationships via phylogenetic analysis and can highlight homologous features between sequences. Alignments highlight mutation events such as point mutations (single amino acid or nucleotide changes), insertion mutations and deletion mutations, and alignments are used to assess sequence conservation and infer the presence and activity of protein domains, tertiary structures, secondary structures, and individual amino acids or nucleotides.

Multiple sequence alignments require more sophisticated methodologies than pairwise alignments, as they are more computationally complex. Most multiple sequence alignment programs use heuristic methods rather than global optimization because identifying the optimal alignment between more than a few sequences of moderate length is prohibitively computationally expensive. However, heuristic methods generally cannot guarantee high-quality solutions and have been shown to fail to yield near-optimal solutions on benchmark test cases.

Si, S by inserting any amount of gaps needed into each of the S'i, all conform to length S'i to Nuin PA, Wang Z, Tillier ER (2006). "The accuracy of several multiple sequence alignment programs for proteins". BMC Bioinformatics. 7 (1) 471. Bibcode:2006BMCBi...7..471N. doi:10.1186/1471-2105-7-471. PMC 1633746. PMID 17062146.

1 2 3 Wang L, Jiang T (1994). "On the complexity of multiple sequence alignment". J Comput Biol. 1 (4): 337–348. Bibcode:1994JCoB....1..337W. doi:10.1089/cmb.1994.1.337. PMID 8790475.

↑ Carrillo H, Lipman DJ (1988). "The Multiple Sequence Alignment Problem in Biology". SIAM Journal on Applied Mathematics. 48 (5): 1073–1082. doi:10.1137/0148063.

↑ Feng DF, Doolittle RF (1987). "Progressive sequence alignment as a prerequisitet to correct phylogenetic trees". J Mol Evol. 25 (4): 351–360. Bibcode:1987JMolE..25..351F. doi:10.1007/BF02603120. PMID 3118049. S2CID 6345432.

1 2 3 4 5 6 7 8 Mount DM. (2004). Bioinformatics: Sequence and Genome Analysis 2nd ed. Cold Spring Harbor Laboratory Press: Cold Spring Harbor, NY.

↑ "EMBL-EBI-ClustalW2-Multiple Sequence Alignment". CLUSTALW2.

↑ Hirosawa M, Totoki Y, Hoshida M, Ishikawa M (1995). "Comprehensive study on iterative algorithms of multiple sequence alignment". Computer Applications in the Biosciences. 11 (1): 13–18. doi:10.1093/bioinformatics/11.1.13. PMID 7796270.

↑ Edgar RC (2004). "MUSCLE: multiple sequence alignment with high accuracy and high throughput". Nucleic Acids Research. 32 (5): 1792–97. doi:10.1093/nar/gkh340. PMC 390337. PMID 15034147.

↑ Grasso C, Lee C (2004). "Combining partial order alignment and progressive multiple sequence alignment increases alignment speed and scalability to very large alignment problems". Bioinformatics. 20 (10): 1546–56. doi:10.1093/bioinformatics/bth126. PMID 14962922.

↑ Hughey R, Krogh A. SAM: Sequence alignment and modeling software system. Technical Report UCSC-CRL-96-22, University of California, Santa Cruz, CA, September 1996.

↑ Durbin R, Eddy S, Krogh A, Mitchison G. (1998). Biological sequence analysis: probabilistic models of proteins and nucleic acids, Cambridge University Press, 1998.

↑ Loytynoja, A. (2005). "An algorithm for progressive multiple alignment of sequences with insertions". Proceedings of the National Academy of Sciences. 102 (30): 10557–10562. Bibcode:2005PNAS..10210557L. doi:10.1073/pnas.0409137102. PMC 1180752. PMID 16000407.

↑ Szalkowski AM (June 2012). "Fast and robust multiple sequence alignment with phylogeny-aware gap placement". BMC Bioinformatics. 13 129. doi:10.1186/1471-2105-13-129. PMC 3495709. PMID 22694311.

↑ Bailey TL, Gribskov M (1998). "Combining evidence using p-values: application to sequence homology searches". Bioinformatics. 14 (1): 48–54. doi:10.1093/bioinformatics/14.1.48. PMID 9520501.

↑ Althaus E, Caprara A, Lenhof HP, Reinert K (2006). "A branch-and-cut algorithm for multiple sequence alignment". Mathematical Programming. 105 (2–3): 387–425. doi:10.1007/s10107-005-0659-3. S2CID 17715172.

↑ Castresana J (April 2000). "Selection of conserved blocks from multiple alignments for their use in phylogenetic analysis". Molecular Biology and Evolution. 17 (4): 540–52. doi:10.1093/oxfordjournals.molbev.a026334. PMID 10742046.

↑ Bradley RK, Roberts A, Smoot M, Juvekar S, Do J, Dewey C, Holmes I, Pachter L (May 2009). "Fast statistical alignment". PLOS Comput. Biol. 5 (5) e1000392. Bibcode:2009PLSCB...5E0392B. doi:10.1371/journal.pcbi.1000392. PMC 2684580. PMID 19478997.

↑ Redelings BD, Suchard MA (June 2005). "Joint Bayesian estimation of alignment and phylogeny". Syst. Biol. 54 (3): 401–18. doi:10.1080/10635150590947041. PMID 16012107.

1 2 Notredame, C. (2002). "Recent progresses in multiple sequence alignment: a survey". Pharmacogenomics. 3 (1): 131–144. doi:10.1517/14622416.3.1.131. PMID 11966409.

Notredame, C (2007). "Recent Evolutions of Multiple Sequence Alignment Algorithms". PLOS Computational Biology. 3 (8) e123. Bibcode:2007PLSCB...3..123N. doi:10.1371/journal.pcbi.0030123. PMC 1963500. PMID 17784778.

• ExPASy sequence alignment tools Archived 2010-04-13 at the Wayback Machine
• Archived Multiple Alignment Resource Page – from the Virtual School of Natural Sciences
• Tools for Multiple Alignments – from Pôle Bioinformatique Lyonnais
• An entry point to clustal servers and information
• An entry point to the main T-Coffee servers
• An entry point to the main MergeAlign server and information
• European Bioinformatics Institute servers:
  • ClustalW2 – general purpose multiple sequence alignment program for DNA or proteins.
  • Muscle – MUltiple Sequence Comparison by Log-Expectation
  • T-coffee – multiple sequence alignment.
  • MAFFT – Multiple Alignment using Fast Fourier Transform
  • KALIGN – a fast and accurate multiple sequence alignment algorithm.

• Multiple sequence alignment lectures – from the Max Planck Institute for Molecular Genetics
• Lecture Notes and practical exercises on multiple sequence alignments at the European Molecular Biology Laboratory (EMBL)
• Molecular Bioinformatics Lecture Notes
• Molecular Evolution and Bioinformatics Lecture Notes