Multiple sequence alignment: Difference between revisions

Revision as of 22:02, 8 September 2020

Revision as of 00:12, 12 September 2020

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 and, 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 = | pages = 387-425 | pmid = | pmc = }}</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===