Multiple sequence alignment: Difference between revisions

Revision as of 20:46, 7 August 2020

Revision as of 10:02, 30 August 2020

Line 54:

A 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 similar gap penalty is used, but a much simpler substitution matrix, wherein only identical matches and mismatches are considered, is typical. The scores in the substitution matrix may be either all positive or a mix of positive and negative in the case of a global alignment, but must be both positive and negative, in the case of a local alignment.<ref>{{cite web | title=Help with matrices used in sequence comparison tools | publisher=European Bioinformatics Institute | url=http://www.ebi.ac.uk/help/matrix.html | accessdate=March 3, 2010 | url-status=dead | archiveurl=https://web.archive.org/web/20100311140200/http://www.ebi.ac.uk/help/matrix.html | archivedate=March 11, 2010 }}</ref>

For ''n'' individual sequences, the naive method requires constructing the ''n''-dimensional equivalent of the matrix formed in standard pairwise [[sequence alignment]]. The search space thus increases exponentially with increasing ''n'' and is also strongly dependent on sequence length. Expressed with the [[big O notation]] commonly used to measure [[Computational complexity theory|computational complexity]], a [[Naïve algorithm|naïve]] MSA takes ''O(Length^Nseqs)'' time to produce. To find the global optimum for ''n'' sequences this way has been shown to be an [[NP complete|NP-complete]] problem.<ref name="wang">{{cite journal | doi = 10.1089/cmb.1994.1.337 |vauthors=Wang L, Jiang T | year = 1994 | title = On the complexity of multiple sequence alignment | url = | journal = J Comput Biol | volume = 1 | issue = 4| pages = 337–348 | pmid = 8790475 |citeseerx=10.1.1.408.894 }}</ref><ref name="just">{{cite journal | doi = 10.1089/106652701753307511 | author = Just W | year = 2001 | title = Computational complexity of multiple sequence alignment with SP-score | url = | journal = J Comput Biol | volume = 8 | issue = 6| pages = 615–23 | pmid = 11747615 | citeseerx = 10.1.1.31.6382 }}</ref><ref name=elias>{{cite journal | journal=J Comput Biol | volume=13 | pages=1323–1339 | year=2006 | author=Elias, Isaac | title=Settling the intractability of multiple alignment | pmid=17037961 | doi =10.1089/cmb.2006.13.1323 | issue=7 | citeseerx=10.1.1.6.256 }}</ref> In 1989, based on Carrillo-Lipman Algorithm,<ref name="carrillo">{{cite journal |vauthors=Carrillo H, Lipman DJ | year = 1988 | title = The Multiple Sequence Alignment Problem in Biology | url = https://zenodo.org/record/1236134| journal = SIAM Journal on Applied Mathematics | volume = 48 | issue = 5| pages = 1073–1082 | doi=10.1137/0148063}}</ref> Altschul introduced a practical method that uses pairwise alignments to constrain the n-dimensional search space.<ref name="altschul">{{cite journal | doi = 10.1073/pnas.86.12.4412 |vauthors=Lipman DJ, Altschul SF, Kececioglu JD | year = 1989 | title = A tool for multiple sequence alignment | url = | journal = Proc Natl Acad Sci U S A | volume = 86 | issue = 12| pages = 4412–4415 | pmid = 2734293 | pmc = 287279 |bibcode=1989PNAS...86.4412L }}</ref> In this approach pairwise dynamic programming alignments are performed on each pair of sequences in the query set, and only the space near the n-dimensional intersection of these alignments is searched for the n-way alignment. The MSA program optimizes the sum of all of the pairs of characters at each position in the alignment (the so-called ''sum of pair'' score) and has been implemented in a software program for constructing multiple sequence alignments.<ref>{{cite web | title=Genetic analysis software | publisher=National Center for Biotechnology Information | url=https://www.ncbi.nlm.nih.gov/CBBresearch/Schaffer/msa.html | accessdate=March 3, 2010}}</ref>

==Alignment methods==

Line 61:

===Progressive alignment construction===

The most widely used approach to multiple sequence alignments uses a heuristic search known as progressive technique (also known as the hierarchical or tree method) developed by Da-Fei Feng and Doolittle in 1987.<ref name="feng1987progressive">{{cite journal |vauthors=Feng DF, Doolittle RF |year=1987 |title=Progressive sequence alignment as a prerequisitetto correct phylogenetic trees |journal=J Mol Evol |volume=25 |issue=4 |pages=351–360 |pmid=3118049|doi=10.1007/BF02603120 |bibcode=1987JMolE..25..351F |s2cid=6345432 }}</ref> Progressive alignment builds up a final MSA by combining pairwise alignments beginning with the most similar pair and progressing to the most distantly related. All progressive alignment methods require two stages: a first stage in which the relationships between the sequences are represented as a [[phylogenetic tree|tree]], called a ''guide tree'', and a second step in which the MSA is built by adding the sequences sequentially to the growing MSA according to the guide tree. The initial ''guide tree'' is determined by an efficient [[Cluster analysis|clustering]] method such as [[neighbor-joining]] or [[UPGMA]], and may use distances based on the number of identical two-letter sub-sequences (as in [[FASTA]] rather than a dynamic programming alignment).<ref name="mount"/>

Progressive alignments are not guaranteed to be globally optimal. The primary problem is that when errors are made at any stage in growing the MSA, these errors are then propagated through to the final result. Performance is also particularly bad when all of the sequences in the set are rather distantly related. 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. This corrects for non-random selection of the sequences given to the alignment program.<ref name="mount"/>

Line 95:

===Phylogeny-aware methods===

[[File:Non-homologous exon alignment.jpg|thumb|450px|Non-homologous exon alignment by an iterative method (a), and by a phylogeny-aware method (b)]]

Most multiple sequence alignment methods try to minimize the number of [[Indel|insertions/deletions]] (gaps) and, as a consequence, produce compact alignments. This causes several problems if the sequences to be aligned contain non-[[Homology (biology)#Sequence homology|homologous]] regions, if gaps are informative in a [[phylogeny]] analysis. These problems are common in newly produced sequences that are poorly annotated and may contain [[Frameshift|frame-shifts]], wrong [[Protein ___domain|domains]] or non-homologous [[RNA splicing|spliced]] [[exons]]. The first such method was developed in 2005 by Löytynoja and Goldman.<ref name="Loytynoja-2005">{{Cite journal | last1 = Loytynoja | first1 = A. | title = An algorithm for progressive multiple alignment of sequences with insertions | doi = 10.1073/pnas.0409137102 | journal = Proceedings of the National Academy of Sciences | volume = 102 | issue = 30 | pages = 10557–10562 | year = 2005 | pmid = 16000407| pmc = 1180752| bibcode = 2005PNAS..10210557L }}</ref> The same authors released a software package called ''PRANK'' in 2008.<ref name="Loytynoja-2008">{{cite journal | vauthors = Löytynoja A, Goldman N | title = Phylogeny-aware gap placement prevents errors in sequence alignment and evolutionary analysis | journal = Science | volume = 320 | issue = 5883 | pages = 1632–5 | date = June 2008 | pmid = 18566285 | doi = 10.1126/science.1158395 | bibcode = 2008Sci...320.1632L | s2cid = 5211928 }}</ref> PRANK improves alignments when insertions are present. Nevertheless, it runs slowly compared to progressive and/or iterative methods which have been developed for several years.

In 2012, two new phylogeny-aware tools appeared. One is called ''PAGAN'' that was developed by the same team as PRANK.<ref name="Loytynoja-2012">{{cite journal | vauthors = Löytynoja A, Vilella AJ, Goldman N | title = Accurate extension of multiple sequence alignments using a phylogeny-aware graph algorithm | journal = Bioinformatics | volume = 28 | issue = 13 | pages = 1684–91 | date = July 2012 | pmid = 22531217 | pmc = 3381962 | doi = 10.1093/bioinformatics/bts198 }}</ref> The other is ''ProGraphMSA'' developed by Szalkowski.<ref name="Szalkowski-2012">{{cite journal | vauthors = Szalkowski AM | title = Fast and robust multiple sequence alignment with phylogeny-aware gap placement | journal = BMC Bioinformatics | volume = 13 | issue = | pages = 129 | date = June 2012 | pmid = 22694311 | pmc = 3495709 | doi = 10.1186/1471-2105-13-129 }}</ref> Both software packages were developed independently but share common features, notably the use of [[Directed acyclic graph#Partial orders and topological ordering|graph algorithms]] to improve the recognition of non-homologous regions, and an improvement in code making these software faster than PRANK.

Line 123:

The necessary use of heuristics for multiple alignment means that for an arbitrary set of proteins, there is always a good chance that an alignment will contain errors. For example, an evaluation of several leading alignment programs using the [[List of sequence alignment software#Benchmarking|BAliBase benchmark]] found that at least 24% of all pairs of aligned amino acids were incorrectly aligned.<ref name="nuin2006">{{cite journal |vauthors=Nuin PA, Wang Z, Tillier ER |year=2006 |title=The accuracy of several multiple sequence alignment programs for proteins |journal=BMC Bioinformatics |doi=10.1186/1471-2105-7-471 |pmid=17062146 |volume=7 |pmc=1633746 |pages=471}}</ref> These errors can arise because of unique insertions into one or more regions of sequences, or through some more complex evolutionary process leading to proteins that do not align easily by sequence alone. As the number of sequence and their divergence increases many more errors will be made simply because of the heuristic nature of MSA algorithms. [[List of alignment visualization software|Multiple sequence alignment viewers]] enable alignments to be visually reviewed, often by inspecting the quality of alignment for annotated functional sites on two or more sequences. Many also enable the alignment to be edited to correct these (usually minor) errors, in order to obtain an optimal 'curated' alignment suitable for use in phylogenetic analysis or comparative modeling.<ref>{{cite web | title=Manual editing and adjustment of MSAs | publisher=European Molecular Biology Laboratory | year=2007 | url=http://www.embl.de/~seqanal/MSAcambridgeGenetics2007/MSAmanualAdjustments/MSAmanualAdjustments.html | accessdate=March 7, 2010 | archive-url=https://web.archive.org/web/20150924000135/http://www.embl.de/~seqanal/MSAcambridgeGenetics2007/MSAmanualAdjustments/MSAmanualAdjustments.html | archive-date=September 24, 2015 | url-status=dead }}</ref>

However, as the number of sequences increases and especially in genome-wide studies that involve many MSAs it is impossible to manually curate all alignments. Furthermore, manual curation is subjective. And finally, even the best expert cannot confidently align the more ambiguous cases of highly diverged sequences. In such cases it is common practice to use automatic procedures to exclude unreliably aligned regions from the MSA. For the purpose of phylogeny reconstruction (see below) the Gblocks program is widely used to remove alignment blocks suspect of low quality, according to various cutoffs on the number of gapped sequences in alignment columns.<ref name="castresana2000">{{cite journal | vauthors = Castresana J | title = Selection of conserved blocks from multiple alignments for their use in phylogenetic analysis | journal = Mol. Biol. Evol. | volume = 17 | issue = 4 | pages = 540–52 | date = April 2000 | pmid = 10742046 | doi = 10.1093/oxfordjournals.molbev.a026334 | doi-access = free }}</ref> However, these criteria may excessively filter out regions with insertion/deletion events that may still be aligned reliably, and these regions might be desirable for other purposes such as detection of positive selection. A few alignment algorithms output site-specific scores that allow the selection of high-confidence regions. Such a service was first offered by the SOAP program,<ref name="loytynojaMilinkovitch2001">{{cite journal | vauthors = Löytynoja A, Milinkovitch MC | title = SOAP, cleaning multiple alignments from unstable blocks | journal = Bioinformatics | volume = 17 | issue = 6 | pages = 573–4 | date = June 2001 | pmid = 11395440 | doi = 10.1093/bioinformatics/17.6.573 | doi-access = free }}</ref> which tests the robustness of each column to perturbation in the parameters of the popular alignment program CLUSTALW. The T-Coffee program<ref name=poirotOTooleNotredame2003>{{cite journal | vauthors = Poirot O, O'Toole E, Notredame C | title = Tcoffee@igs: A web server for computing, evaluating and combining multiple sequence alignments | journal = Nucleic Acids Res. | volume = 31 | issue = 13 | pages = 3503–6 | date = July 2003 | pmid = 12824354 | pmc = 168929 | doi = 10.1093/nar/gkg522 }}</ref> uses a library of alignments in the construction of the final MSA, and its output MSA is colored according to confidence scores that reflect the agreement between different alignments in the library regarding each aligned residue. Its extension, [http://tcoffee.crg.cat/tcs TCS] : ('''T'''ransitive '''C'''onsistency '''S'''core), uses T-Coffee libraries of pairwise alignments to evaluate any third party MSA. Pairwise projections can be produced using fast or slow methods, thus allowing a trade-off between speed and accuracy.<ref name=TCS2014MBE>{{cite journal|last=Chang|first=JM|author2=Di Tommaso, P | author3 = Notredame, C|title=TCS: A New Multiple Sequence Alignment Reliability Measure to Estimate Alignment Accuracy and Improve Phylogenetic Tree Reconstruction.|journal=Molecular Biology and Evolution|date=Jun 2014|volume=31|issue=6|pages=1625–37|doi=10.1093/molbev/msu117|pmid=24694831|url=http://mbe.oxfordjournals.org/content/31/6/1625|doi-access=free}}</ref><ref name=TCS_2015_NAR>{{cite journal | vauthors = Chang JM, Di Tommaso P, Lefort V, Gascuel O, Notredame C | title = TCS: a web server for multiple sequence alignment evaluation and phylogenetic reconstruction | journal = Nucleic Acids Res. | volume = 43 | issue = W1 | pages = W3–6 | date = July 2015 | pmid = 25855806 | pmc = 4489230 | doi = 10.1093/nar/gkv310 }}</ref> Another alignment program that can output an MSA with confidence scores is FSA,<ref name=bradley2009>{{cite journal | vauthors = Bradley RK, Roberts A, Smoot M, Juvekar S, Do J, Dewey C, Holmes I, Pachter L | title = Fast statistical alignment | journal = PLoSPLOS Comput. Biol. | volume = 5 | issue = 5 | pages = e1000392 | date = May 2009 | pmid = 19478997 | pmc = 2684580 | doi = 10.1371/journal.pcbi.1000392 | bibcode = 2009PLSCB...5E0392B }}</ref> which uses a statistical model that allows calculation of the uncertainty in the alignment. The HoT (Heads-Or-Tails) score can be used as a measure of site-specific alignment uncertainty due to the existence of multiple co-optimal solutions.<ref name=landanGraur2008>{{cite book | vauthors = Landan G, Graur D | title = Biocomputing 2008 | chapter = Local reliability measures from sets of co-optimal multiple sequence alignments | journal = Pac Symp Biocomput | volume = | issue = | pages = 15–24 | date = 2008 | pmid = 18229673 | doi = 10.1142/9789812776136_0003 |isbn = 978-981-277-608-2 }}</ref> The GUIDANCE program<ref name="penn2010">{{cite journal | vauthors = Penn O, Privman E, Landan G, Graur D, Pupko T | title = An alignment confidence score capturing robustness to guide tree uncertainty | journal = Mol. Biol. Evol. | volume = 27 | issue = 8 | pages = 1759–67 | date = August 2010 | pmid = 20207713 | pmc = 2908709 | doi = 10.1093/molbev/msq066 }}</ref> calculates a similar site-specific confidence measure based on the robustness of the alignment to uncertainty in the guide tree that is used in progressive alignment programs. An alternative, more statistically justified approach to assess alignment uncertainty is the use of probabilistic evolutionary models for joint estimation of phylogeny and alignment. A Bayesian approach allows calculation of posterior probabilities of estimated phylogeny and alignment, which is a measure of the confidence in these estimates. In this case, a posterior probability can be calculated for each site in the alignment. Such an approach was implemented in the program BAli-Phy.<ref name="redelingsSuchard2005">{{cite journal | vauthors = Redelings BD, Suchard MA | title = Joint Bayesian estimation of alignment and phylogeny | journal = Syst. Biol. | volume = 54 | issue = 3 | pages = 401–18 | date = June 2005 | pmid = 16012107 | doi = 10.1080/10635150590947041 | doi-access = free }}</ref>

There are free programs available for visualization of multiple sequence alignments, for example [[Jalview]] and [[UGENE]].