Content deleted Content added
Line 116:
The technique of [[simulated annealing]], by which an existing MSA produced by another method is refined by a series of rearrangements designed to find better 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">{{cite journal |vauthors=Kim J, Pramanik S, Chung MJ | year = 1994 | title = Multiple sequence alignment using simulated annealing | url = | journal = Comput Appl Biosci | volume = 10 | issue = 4| pages = 419–26 | pmid = 7804875 | doi=10.1093/bioinformatics/10.4.419}}</ref>
=== Mathematical programming ===
[[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">{{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>. Although such exact approaches are slow compared to heuristic algorithms for MSA, they are guaranteed to reach the optimal solution eventually, even for large-size problems.
==Simulated quantum computing==
| |||