Genetic Algorithms and Simulated Annealing
Standard optimization techniques in computer science — both of which were inspired by, but do not directly reproduce, physical processes — have also been used in an attempt to more efficiently produce quality MSAs. One such technique, genetic algorithms, has been used for MSA production in an attempt to broadly simulate the hypothesized evolutionary process that gave rise to the divergence in the query set. The method works by breaking a series of possible MSAs into fragments and repeatedly rearranging those fragments with the introduction of gaps at varying positions. A general objective function is optimized during the simulation, most generally the "sum of pairs" maximization function introduced in dynamic programming-based MSA methods. A technique for protein sequences has been implemented in the software program SAGA (Sequence Alignment by Genetic Algorithm) and its equivalent in RNA is called RAGA.
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).
Read more about this topic: Multiple Sequence Alignment
Famous quotes containing the words genetic and/or simulated:
“We cannot think of a legitimate argument why ... whites and blacks need be affected by the knowledge that an aggregate difference in measured intelligence is genetic instead of environmental.... Given a chance, each clan ... will encounter the world with confidence in its own worth and, most importantly, will be unconcerned about comparing its accomplishments line-by-line with those of any other clan. This is wise ethnocentricism.”
—Richard Herrnstein (1930–1994)
“Simulated disorder postulates perfect discipline; simulated fear postulates courage; simulated weakness postulates strength.”
—Sun Tzu (6th–5th century B.C.)