Access Restriction

Author Huson, D. ♦ Nettles, S. ♦ Rice, K. ♦ Warnow, T. ♦ Yooseph, S.
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©1999
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Computer programming, programs & data
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.
ISSN 10846654
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 1999-12-01
Publisher Place New York
e-ISSN 10846654
Journal Journal of Experimental Algorithmics (JEA)
Volume Number 4

Open content in new tab

   Open content in new tab
Source: ACM Digital Library