Bioinformatics Vol. 16 no. 4 2000
Pages 383-394
© 2000 Oxford University Press
TrExML: a maximum-likelihood approach for extensive tree-space exploration
1 Department of Mathematics and Computer
Science, Bemidji State University, Bemidji, MN 56601-2699, USA
2 The John Curtin School of Medical
Research, The Australian National University, Canberra ACT 0200,
Australia
3 ANU Supercomputer Facility, The Australian
National University, Canberra ACT 0200, Australia
4 Department of Computer Science, The
Australian National University, Canberra ACT 0200, Australia
Received on March 28, 1999
; revised on August 30, 1999
; accepted on October 11, 1999
*To whom correspondence should be addressed. 5 Present address: Australian Genomics Information Centre, Building C80, University of Sydney, Sydney, NSW 2006, Australia.
Motivation: Maximum-likelihood analysis of nucleotide and amino acid sequences is a powerful approach for inferring phylogenetic relationships and for comparing evolutionary hypotheses. Because it is a computationally demanding and time-consuming process, most algorithms explore only a minute portion of tree-space, with the emphasis on finding the most likely tree while ignoring the less likely, but not significantly worse, trees. However, when such trees exist, it is equally important to identify them to give due consideration to the phylogenetic uncertainty. Consequently, it is necessary to change the focus of these algorithms such that near optimal trees are also identified.
Results: This paper presents the Advanced Stepwise Addition Algorithmfor exploring tree-space and two algorithms for generating all binary trees on a set of sequences. The Advanced Stepwise Addition Algorithm has been implemented in TrExML, a phylogenetic program for maximum-likelihood analysis of nucleotide sequences. TrExML is shown to be more effective at finding near optimal trees than a similar program, fastDNAml, implying that TrExML offers a better approach to account for phylogenetic uncertainty than has previously been possible. A program, TreeGen, is also described; it generates binary trees on a set of sequences allowing for extensive exploration of tree-space using other programs.
Availability: TreeGen, TrExML, and the sequence data used to test the programs are available from the following two WWW sites: http://whitetail.bemidji.msus.edu/trexml/and http://jcsmr.anu.edu.au/dmm/humgen.html.
Contact: mjwolf{at}whitetail.bemidji.msus.edu; Simon.Easteal{at}anu.edu.au; Margaret.Kahn{at}anu.edu.au; bdm{at}cs.anu.edu.au; jermiin{at}angis.usyd.edu.au
CiteULike 
Connotea 
Del.icio.us What's this?
This article has been cited by other articles:
|
|
 |
|
  M. Premzl, J. E. Gready, L. S. Jermiin, T. Simonic, and J. A. Marshall Graves Evolution of Vertebrate Genes Related to Prion and Shadoo Proteins--Clues from Comparative Genomic Analysis Mol. Biol. Evol., December 1, 2004; 21(12): 2210 - 2231. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 S. Wong, G. Butler, and K. H. Wolfe Gene order evolution and paleopolyploidy in hemiascomycete yeasts PNAS, July 9, 2002; 99(14): 9272 - 9277. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 R. S. Millen, R. G. Olmstead, K. L. Adams, J. D. Palmer, N. T. Lao, L. Heggie, T. A. Kavanagh, J. M. Hibberd, J. C. Gray, C. W. Morden, et al. Many Parallel Losses of infA from Chloroplast DNA during Angiosperm Evolution with Multiple Independent Transfers to the Nucleus PLANT CELL, March 1, 2001; 13(3): 645 - 658. [Abstract] [Full Text]
|
|
|
|
|
|
G. J. Adcock, E. S. Dennis, S. Easteal, G. A. Huttley, L. S. Jermiin, W. J. Peacock, and A. Thorne From the Cover: Mitochondrial DNA sequences in ancient Australians: Implications for modern human origins PNAS, January 16, 2001; 98(2): 537 - 542. [Abstract] [Full Text] [PDF]
|
|