Sequence-length requirements for phylogenetic methods

Bernard M.E. Moret, Usman Roshan, Tandy Warnow

Research output: Chapter in Book/Report/Conference proceedingConference contribution

37 Scopus citations


We study the sequence lengths required by neighbor-joining, greedy parsimony, and a phylogenetic reconstruction method (DCMNJ+MP) based on disk-covering and the maximum parsimony criterion. We use extensive simulations based on random birth-death trees, with controlled deviations from ultrametricity, to collect data on the scaling of sequence-length requirements for each of the three methods as a function of the number of taxa, the rate of evolution on the tree, and the deviation from ultrametricity. Our experiments show that DCMNJ+MP has consistently lower sequence-length requirements than the other two methods when trees of high topological accuracy are desired, although all methods require much longer sequences as the deviation from ultrametricity or the height of the tree grows. Our study has significant implications for large-scale phylogenetic reconstruction (where sequencelength requirements are a crucial factor), but also for future performance analyses in phylogenetics (since deviations from ultrametricity are proving pivotal).

Original languageEnglish (US)
Title of host publicationAlgorithms in Bioinformatics - 2nd International Workshop,WABI 2002, Proceedings
EditorsRoderic Guigo, Dan Gusfield
PublisherSpringer Verlag
Number of pages14
ISBN (Print)3540442111, 9783540442110
StatePublished - 2002
Externally publishedYes
Event2nd International Workshop on Algorithms in Bioinformatics, WABI 2002 - Rome, Italy
Duration: Sep 17 2002Sep 21 2002

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other2nd International Workshop on Algorithms in Bioinformatics, WABI 2002

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Sequence-length requirements for phylogenetic methods'. Together they form a unique fingerprint.

Cite this