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

Phylogeny
Campanulaceae
Gene Order
Genes
Heuristics
History
Genome
Datasets

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)

A new fast heuristic for computing the breakpoint phylogeny and experimental phylogenetic analyses of real and synthetic data. / Cosner, M. E.; Jansen, R. K.; Moret, B. M.; Raubeson, L. A.; Wang, L. S.; Warnow, Tandy; Wyman, S.

Proceedings / . International Conference on Intelligent Systems for Molecular Biology ; ISMB. International Conference on Intelligent Systems for Molecular Biology. Vol. 8 2000. p. 104-115.

Research output: Chapter in Book/Report/Conference proceedingChapter

Cosner, ME, Jansen, RK, Moret, BM, Raubeson, LA, Wang, LS, 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.
Cosner ME, Jansen RK, Moret BM, Raubeson LA, Wang LS, Warnow T et al. 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. 2000. p. 104-115
Cosner, M. E. ; Jansen, R. K. ; Moret, B. M. ; Raubeson, L. A. ; Wang, L. S. ; Warnow, Tandy ; Wyman, S. / A new fast heuristic for computing the breakpoint phylogeny and experimental phylogenetic analyses of real and synthetic data. Proceedings / . International Conference on Intelligent Systems for Molecular Biology ; ISMB. International Conference on Intelligent Systems for Molecular Biology. Vol. 8 2000. pp. 104-115
@inbook{f4d45957a0c44c7cb3db654d64da3b8c,
title = "A new fast heuristic for computing the breakpoint phylogeny and experimental phylogenetic analyses of real and synthetic data.",
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.",
author = "Cosner, {M. E.} and Jansen, {R. K.} and Moret, {B. M.} and Raubeson, {L. A.} and Wang, {L. S.} and Tandy Warnow and S. Wyman",
year = "2000",
month = "12",
day = "1",
language = "English",
volume = "8",
pages = "104--115",
booktitle = "Proceedings / . International Conference on Intelligent Systems for Molecular Biology ; ISMB. International Conference on Intelligent Systems for Molecular Biology",

}

TY - CHAP

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

AU - Cosner, M. E.

AU - Jansen, R. K.

AU - Moret, B. M.

AU - Raubeson, L. A.

AU - Wang, L. S.

AU - Warnow, Tandy

AU - Wyman, S.

PY - 2000/12/1

Y1 - 2000/12/1

N2 - 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.

AB - 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.

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

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

M3 - Chapter

C2 - 10977071

AN - SCOPUS:0034566411

VL - 8

SP - 104

EP - 115

BT - Proceedings / . International Conference on Intelligent Systems for Molecular Biology ; ISMB. International Conference on Intelligent Systems for Molecular Biology

ER -