A new fast heuristic for computing the breakpoint phylogeny and experimental phylogenetic analyses of real and synthetic data.

M. E. Cosner, R. K. Jansen, B. M. Moret, L. A. Raubeson, L. S. Wang, Tandy Warnow, S. Wyman

Research output: Chapter in Book/Report/Conference proceedingChapter

Abstract

The breakpoint phylogeny is an optimization problem proposed by Blanchette et al. for reconstructing evolutionary trees from gene order data. These same authors also developed and implemented BPAnalysis [3], a heuristic method (based upon solving many instances of the travelling salesman problem) for estimating the breakpoint phylogeny. We present a new heuristic for this purpose; although not polynomial-time, our heuristic is much faster in practice than BPAnalysis. We present and discuss the results of experimentation on synthetic datasets and on the flowering plant family Campanulaceae with three methods: our new method, BPAnalysis, and the neighbor-joining method [25] using several distance estimation techniques. Our preliminary results indicate that, on datasets with slow evolutionary rates and large numbers of genes in comparison with the number of taxa (genomes), all methods recover quite accurate reconstructions of the true evolutionary history (although BPAnalysis is too slow to be practical), but that on datasets where the rate of evolution is high relative to the number of genes, the accuracy of all three methods is poor.

Original languageEnglish
Title of host publicationProceedings / . International Conference on Intelligent Systems for Molecular Biology ; ISMB. International Conference on Intelligent Systems for Molecular Biology
Pages104-115
Number of pages12
Volume8
StatePublished - Dec 1 2000
Externally publishedYes

    Fingerprint

Cite this

Cosner, M. E., Jansen, R. K., Moret, B. M., Raubeson, L. A., Wang, L. S., Warnow, T., & Wyman, S. (2000). A new fast heuristic for computing the breakpoint phylogeny and experimental phylogenetic analyses of real and synthetic data. In Proceedings / . International Conference on Intelligent Systems for Molecular Biology ; ISMB. International Conference on Intelligent Systems for Molecular Biology (Vol. 8, pp. 104-115)