Sequence-length requirements for phylogenetic methods

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

doi:10.1007/3-540-45784-4_26

Sequence-length requirements for phylogenetic methods

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

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

37 Scopus citations

Abstract

We study the sequence lengths required by neighbor-joining, greedy parsimony, and a phylogenetic reconstruction method (DCM_NJ+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 DCM_NJ+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 language	English (US)
Title of host publication	Algorithms in Bioinformatics - 2nd International Workshop,WABI 2002, Proceedings
Editors	Roderic Guigo, Dan Gusfield
Publisher	Springer Verlag
Pages	343-356
Number of pages	14
ISBN (Print)	3540442111, 9783540442110
DOIs	https://doi.org/10.1007/3-540-45784-4_26
State	Published - 2002
Externally published	Yes
Event	2nd International Workshop on Algorithms in Bioinformatics, WABI 2002 - Rome, Italy Duration: Sep 17 2002 → Sep 21 2002

Publication series

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

Other

Other	2nd International Workshop on Algorithms in Bioinformatics, WABI 2002
Country/Territory	Italy
City	Rome
Period	9/17/02 → 9/21/02

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/3-540-45784-4_26

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. https://doi.org/10.1007/3-540-45784-4_26

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{4da4575d2b3a4d309f66e62efc22e43d,

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",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 2002.; 2nd International Workshop on Algorithms in Bioinformatics, WABI 2002 ; Conference date: 17-09-2002 Through 21-09-2002",

year = "2002",

doi = "10.1007/3-540-45784-4_26",

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",

address = "Germany",

}

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. https://doi.org/10.1007/3-540-45784-4_26

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 proceeding › Conference contribution

TY - GEN

T1 - Sequence-length requirements for phylogenetic methods

AU - Moret, Bernard M.E.

AU - Roshan, Usman

AU - Warnow, Tandy

N1 - Publisher Copyright: © Springer-Verlag Berlin Heidelberg 2002.

PY - 2002

Y1 - 2002

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

U2 - 10.1007/3-540-45784-4_26

DO - 10.1007/3-540-45784-4_26

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

T2 - 2nd International Workshop on Algorithms in Bioinformatics, WABI 2002

Y2 - 17 September 2002 through 21 September 2002

ER -

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)). doi: 10.1007/3-540-45784-4_26

Sequence-length requirements for phylogenetic methods

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this