Hard optimization problems in phylogenetic reconstruction

Current approaches for phylogenetic reconstruction generally attempt to solve hard optimization problems such as maximum parsimony and maximum likelihood. However, current techniques do not seem able to provide good analyses on datasets containing thousands of sequences in reasonable time periods. Finding new approaches which can enable new techniques to scale to datasets containing tens of thousands of sequences is the focus of the algorithms research for CIPRES. Our current techniques employ a particular divide-and-conquer strategy to work with existing "base methods". The divide-and-conquer strategy we are currently investigating, Rec-I-DCM3, is able to speed up the best of the currently available software for maximum parsimony dramatically (probably two orders of magnitude for large and difficult datasets) The CIPRES project is developing open source software for Rec-I-DCM3 for use with PAUP* and other software products. Ongoing research is investigating how to speed-up heuristics for maximum likelihood, where even bigger improvements are expected.



People

• Tandy Warnow,  Department of Computer Sciences, UT-Austin
• Bernard Moret,   Department of Computer Sciences, University of New Mexico
• Usman Roshan,   Department of Computer Science, New Jersey Institute of Technology
• Tiffani Williams, Department of Computer Science,   Texas A&M. (Currently at the Radcliffe Institute of Advanced Study.)

Rec-I-DCM3 is described in

• U. Roshan, B. M. E. Moret, T. L. Williams, T. Warnow, Rec-I-DCM3: A Fast Algorithmic Technique for Reconstructing Large Phylogenetic Trees, Proceedings of the IEEE Computational Systems Bioinformatics conference (CSB) 2004 Abstract Text (pdf)