Multiple sequence alignment: Difference between revisions

Revision as of 00:12, 12 September 2020

Revision as of 02:47, 16 September 2020

Line 3:

A '''multiple sequence alignment''' ('''MSA''') is a [[sequence alignment]] of three or more [[biological sequence]]s, generally [[protein]], [[DNA]], or [[RNA]]. In many cases, the input set of query sequences are assumed to have an [[evolutionary]] relationship by which they share a linkage and are descended from a common ancestor. From the resulting MSA, sequence [[homology (biology)|homology]] can be inferred and [[molecular phylogeny|phylogenetic analysis]] can be conducted to assess the sequences' shared evolutionary origins. Visual depictions of the alignment as in the image at right illustrate [[mutation]] events such as point mutations (single [[amino acid]] or [[nucleotide]] changes) that appear as differing characters in a single alignment column, and insertion or deletion mutations ([[indel]]s or gaps) that appear as hyphens in one or more of the sequences in the alignment. Multiple sequence alignment is often used to assess sequence [[conservation (genetics)|conservation]] of [[protein ___domain]]s, [[tertiary structure|tertiary]] and [[secondary structure|secondary]] structures, and even individual amino acids or nucleotides.

Multiple sequence alignment also refers to the process of aligning such a sequence set. Because three or more sequences of biologically relevant length can be difficult and are almost always time-consuming to align by hand, computational [[algorithm]]s are used to produce and analyze the alignments. MSAs require more sophisticated methodologies than [[sequence alignment|pairwise alignment]] because they are more [[Computational complexity theory|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. On the other hand, heuristic methods generally fail to give guarantees on the solution quality, with heuristic solutions shown to be often far below the optimal solution on benchmark instances. <ref name="thompson2011">{{cite journal | doi = 10.1371/journal.pone.0018093|vauthors= Thompson JD, Linard B, Lecompte O, Poch O | year = 2011 | title = A comprehensive benchmark study of multiple sequence alignment methods: current challenges and future perspectives | url = | journal = PloSPLOS oneONE | volume = 6 | issue = 3| pages = e18093| pmid = 21483869| pmc = 3069049|bibcode= }}</ref><ref name="nuin2006" /><ref name="hosseininasab">{{cite journal | doi = 10.1287/ijoc.2019.0937 |vauthors=Hosseininasab A, van Hoeve WJ | year = 2019 | title = Exact Multiple Sequence Alignment by Synchronized Decision Diagrams | url = https://pubsonline.informs.org/doi/10.1287/ijoc.2019.0937 | journal = INFORMS Journal on Computing | volume = | issue = | pages = | pmid = | pmc = |bibcode= }}</ref>

==Algorithm==

Line 119:

=== Mathematical programming and exact solution algorithms ===

[[Mathematical programming]] and in particular [[Mixed integer programming]] models are another approach to solve MSA problems. The advantage of such optimization models is that they can be used to find the optimal MSA solution more efficiently compared to the traditional DP approach. This is due in part, to the applicability of decomposition techniques for mathematical programs, where the MSA model is decomposed into smaller parts and iteratively solved until the optimal solution is found. Example algorithms used to solve mixed integer programming models of MSA include [[branch and price]] <ref name="althaus2006">{{cite journal | doi = 10.1007/s10107-005-0659-3 |vauthors=Althaus E, Caprara A, Lenhof HP, Reinert K | year = 2006 | title = A branch-and-cut algorithm for multiple sequence alignment | url = https://link.springer.com/article/10.1007/s10107-005-0659-3 | journal = Mathematical Programming | volume = 105 | issue = 2–3| pages = 387-425387–425 | pmid = | pmc = |s2cid=17715172 }}</ref> and [[Benders decomposition]] <ref name="hosseininasab"/>. Although exact approaches are computationally slow compared to heuristic algorithms for MSA, they are guaranteed to reach the optimal solution eventually, even for large-size problems.

===Simulated quantum computing===