Rec-I-DCM3: A fast algorithmic technique for reconstructing large phylogenetic trees

Usman W. Roshan; Tandy Warnow; Bernard M.E. Moret; Tiffani L. Williams

Rec-I-DCM3: A fast algorithmic technique for reconstructing large phylogenetic trees

Usman W. Roshan, Tandy Warnow, Bernard M.E. Moret, Tiffani L. Williams

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

Abstract

Phylogenetic trees are commonly reconstructed based on hard optimization problems such as maximum parsimony (MP) and maximum likelihood (ML). Conventional MP heuristics for producing phylogenetic trees produce good solutions within reasonable time on small datasets (up to a few thousand sequences), while ML heuristics are limited to smaller datasets (up to a few hundred sequences). However, since MP (and presumably ML) is NP-hard, such approaches do not scale when applied to large datasets. In this paper, we present a new technique called Recursive-Iterative-DCM3 (Rec-I-DCM3), which belongs to our family of Disk-Covering Methods (DCMs). We tested this new ' technique on ten large biological datasets ranging from 1,322 to 13,921 sequences and obtained dramatic speedups as well as significant improvements in accuracy (better than 99.99%) in comparison to existing approaches. Thus, high-quality reconstructions can be obtained for datasets at least ten times larger than was previously possible.

Original language	English (US)
Title of host publication	Proceedings - 2004 IEEE Computational Systems Bioinformatics Conference, CSB 2004
Publisher	IEEE Computer Society
Pages	98-109
Number of pages	12
ISBN (Print)	0769521940, 9780769521947
State	Published - 2004
Externally published	Yes
Event	Proceedings - 2004 IEEE Computational Systems Bioinformatics Conference, CSB 2004 - Stanford, CA, United States Duration: Aug 16 2004 → Aug 19 2004

Publication series

Name	Proceedings - 2004 IEEE Computational Systems Bioinformatics Conference, CSB 2004

Other

Other	Proceedings - 2004 IEEE Computational Systems Bioinformatics Conference, CSB 2004
Country/Territory	United States
City	Stanford, CA
Period	8/16/04 → 8/19/04

All Science Journal Classification (ASJC) codes

General Engineering

Cite this

@inproceedings{55388b57eedf4a48863f21901a02aef0,

title = "Rec-I-DCM3: A fast algorithmic technique for reconstructing large phylogenetic trees",

abstract = "Phylogenetic trees are commonly reconstructed based on hard optimization problems such as maximum parsimony (MP) and maximum likelihood (ML). Conventional MP heuristics for producing phylogenetic trees produce good solutions within reasonable time on small datasets (up to a few thousand sequences), while ML heuristics are limited to smaller datasets (up to a few hundred sequences). However, since MP (and presumably ML) is NP-hard, such approaches do not scale when applied to large datasets. In this paper, we present a new technique called Recursive-Iterative-DCM3 (Rec-I-DCM3), which belongs to our family of Disk-Covering Methods (DCMs). We tested this new ' technique on ten large biological datasets ranging from 1,322 to 13,921 sequences and obtained dramatic speedups as well as significant improvements in accuracy (better than 99.99%) in comparison to existing approaches. Thus, high-quality reconstructions can be obtained for datasets at least ten times larger than was previously possible.",

author = "Roshan, {Usman W.} and Tandy Warnow and Moret, {Bernard M.E.} and Williams, {Tiffani L.}",

year = "2004",

language = "English (US)",

isbn = "0769521940",

series = "Proceedings - 2004 IEEE Computational Systems Bioinformatics Conference, CSB 2004",

publisher = "IEEE Computer Society",

pages = "98--109",

booktitle = "Proceedings - 2004 IEEE Computational Systems Bioinformatics Conference, CSB 2004",

address = "United States",

note = "Proceedings - 2004 IEEE Computational Systems Bioinformatics Conference, CSB 2004 ; Conference date: 16-08-2004 Through 19-08-2004",

}

Roshan, UW, Warnow, T, Moret, BME & Williams, TL 2004, Rec-I-DCM3: A fast algorithmic technique for reconstructing large phylogenetic trees. in Proceedings - 2004 IEEE Computational Systems Bioinformatics Conference, CSB 2004. Proceedings - 2004 IEEE Computational Systems Bioinformatics Conference, CSB 2004, IEEE Computer Society, pp. 98-109, Proceedings - 2004 IEEE Computational Systems Bioinformatics Conference, CSB 2004, Stanford, CA, United States, 8/16/04.

Rec-I-DCM3: A fast algorithmic technique for reconstructing large phylogenetic trees. / Roshan, Usman W.; Warnow, Tandy; Moret, Bernard M.E. et al.
Proceedings - 2004 IEEE Computational Systems Bioinformatics Conference, CSB 2004. IEEE Computer Society, 2004. p. 98-109 (Proceedings - 2004 IEEE Computational Systems Bioinformatics Conference, CSB 2004).

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

TY - GEN

T1 - Rec-I-DCM3

T2 - Proceedings - 2004 IEEE Computational Systems Bioinformatics Conference, CSB 2004

AU - Roshan, Usman W.

AU - Warnow, Tandy

AU - Moret, Bernard M.E.

AU - Williams, Tiffani L.

PY - 2004

Y1 - 2004

N2 - Phylogenetic trees are commonly reconstructed based on hard optimization problems such as maximum parsimony (MP) and maximum likelihood (ML). Conventional MP heuristics for producing phylogenetic trees produce good solutions within reasonable time on small datasets (up to a few thousand sequences), while ML heuristics are limited to smaller datasets (up to a few hundred sequences). However, since MP (and presumably ML) is NP-hard, such approaches do not scale when applied to large datasets. In this paper, we present a new technique called Recursive-Iterative-DCM3 (Rec-I-DCM3), which belongs to our family of Disk-Covering Methods (DCMs). We tested this new ' technique on ten large biological datasets ranging from 1,322 to 13,921 sequences and obtained dramatic speedups as well as significant improvements in accuracy (better than 99.99%) in comparison to existing approaches. Thus, high-quality reconstructions can be obtained for datasets at least ten times larger than was previously possible.

AB - Phylogenetic trees are commonly reconstructed based on hard optimization problems such as maximum parsimony (MP) and maximum likelihood (ML). Conventional MP heuristics for producing phylogenetic trees produce good solutions within reasonable time on small datasets (up to a few thousand sequences), while ML heuristics are limited to smaller datasets (up to a few hundred sequences). However, since MP (and presumably ML) is NP-hard, such approaches do not scale when applied to large datasets. In this paper, we present a new technique called Recursive-Iterative-DCM3 (Rec-I-DCM3), which belongs to our family of Disk-Covering Methods (DCMs). We tested this new ' technique on ten large biological datasets ranging from 1,322 to 13,921 sequences and obtained dramatic speedups as well as significant improvements in accuracy (better than 99.99%) in comparison to existing approaches. Thus, high-quality reconstructions can be obtained for datasets at least ten times larger than was previously possible.

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

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

M3 - Conference contribution

C2 - 16448004

AN - SCOPUS:14044251530

SN - 0769521940

SN - 9780769521947

T3 - Proceedings - 2004 IEEE Computational Systems Bioinformatics Conference, CSB 2004

SP - 98

EP - 109

BT - Proceedings - 2004 IEEE Computational Systems Bioinformatics Conference, CSB 2004

PB - IEEE Computer Society

Y2 - 16 August 2004 through 19 August 2004

ER -

Rec-I-DCM3: A fast algorithmic technique for reconstructing large phylogenetic trees

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Other files and links

Fingerprint

Cite this