ACM logo

The ACM Journal of Experimental Algorithmics

Volume 4, Article 5, 1999

Hybrid Tree Reconstruction Methods

by

Daniel Huson

and

Scott Nettles

and

Kenneth Rice

and

Tandy Warnow

and

Shibu Yooseph

http://www.jea.acm.org/1999/HusonHybrid/


Abstract:

A major computational problem in biology is the reconstruction of evolutionary trees for species sets, and accuracy is measured by comparing the topologies of the reconstructed tree and the model tree. One of the major debates in the field is whether large evolutionary trees can be even approximately accurately reconstructed from biomolecular sequences of realistically bounded lengths (up to about 2000 nucleotides) using standard techniques (polynomial-time distance methods, and heuristics for NP-hard optimization problems). Using both analytical and experimental techniques, we show that on large trees, the two most popular methods in systematic biology, Neighbor-Joining and Maximum Parsimony heuristics, as well as two promising methods introduced by theoretical computer scientists, are all likely to have significant errors in the topology reconstruction of the model tree. We also present a new general technique for combining outputs of different methods (thus producing hybrid methods), and show experimentally how one such hybrid method has better performance than its constituent parts.

  • Keywords:
  • CR Categories:
  • Sources:

    Received
    		 Accepted
    		 Final Revision
    		 Published
    April 1, 1999
    		 March 9, 2000
    		 June 12, 2000
    		 June 12, 2000

    Last updated and validated June 12, 2000, by editor@jea.acm.org