An algorithm for progressive multiple alignment of sequences with insertions
An algorithm for progressive multiple alignment of sequences with insertions
复制标题
DOI：
10.1073/pnas.0409137102
复制
发表时间：
2005-07-26
影响因子：
11.1
通讯作者：
Goldman, N
中科院分区：
文献类型：
--
作者：
Löytynoja, A;Goldman, N
动态规划算法保证找到两个序列之间的最佳比对。对于多于几个序列，精确算法在计算上变得不切实际，并且广泛使用迭代成对比对的渐进算法。这些启发式方法有一个严重的缺点，因为成对算法不区分插入和删除，并最终惩罚单个插入事件多次。对于插入的这种不切实际的高罚分通常导致序列的过度匹配和低估插入事件的数量。我们描述了一种修改的传统的比对算法，可以区分插入删除，避免重复惩罚的插入，并说明这种方法与一对隐马尔可夫模型，使用进化评分函数。与传统的渐进式比对方法相比，我们的算法推断了更多的插入事件，并创建了遗传学一致但空间上不太集中的间隙。我们的研究结果表明，一些插入/删除的“热点”实际上可能是传统的比对算法的文物。
Dynamic programming algorithms guarantee to find the optimal alignment between two sequences. For more than a few sequences, exact algorithms become computationally impractical, and progressive algorithms iterating pairwise alignments are widely used. These heuristic methods have a serious drawback because pairwise algorithms do not differentiate insertions from deletions and end up penalizing single insertion events multiple times. Such an unrealistically high penalty for insertions typically results in overmatching of sequences and an underestimation of the number of insertion events. We describe a modification of the traditional alignment algorithm that can distinguish insertion from deletion and avoid repeated penalization of insertions and illustrate this method with a pair hidden Markov model that uses an evolutionary scoring function. In comparison with a traditional progressive alignment method, our algorithm infers a greater number of insertion events and creates gaps that are phylogenetically consistent but spatially less concentrated. Our results suggest that some insertion/deletion "hot spots" may actually be artifacts of traditional alignment algorithms.