Jump to content United States-English
HP.com Home Products and Services Support and Drivers Solutions How to Buy
» Contact HP

hp.com home

Technical Reports

printable version

HP Labs

» Research
» News and events
» Technical reports
» About HP Labs
» Careers @ HP Labs
» Worldwide sites
» Downloads
Content starts here

Click here for full text: PDF

On the Complexity of Distance-based Evolutionary Tree Reconstruction

King, Valerie; Zhang, Li; Zhou, Yunhong


Keyword(s): evolutionary tree reconstruction; algorithm; complexity; bioinformatics

Abstract: We give the first tight lower bounds on the complexity of reconstructing k-ary evolutionary trees from additive distance data. We also consider the problem under DNA-based distance estimation assumptions, where the accuracy of distance data depends on the length of the sequence and the distance. We give the first o(n^2) algorithm to reconstruct trees in this context, and prove a trade-off between the length of the DNA sequences and the number of distance queries needed to reconstruct the tree. We introduce new computational models for understanding this problem, which simplify the development of algorithms. We prove lower bounds in these models which apply to the type of techniques currently in use. Notes: Copyright SIAM To be published in and presented at the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 12-14 January 2003, Baltimore, Maryland

22 Pages

Back to Index

»Technical Reports

» 2009
» 2008
» 2007
» 2006
» 2005
» 2004
» 2003
» 2002
» 2001
» 2000
» 1990 - 1999

Heritage Technical Reports

» Compaq & DEC Technical Reports
» Tandem Technical Reports
Privacy statement Using this site means you accept its terms Feedback to HP Labs
© 2009 Hewlett-Packard Development Company, L.P.