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:
|
|
 |
|
  I. Miklos, A. Novak, R. Satija, R. Lyngso, and J. Hein Stochastic models of sequence evolution including insertion--deletion events Statistical Methods in Medical Research, October 1, 2009; 18(5): 453 - 485. [Abstract] [PDF]
|
|
|
|
 |
|
 Y. Yamanoue, M. Miya, K. Matsuura, S. Miyazawa, N. Tsukamoto, H. Doi, H. Takahashi, K. Mabuchi, M. Nishida, and H. Sakai Explosive Speciation of Takifugu: Another Use of Fugu as a Model System for Evolutionary Biology Mol. Biol. Evol., March 1, 2009; 26(3): 623 - 629. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 L. J. Harmon, J. Melville, A. Larson, and J. B. Losos The Role of Geography and Ecological Opportunity in the Diversification of Day Geckos (Phelsuma) Syst Biol, August 1, 2008; 57(4): 562 - 573. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 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]
|
|
|
|
|
|
E. Benavides, R. Baum, D. McClellan, and J. W. Sites Molecular Phylogenetics of the Lizard Genus Microlophus (Squamata:Tropiduridae): Aligning and Retrieving Indel Signal from Nuclear Introns Syst Biol, October 1, 2007; 56(5): 776 - 797. [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]
|
|
|
|
|
|
A. B. Smythe, M. J. Sanderson, and S. A. Nadler Nematode Small Subunit Phylogeny Correlates with Alignment Parameters Syst Biol, December 1, 2006; 55(6): 972 - 992. [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]
|
|
|
|
|
|
D. Lanterbecq, G. W. Rouse, M. C. Milinkovitch, and I. Eeckhaut Molecular Phylogenetic Analyses Indicate Multiple Independent Emergences of Parasitism in Myzostomida (Protostomia) Syst Biol, April 1, 2006; 55(2): 208 - 227. [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]
|
|
|
|
|
|
K. Roelants and F. Bossuyt Archaeobatrachian Paraphyly and Pangaean Diversification of Crown-Group Frogs Syst Biol, February 1, 2005; 54(1): 111 - 126. [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]
|
|