Mount David W
Cold Spring Harb Protoc. 2009 Jul;2009(7):pdb.top44. doi: 10.1101/pdb.top44.
Finding a global optimal alignment of more than two sequences that includes matches, mismatches, and gaps and that takes into account the degree of variation in all of the sequences at the same time is especially difficult. The dynamic programming algorithm used for optimal alignment of pairs of sequences can be extended to global alignment of three sequences, but for more than three sequences, only a small number of relatively short sequences may be analyzed. Thus, approximate methods are used for global alignment. One class of these is iterative global alignment, which makes an initial global alignment of groups of sequences and then revises the alignment to achieve a more reasonable result. This article discusses several iterative alignment methods. In particular, steps are provided for using the Sequence Alignment by Genetic Algorithm (SAGA).
找到包含匹配、错配和空位且同时考虑所有序列变异程度的两个以上序列的全局最优比对尤其困难。用于两个序列对最优比对的动态规划算法可以扩展到三个序列的全局比对，但对于三个以上的序列，可能只能分析少量相对较短的序列。因此，近似方法被用于全局比对。其中一类是迭代全局比对，它对序列组进行初始全局比对，然后修正比对以获得更合理的结果。本文讨论了几种迭代比对方法。特别地，提供了使用遗传算法序列比对（SAGA）的步骤。
