Multiple sequence alignment: Difference between revisions

Revision as of 04:19, 9 July 2006

Revision as of 03:44, 18 July 2006

Line 1:

<!-- please don't refconvert this article - I'll do it once I've finished the text ~~~~ -->

[[Image:RPLP0_90_ClustalW_aln.gif|right|thumb|300px|First 90 positions of a protein multiple sequence alignment of instances of the acidic ribosomal protein P0 (L10E) from several organisms. Generated with [[ClustalW]].]]

Line 10 ⟶ 8:

The most direct method for producing an MSA uses the [[dynamic programming]] technique to identify the globally optimal alignment solution. For proteins, this method usually involves two sets of parameters: a [[gap penalty]] and a [[substitution matrix]] assigning scores or probabilities to the alignment of each possible pair of amino acids based on the similarity of the amino acids' chemical properties and the evolutionary probability of the mutation. For nucleotide sequences a substitution matrix can be used, but since there are only four possible standard characters per sequence and the individual nucleotides do not typically differ much in substitution probability, the parameters for DNA and RNA sequences usually consist of a gap penalty, a positive score for character matches, and a negative score for mismatches.

For ''n'' individual sequences, the method requires constructing the ''n''-dimensional equivalent of the matrix formed in standard pairwise dynamic programming. The search space thus increases exponentially with increasing ''n'' and is also strongly dependent on sequence length. To find the global optimum for ''n'' sequences this way has been shown to be an [[NP-complete]] problem{{<ref| name="wang">Wang}}{{ L, Jiang T. (1994) On the complexity of multiple sequence alignment. ''J Comput Biol'' 1:337-348.</ref|><ref name="just">Just}} W. (2001). Computational complexity of multiple sequence alignment with SP-score. ''J Comput Biol'' 8(6):615-23.</ref>. Methods to reduce the search space by first performing pairwise dynamic programming on each pair of sequences in the query set and searching only the solution space near these results (effectively finding the intersection between local paths immediately surrounding each pairwise optimum solution) render the dynamic programming technique more efficient. The so-called "sum of pairs" method has been implemented in the software package [http://www.ncbi.nlm.nih.gov/CBBresearch/Schaffer/msa.html MSA], but it is still impractical for many MSA applications that require the simultaneous alignment of dozens or even a few hundred sequences. Dynamic programming methods are now used only when an extremely high-quality alignment of a small number of sequences is needed, and as a [[benchmark]]ing standard in evaluating new or refined heuristic techniques.

==Progressive alignment construction==

Line 17 ⟶ 15:

One major limitation of progressive methods is their heavy dependence on the initial assignment of relatedness and on the quality of the initial alignment. The methods are thus sensitive as well to the distribution of sequences in the query set; performance improves when relatedness among query sequences is a relatively smooth gradient rather than distantly separated clusters. Performance also degrades significantly when all of the sequences in the set are rather distantly related, because inaccuracies in the initial alignment are then more likely. Most modern progressive methods modify their scoring function with a secondary weighting function that assigns scaling factors to individual members of the query set in a nonlinear fashion based on their phylogenetic distance from their nearest neighbors. Judicious choice of weighting can aid in evaluating relatedness and mitigate the effects of relatively poor initial alignments early in the progression.

Progressive alignment methods are efficient enough to implement on a large scale for many sequences and are often run on publicly accessible web servers so users need not locally install the applications of interest. A very popular progressive alignment method is the [[Clustal]] family{{<ref| name="higgins">Higgins}} DG, Sharp PM. (1988). CLUSTAL: a package for performing multiple sequence alignment on a microcomputer. ''Gene'' 73(1):237-44.</ref>, especially the weighted variant ClustalW{{<ref name="thomson">Thompson JD, Higgins DG, Gibson TJ. (1994). CLUSTAL W: improving the sensitivity of progressive multiple sequence alignment through sequence weighting, positions-specific gap penalties and weight matrix choice. ''Nucleic Acids Res'' 22:4673-4680.</ref|Thomson}}> to which access is provided by a large number of web portals including [http://align.genome.jp/ GenomeNet], [http://www.ebi.ac.uk/clustalw/ EBI], and [http://www.ch.embnet.org/software/ClustalW.html EMBNet]. Different portals or implementations can vary in user interface and make different parameters accessible to the user. Clustal is used extensively for phylogenetic tree construction and as input for [[protein structure prediction]] by homology modeling.

Another common progressive alignment method called [[T-Coffee]]{{<ref| name="notredame">Notredame}} C, Higgins DG, Heringa J. (2000). T-Coffee: A novel method for fast and accurate multiple sequence alignment. ''J Mol Biol'' 302(1):205-17.</ref> is slower than Clustal and its derivatives but generally produces more accurate alignments for distantly related sequence sets. T-coffee uses the output from Clustal as well as another local alignment program LALIGN, which finds multiple reqions of local alignment between two sequences. The resulting alignment and phylogenetic tree are used as a guide to produce new and more accurate weighting factors.

Because progressive methods are heuristics that are not guaranteed to converge to a global optimum, alignment quality can be difficult to evaluate and their true biological significance can be obscure. A very recent semi-progressive method that improves alignment quality and does not use a lossy heuristic while still running in [[polynomial time]]{{<ref| name="sze">Sze}} SH, Lu Y, Yang Q. (2006). A polynomial time solvable formulation of multiple sequence alignment. ''J Comput Biol'' 13(2):309-19.</ref> has been implemented in the program [http://faculty.cs.tamu.edu/shsze/psalign PSAlign].

==Iterative methods==

A set of methods to produce MSAs while reducing the errors inherent in progressive methods are classified as "iterative" because they work similarly to progressive methods but repeatedly realign the initial sequences as well as adding new sequences to the growing MSA. One reason progressive methods are so strongly dependent on a high-quality initial alignment is the fact that these alignments are always incorporated into the final result - that is, once a sequence has been aligned into the MSA, its alignment is not considered further. This approximation improves efficiency at the cost of accuracy. By contrast, iterative methods can return to previously calculated pairwise alignments or sub-MSAs incorporating subsets of the query sequence as a means of optimizing a general [[objective function]] such as finding a high-quality alignment score.

A variety of subtly different iteration methods have been implemented and made available in software packages; reviews and comparisons have been useful but generally refrain from choosing a "best" technique{{<ref| name="hirosawa">Hirosawa}} M, Totoki Y, Hoshida M, Ishikawa M. (1995). Comprehensive study on iterative algorithms of multiple sequence alignment. ''Comput Appl Biosci'' 11:13-18.</ref>. The software package [http://prrn.hgc.jp/ PRRN/PRRP] uses a [[hill-climbing algorithm]] to optimize its MSA alignment score{{<ref| name="gotoh">Gotoh}} O. (1996). Significant improvement in accuracy of multiple protein sequence alignments by iterative refinement as assessed by reference to structural alignments. ''J Mol Biol'' 264(4):823-38.</ref> and iteratively corrects both alignment weights and locally divergent or "gappy" regions of the growing MSA{{<ref| name="mount">Mount}} DM. (2004). Bioinformatics: Sequence and Genome Analysis 2nd ed. Cold Spring Harbor Laboratory Press: Cold Spring Harbor, NY.</ref>. PRRP performs best when refining an alignment previously constructed by a faster method.

Another iterative program, DIALIGN, takes an unusual approach of focusing narrowly on local alignments between sub-segments or [[sequence motif]]s without introducing a gap penalty{{<ref| name="brudno">Brudno}} M, Chapman M, Göttgens B, Batzoglou S, Morgenstern B. (2003) Fast and sensitive multiple alignment of large genomic sequences. ''BMC Bioinformatics'' 4:66.</ref>. The alignment of individual motifs is then achieved with a matrix representation similar to a dot-matrix plot in a pairwise alignment. DIALIGN is also available as a web portal at [http://dialign.gobics.de/chaos-dialign-submission CHAOS/DIALIGN].

A third popular iteration-based method called MUSCLE (multiple sequence alignment by log-expectation) improves on progressive methods with a more accurate distance measure to assess the relatedness of two sequences{{<ref| name="edgar">Edgar}} RC. (2004), MUSCLE: multiple sequence alignment with high accuracy and high throughput. ''Nucleic Acids Research'' 32(5), 1792-97.</ref>. The distance measure is updated between iteration stages (although, in its original form, MUSCLE contained only 2-3 iterations depending on whether refinement was enabled). A web portal and download site is available at [http://www.drive5.com/muscle/ MUSCLE].

==Hidden Markov models==

[[Hidden Markov model]]s are probabilistic models that can assign likelihoods to all possible combinations of gaps, matches, and mismatches to determine the most likely MSA or set of possible MSAs. HMMs can produce a single highest-scoring output but can also generate a family of possible alignments that can then be evaluated for biological significance. Because HMMs are probablistics, they do not produce the same solution every time they are run on the same dataset; thus they cannot be guaranteed to converge to an optimal alignment. HMMs can produce both global and local alignments. Although HMM-based methods have been developed relatively recently, they offer significant improvements in computational speed, especially for sequences that contain overlapping regions {{<ref|Mount}} name="mount" />.

Typical HMM-based methods work by representing an MSA as a form of [[directed acyclic graph]] known as a partial-order graph, which consists of a series of nodes representing possible entries in the columns of an MSA. In this representation a column that is absolutely conserved (that is, that all the sequences in the MSA share a particular character at a particular position) is coded as a single node with as many outgoing connections as there are possible characters in the next column of the alignment. In the terms of a typical hidden Markov model, the observed states are the individual alignment columns and the "hidden" states represent the presumed ancestral sequence from which the sequences in the query set are hypothesized to have descended. A efficient search variant of the dynamic programming method, known as the [[Viterbi algorithm]], is generally used to successively align the growing MSA to the next sequence in the query set to produce a new MSA{{<ref| name="hughey">Hughey}} R, Krogh A. (1996). Hidden Markov models for sequence analysis: extension and analysis of the basic method. ''CABIOS'' 12(2):95-107.</ref>. This is distinct from progressive alignment methods because the alignment of prior sequences is updated at each new sequence addition. However, like progressive methods, this technique can be influenced by the order in which the sequences in the query set are integrated into the alignment, especially when the sequences are distantly related{{<ref|Mount}} name="mount" />.

Several software programs are available in which variants of HMM-based methods have been implemented and which are noted for their scalability and efficiency, although properly using an HMM method is more complex than using more common progressive methods. The simplest is [http://sourceforge.net/project/showfiles.php?group_id=168080 POA] (Partial-Order Alignment, temporarily available for download via [[SourceForge]]); a similar but more generalized method is implemented in the package [http://www.cse.ucsc.edu/compbio/sam.html SAM] (Sequence Alignment and Modeling System), which is also available as a [http://www.cse.ucsc.edu/compbio/HMM-apps/T02-query.html web portal]. SAM has been used as a source of alignments for [[protein structure prediction]] to participate in the [[CASP]] structure prediction experiment and to develop a database of predicted proteins in the yeast species [[S. cerevisiae]]. A database-search technique based on HMM methods is available in the program [http://hmmer.wustl.edu/ HMMer].

==Genetic algorithms and simulated annealing==

Standard optimization techniques in computer science - both of which were inspired by, but do not directly reproduce, physical processes - have also been used in an attempt to more efficiently produce quality MSAs. On such technique, [[genetic algorithm]]s, have been used for MSA production in an attempt to broadly simulate the hypothesized evolutionary process that gave rise to the divergence in the query set. The method works by breaking a series of possible MSAs into fragments and repeatedly rearranging those fragments with the introduction of gaps at varying positions. A general [[objective function]] is optimized during the simulation, most generally the "sum of pairs" maximization function introduced in dynamic programming-based MSA methods. A technique for protein sequences has been implemented in the software program SAGA (Sequence Alignment by Genetic Algorithm){{<ref|Notredame2}} name="notredame2">Notredame C, Higgins DG. (1996). SAGA: sequence alignment by genetic algorithm. ''Nucleic Acids Res'' 24(8):1515-24.</ref> and its equivalent in RNA is run in RAGA{{<ref name="notredame3">Notredame C, O'Brien EA, Higgins DG. (1997). RAGA: RNA sequence alignment by genetic algorithm. ''Nucleic Acids Res'' 25(22):4570-80.</ref|Notredame3}}>.

The technique of [[simulated annealing]], by which an existing MSA produced by another method is refined by a series of rearrangements designed to find more optimal regions of alignment space than the one the input alignment already occupies. Like the genetic algorithm method, simulated annealing maximizes an objective function like the sum-of-pairs function. Simulated annealing uses a metaphorical "temperature factor" that determines the rate at which rearrangements proceed and the likelihood of each rearrangement; typical usage alternates periods of high rearrangement rates with relatively low likelihood (to explore more distant regions of alignment space) with periods of lower rates and higher likelihoods to more thoroughly explore local minima near the newly "colonized" regions. This approach has been implemented in the program MSASA (Multiple Sequence Alignment by Simulated Annealing){{<ref| name="kim">Kim}} J, Pramanik S, Chung MJ. (1994). Multiple sequence alignment using simulated annealing. ''Comput Appl Biosci'' 10(4):419-26.</ref>.

==Motif finding==

Motif finding, also known as profile analysis, is a method of locating [[sequence motif]]s in global MSAs that is both a means of producing a better MSA and a means of producing a scoring matrix for use in searching other sequences for similar motifs. A variety of methods for isolating the motifs have been developed, but all are based on identifying short highly conserved patterns within the larger alignment and constructing a matrix similar to a substitution matrix that reflects the amino acid or nucleotide composition of each position in the putative motif. The alignment can then be refined using these matrices. In standard profile analysis, the matrix includes entries for each possible character as well as entries for gaps{{<ref|Mount}} name="mount" />. Alternatively, statistical pattern-finding algorithms can identify motifs as a precursor to an MSA rather than as a derivation. In many cases when the query set contains only a small number of sequences or contains only highly related sequences, [[pseudocount]]s are added to normalize the distribution reflected in the scoring matrix. In particular, this corrects zero-probability entries in the matrix to values that are small but nonzero.

Blocks analysis is a method of motif finding that restricts motifs to ungapped regions in the alignment. Blocks can be generated from an MSA or they can be extracted from unaligned sequences using a precalculated set of common motifs previously generated from known gene families{{<ref| name="henikoff">Henikoff}} S, Henikoff JG. (1991). Automated assembly of protein blocks for database searching. ''Nucleic Acids Res'' 19:6565-72.</ref>. Block scoring generally relies on the spacing of high-frequency characters rather than on the calculation of an explicit substitution matrix. A server for locating motifs in unaligned sequences is located at [http://blocks.fhcrc.org/ BLOCKS].

Statistical pattern-matching has been implemented using both the [[expectation-maximization algorithm]] and the [[Gibbs sampler]]. One of the most common motif-finding tools, known as MEME, uses expectation maximization and hidden Markov methods to generate motifs that are then used as search tools by its companion program MAST. Both are available at [http://meme.sdsc.edu/meme/intro.html MEME/MAST].

Line 56 ⟶ 54:

== References ==

<div class="references-small"><references /></div>

#{{note|Wang}} Wang L, Jiang T. (1994) On the complexity of multiple sequence alignment. ''J Comput Biol'' 1:337-348.

#{{note|Just}} Just W. (2001). Computational complexity of multiple sequence alignment with SP-score. ''J Comput Biol'' 8(6):615-23.

#{{note|Higgins}} Higgins DG, Sharp PM. (1988). CLUSTAL: a package for performing multiple sequence alignment on a microcomputer. ''Gene'' 73(1):237-44.

#{{note|Thomson}} Thompson JD, Higgins DG, Gibson TJ. (1994). CLUSTAL W: improving the sensitivity of progressive multiple sequence alignment through sequence weighting, positions-specific gap penalties and weight matrix choice. ''Nucleic Acids Res'' 22:4673-4680.

#{{note|Notredame}} Notredame C, Higgins DG, Heringa J. (2000). T-Coffee: A novel method for fast and accurate multiple sequence alignment. ''J Mol Biol'' 302(1):205-17.

#{{note|Sze}} Sze SH, Lu Y, Yang Q. (2006). A polynomial time solvable formulation of multiple sequence alignment. ''J Comput Biol'' 13(2):309-19.

#{{note|Hirosawa}} Hirosawa M, Totoki Y, Hoshida M, Ishikawa M. (1995). Comprehensive study on iterative algorithms of multiple sequence alignment. ''Comput Appl Biosci'' 11:13-18.

#{{note|Gotoh}} Gotoh O. (1996). Significant improvement in accuracy of multiple protein sequence alignments by iterative refinement as assessed by reference to structural alignments. ''J Mol Biol'' 264(4):823-38.

#{{note|Mount}} Mount DM. (2004). Bioinformatics: Sequence and Genome Analysis 2nd ed. Cold Spring Harbor Laboratory Press: Cold Spring Harbor, NY.

#{{note|Brudno}} Brudno M, Chapman M, Göttgens B, Batzoglou S, Morgenstern B. (2003) Fast and sensitive multiple alignment of large genomic sequences. ''BMC Bioinformatics'' 4:66.

#{{note|Edgar}} Edgar RC. (2004), MUSCLE: multiple sequence alignment with high accuracy and high throughput. ''Nucleic Acids Research'' 32(5), 1792-97.

#{{note|Hughey}} Hughey R, Krogh A. (1996). Hidden Markov models for sequence analysis: extension and analysis of the basic method. ''CABIOS'' 12(2):95-107.

#{{note|Notredame2}} Notredame C, Higgins DG. (1996). SAGA: sequence alignment by genetic algorithm. ''Nucleic Acids Res'' 24(8):1515-24.

#{{note|Notredame3}} Notredame C, O'Brien EA, Higgins DG. (1997). RAGA: RNA sequence alignment by genetic algorithm. ''Nucleic Acids Res'' 25(22):4570-80.

#{{note|Kim}} Kim J, Pramanik S, Chung MJ. (1994). Multiple sequence alignment using simulated annealing. ''Comput Appl Biosci'' 10(4):419-26.

#{{note|Henikoff}} Henikoff S, Henikoff JG. (1991). Automated assembly of protein blocks for database searching. ''Nucleic Acids Res'' 19:6565-72.

=== Survey articles ===

*{{cite book | first = L. | last = Duret | coauthors = S. Abdeddaim | year = 2000 | chapter = Multiple alignment for structural functional or phylogenetic analyses of homologous sequences | editor = D. Higgins and W. Taylor | title = Bioinformatics sequence structure and databanks | ___location = Oxford | publisher = Oxford University Press}}

*{{cite book

| first = L.

*{{cite journal | first = C. | last = Notredame | year = 2002 | title = Recent progresses in multiple sequence alignment: a survey | journal = Pharmacogenomics | volume = 31 | issue = 1 | pages = 131 -- 144 }}

| last = Duret

| coauthors = S. Abdeddaim

| year = 2000

| chapter = Multiple alignment for structural functional or phylogenetic analyses of homologous sequences

| editor = D. Higgins and W. Taylor

| title = Bioinformatics sequence structure and databanks

| ___location = Oxford

| publisher = Oxford University Press

}}

*{{cite journal | first = J. D. | last = Thompson | coauthors = F. Plewniak and O. Poch | year = 1999 | title = A comprehensive comparison of multiple sequence alignment programs | journal = Nucleic Acids Research | volume = 27 | issue = 13 | pages = 12682--2690 }}

*{{cite journal

| first = C.

| last = Notredame

| year = 2002

| title = Recent progresses in multiple sequence alignment: a survey

| journal = Pharmacogenomics

| volume = 31

| issue = 1

| pages = 131 -- 144

}}

*{{cite journal | first = I.M. | last = Wallace | coauthors = Blackshields G and Higgins DG. | year = 2005 | title = Multiple sequence alignments | journal = Curr Opin Struct Biol | volume = 15 | issue = 3 | pages = 261-6.}}

*{{cite journal

| first = J. D.

| last = Thompson

| coauthors = F. Plewniak and O. Poch

| year = 1999

| title = A comprehensive comparison of multiple sequence alignment programs

| journal = Nucleic Acids Research

| volume = 27

| issue = 13

| pages = 12682--2690

}}

[[Category:Bioinformatics]]