Löytynoja Ari, Milinkovitch Michel C
Unit of Evolutionary Genetics, Free University of Brussels (ULB), cp 300, Institute of Molecular Biology and Medicine, rue Jeener & Brachet 12, B-6041 Gosselies, Belgium.
Bioinformatics. 2003 Aug 12;19(12):1505-13. doi: 10.1093/bioinformatics/btg193.
Progressive algorithms are widely used heuristics for the production of alignments among multiple nucleic-acid or protein sequences. Probabilistic approaches providing measures of global and/or local reliability of individual solutions would constitute valuable developments.
We present here a new method for multiple sequence alignment that combines an HMM approach, a progressive alignment algorithm, and a probabilistic evolution model describing the character substitution process. Our method works by iterating pairwise alignments according to a guide tree and defining each ancestral sequence from the pairwise alignment of its child nodes, thus, progressively constructing a multiple alignment. Our method allows for the computation of each column minimum posterior probability and we show that this value correlates with the correctness of the result, hence, providing an efficient mean by which unreliably aligned columns can be filtered out from a multiple alignment.
渐进算法是用于生成多个核酸或蛋白质序列比对的广泛使用的启发式方法。提供个体解决方案的全局和/或局部可靠性度量的概率方法将是有价值的进展。
我们在此提出一种新的多序列比对方法，该方法结合了隐马尔可夫模型方法、渐进比对算法和描述字符替换过程的概率进化模型。我们的方法通过根据引导树迭代成对比对，并从其子节点的成对比对中定义每个祖先序列，从而逐步构建多序列比对。我们的方法允许计算每列的最小后验概率，并且我们表明该值与结果的正确性相关，因此，提供了一种有效的方法，通过该方法可以从多序列比对中过滤出不可靠比对的列。
