Bioinformatics Vol. 19 no. 12 2003
Pages 1505-1513
© 2003 Oxford University Press
A hidden Markov model for progressive multiple alignment
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
Received on November 15, 2002
; revised on February 11, 2003
; accepted on February 21, 2003
Motivation: 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.
Availability: The software is freely available http://www.ulb.ac.be/sciences/ueg/
Contact: aloytyno{at}ulb.ac.be; mcmilink{at}ulb.ac.be.
* To whom correspondence should be addressed.
CiteULike 
Connotea 
Del.icio.us What's this?
This article has been cited by other articles:
|
|
 |
|
  A. Wilm, D. G. Higgins, and C. Notredame R-Coffee: a method for multiple alignment of non-coding RNA Nucleic Acids Res., May 1, 2008; 36(9): e52 - e52. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 P. Fariselli, I. Rossi, E. Capriotti, and R. Casadio The WWWH of remote homolog detection: The state of the art Brief Bioinform, March 1, 2007; 8(2): 78 - 87. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 E. K. Freyhult, J. P. Bollback, and P. P. Gardner Exploring genomic dark matter: A critical assessment of the performance of homology search methods on noncoding RNA Genome Res., January 1, 2007; 17(1): 117 - 125. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 Y. Tabei, K. Tsuda, T. Kin, and K. Asai SCARNA: fast and accurate structural alignment of RNA sequences by matching fixed-length stem fragments Bioinformatics, July 15, 2006; 22(14): 1723 - 1729. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
D. Dalli, A. Wilm, I. Mainz, and G. Steger STRAL: progressive alignment of non-coding RNA using base pairing probability vectors in quadratic time Bioinformatics, July 1, 2006; 22(13): 1593 - 1599. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
A. J. Bordner and R. Abagyan REVCOM: a robust Bayesian method for evolutionary rate estimation Bioinformatics, May 15, 2005; 21(10): 2315 - 2321. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
P. P. Gardner, A. Wilm, and S. Washietl A benchmark of multiple sequence alignment programs upon structural RNAs Nucleic Acids Res., April 28, 2005; 33(8): 2433 - 2439. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
N. Bray and L. Pachter MAVID: Constrained Ancestral Alignment of Multiple Sequences Genome Res., April 1, 2004; 14(4): 693 - 699. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 N. Radjef, E. Gordien, V. Ivaniushina, E. Gault, P. Anais, T. Drugan, J.-C. Trinchet, D. Roulot, M. Tamby, M. C. Milinkovitch, et al. Molecular Phylogenetic Analyses Indicate a Wide and Ancient Radiation of African Hepatitis Delta Virus, Suggesting a Deltavirus Genus of at Least Seven Major Clades J. Virol., March 1, 2004; 78(5): 2537 - 2544. [Abstract] [Full Text] [PDF]
|
|