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 proceedingConference 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 languageEnglish (US)
Title of host publicationProceedings - 2004 IEEE Computational Systems Bioinformatics Conference, CSB 2004
PublisherIEEE Computer Society
Pages98-109
Number of pages12
ISBN (Print)0769521940, 9780769521947
StatePublished - Jan 1 2004
Externally publishedYes
EventProceedings - 2004 IEEE Computational Systems Bioinformatics Conference, CSB 2004 - Stanford, CA, United States
Duration: Aug 16 2004Aug 19 2004

Publication series

NameProceedings - 2004 IEEE Computational Systems Bioinformatics Conference, CSB 2004

Other

OtherProceedings - 2004 IEEE Computational Systems Bioinformatics Conference, CSB 2004
CountryUnited States
CityStanford, CA
Period8/16/048/19/04

ASJC Scopus subject areas

  • Engineering(all)

Fingerprint Dive into the research topics of 'Rec-I-DCM3: A fast algorithmic technique for reconstructing large phylogenetic trees'. Together they form a unique fingerprint.

  • Cite this

    Roshan, U. W., Warnow, T., Moret, B. M. E., & Williams, T. L. (2004). Rec-I-DCM3: A fast algorithmic technique for reconstructing large phylogenetic trees. In Proceedings - 2004 IEEE Computational Systems Bioinformatics Conference, CSB 2004 (pp. 98-109). (Proceedings - 2004 IEEE Computational Systems Bioinformatics Conference, CSB 2004). IEEE Computer Society.