A hidden Markov model for progressive multiple alignment.
BACKGROUND
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.


RESULTS
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.
Löytynoja
Ari
A
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. aloytyno@ulb.ac.be
Milinkovitch
Michel C
MC
D000465:Algorithms; D030541:Databases, Genetic; D020869:Gene Expression Profiling / Q000379:methods*; D008390:Markov Chains; D008957:Models, Genetic; D015233:Models, Statistical; D015203:Reproducibility of Results; D012680:Sensitivity and Specificity; D017422:Sequence Analysis, DNA / Q000379:methods*; D020539:Sequence Analysis, Protein / Q000379:methods*; D012984:Software