Content deleted Content added
Cheater no1 (talk | contribs) →top: Inverted -> normal sentence structure. Fixing the inconsistency that slow alignment by hand leads to the need for algorithms for aligning AND processing. |
Cheater no1 (talk | contribs) →top: Renaming Algorithm -> Problem statement. Deleting duplicating explanations from the intro. |
||
Line 5:
Computational [[algorithm]]s are used to produce and analyse the MSAs due to the difficulty and intractability of manually processing the sequences given their biologically-relevant length. 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 | journal = PLOS ONE | volume = 6 | issue = 3| pages = e18093| pmid = 21483869| pmc = 3069049}}</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 | journal = INFORMS Journal on Computing }}</ref>
==Problem statement==
Given <math>m</math> sequences <math>S_i</math>, <math>i = 1,\cdots,m</math> similar to the form below:
| |||