Content deleted Content added
m →Dynamic programming and computational complexity: not just NP-hard, it's NP-complete |
see also |
||
Line 43:
The technique of [[simulated annealing]], by which an existing MSA produced by another method is refined by a series of rearrangements designed to find more optimal 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|Kim}}.
==See Also==
*[[Sequence alignment software]]
*[[Structural alignment]]
== References ==
Line 60 ⟶ 64:
#{{note|Notredame3}} Notredame C, O'Brien EA, Higgins DG. (1997). RAGA: RNA sequence alignment by genetic algorithm. ''Nucleic Acids Res'' 25(22):4570-80.
#{{note|Kim}} Kim J, Pramanik S, Chung MJ. (1994). Multiple sequence alignment using simulated annealing. ''Comput Appl Biosci'' 10(4):419-26.
=== Survey articles ===
| |||