Sequence-length requirements for phylogenetic methods

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

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

Abstract

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
Pages343-356
Number of pages14
ISBN (Print)3540442111, 9783540442110
StatePublished - Jan 1 2002
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)
Volume2452
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other2nd International Workshop on Algorithms in Bioinformatics, WABI 2002
CountryItaly
CityRome
Period9/17/029/21/02

Fingerprint

Phylogenetics
Joining
Deviation
Requirements
Experiments
Maximum Parsimony
Parsimony
Covering
Scaling
Experiment
Simulation

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this

Moret, B. M. E., Roshan, U., & Warnow, T. (2002). Sequence-length requirements for phylogenetic methods. In R. Guigo, & D. Gusfield (Eds.), Algorithms in Bioinformatics - 2nd International Workshop,WABI 2002, Proceedings (pp. 343-356). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2452). Springer-Verlag.

Sequence-length requirements for phylogenetic methods. / Moret, Bernard M.E.; Roshan, Usman; Warnow, Tandy.

Algorithms in Bioinformatics - 2nd International Workshop,WABI 2002, Proceedings. ed. / Roderic Guigo; Dan Gusfield. Springer-Verlag, 2002. p. 343-356 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2452).

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

Moret, BME, Roshan, U & Warnow, T 2002, Sequence-length requirements for phylogenetic methods. in R Guigo & D Gusfield (eds), Algorithms in Bioinformatics - 2nd International Workshop,WABI 2002, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 2452, Springer-Verlag, pp. 343-356, 2nd International Workshop on Algorithms in Bioinformatics, WABI 2002, Rome, Italy, 9/17/02.
Moret BME, Roshan U, Warnow T. Sequence-length requirements for phylogenetic methods. In Guigo R, Gusfield D, editors, Algorithms in Bioinformatics - 2nd International Workshop,WABI 2002, Proceedings. Springer-Verlag. 2002. p. 343-356. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
Moret, Bernard M.E. ; Roshan, Usman ; Warnow, Tandy. / Sequence-length requirements for phylogenetic methods. Algorithms in Bioinformatics - 2nd International Workshop,WABI 2002, Proceedings. editor / Roderic Guigo ; Dan Gusfield. Springer-Verlag, 2002. pp. 343-356 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{287ee210b9264200b0c623e04b63361c,
title = "Sequence-length requirements for phylogenetic methods",
abstract = "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).",
author = "Moret, {Bernard M.E.} and Usman Roshan and Tandy Warnow",
year = "2002",
month = "1",
day = "1",
language = "English (US)",
isbn = "3540442111",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer-Verlag",
pages = "343--356",
editor = "Roderic Guigo and Dan Gusfield",
booktitle = "Algorithms in Bioinformatics - 2nd International Workshop,WABI 2002, Proceedings",

}

TY - GEN

T1 - Sequence-length requirements for phylogenetic methods

AU - Moret, Bernard M.E.

AU - Roshan, Usman

AU - Warnow, Tandy

PY - 2002/1/1

Y1 - 2002/1/1

N2 - 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).

AB - 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).

UR - http://www.scopus.com/inward/record.url?scp=84889959894&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84889959894&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:84889959894

SN - 3540442111

SN - 9783540442110

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 343

EP - 356

BT - Algorithms in Bioinformatics - 2nd International Workshop,WABI 2002, Proceedings

A2 - Guigo, Roderic

A2 - Gusfield, Dan

PB - Springer-Verlag

ER -