97-17: Constructing big trees from short sequences

DIMACS TR: 97-17

Constructing big trees from short sequences

Authors: Peter L. Erdos, Michael A. Steel, Laszlo A. Szekely and Tandy J. Warnow

ABSTRACT
The construction of evolutionary trees is a fundamental problem in biology, and yet methods for reconstructing evolutionary trees are not reliable when it comes to inferring accurate topologies of large divergent evolutionary trees from realistic lengh sequences. We address this problem and present a new polynomial time algorithm for reconstructing evolutionary trees called the Short Quartets Method which is consistent and which has greater statistical power than other polynomial time methods, such as Neighbor-Joining and the 3-approximation algorithm by Agarwala et al. (and the "Double Pivot" variant of the Agarwala et al. algorithm by Cohen and Farach) for the $L_{\infty}$-nearest tree problem. Our study indicates that our method will produce the correct topology from shorter sequences than can be guranteed using these other methods.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-17.ps.gz

DIMACS Home Page