A new implementation and detailed study of breakpoint analysis.

B. M. Moret, S. Wyman, D. A. Bader, Tandy Warnow, M. Yan

Research output: Chapter in Book/Report/Conference proceedingChapter

Abstract

Phylogenies derived from gene order data may prove crucial in answering some fundamental open questions in biomolecular evolution. Yet very few techniques are available for such phylogenetic reconstructions. One method is breakpoint analysis, developed by Blanchette and Sankoff for solving the "breakpoint phylogeny." Our earlier studies confirmed the usefulness of this approach, but also found that BPAnalysis, the implementation developed by Sankoff and Blanchette, was too slow to use on all but very small datasets. We report here on a reimplementation of BPAnalysis using the principles of algorithmic engineering. Our faster (by 2 to 3 orders of magnitude) and flexible implementation allowed us to conduct studies on the characteristics of breakpoint analysis, in terms of running time, quality, and robustness, as well as to analyze datasets that had so far been considered out of reach. We report on these findings and also discuss future directions for our new implementation.

Original languageEnglish
Title of host publicationPacific Symposium on Biocomputing. Pacific Symposium on Biocomputing
Pages583-594
Number of pages12
StatePublished - Mar 23 2001
Externally publishedYes

Fingerprint

Phylogeny
Gene Order
Datasets
Direction compound

Cite this

Moret, B. M., Wyman, S., Bader, D. A., Warnow, T., & Yan, M. (2001). A new implementation and detailed study of breakpoint analysis. In Pacific Symposium on Biocomputing. Pacific Symposium on Biocomputing (pp. 583-594)

A new implementation and detailed study of breakpoint analysis. / Moret, B. M.; Wyman, S.; Bader, D. A.; Warnow, Tandy; Yan, M.

Pacific Symposium on Biocomputing. Pacific Symposium on Biocomputing. 2001. p. 583-594.

Research output: Chapter in Book/Report/Conference proceedingChapter

Moret, BM, Wyman, S, Bader, DA, Warnow, T & Yan, M 2001, A new implementation and detailed study of breakpoint analysis. in Pacific Symposium on Biocomputing. Pacific Symposium on Biocomputing. pp. 583-594.
Moret BM, Wyman S, Bader DA, Warnow T, Yan M. A new implementation and detailed study of breakpoint analysis. In Pacific Symposium on Biocomputing. Pacific Symposium on Biocomputing. 2001. p. 583-594
Moret, B. M. ; Wyman, S. ; Bader, D. A. ; Warnow, Tandy ; Yan, M. / A new implementation and detailed study of breakpoint analysis. Pacific Symposium on Biocomputing. Pacific Symposium on Biocomputing. 2001. pp. 583-594
@inbook{701115e78c5a475a9bb8cb926dab3e2b,
title = "A new implementation and detailed study of breakpoint analysis.",
abstract = "Phylogenies derived from gene order data may prove crucial in answering some fundamental open questions in biomolecular evolution. Yet very few techniques are available for such phylogenetic reconstructions. One method is breakpoint analysis, developed by Blanchette and Sankoff for solving the {"}breakpoint phylogeny.{"} Our earlier studies confirmed the usefulness of this approach, but also found that BPAnalysis, the implementation developed by Sankoff and Blanchette, was too slow to use on all but very small datasets. We report here on a reimplementation of BPAnalysis using the principles of algorithmic engineering. Our faster (by 2 to 3 orders of magnitude) and flexible implementation allowed us to conduct studies on the characteristics of breakpoint analysis, in terms of running time, quality, and robustness, as well as to analyze datasets that had so far been considered out of reach. We report on these findings and also discuss future directions for our new implementation.",
author = "Moret, {B. M.} and S. Wyman and Bader, {D. A.} and Tandy Warnow and M. Yan",
year = "2001",
month = "3",
day = "23",
language = "English",
pages = "583--594",
booktitle = "Pacific Symposium on Biocomputing. Pacific Symposium on Biocomputing",

}

TY - CHAP

T1 - A new implementation and detailed study of breakpoint analysis.

AU - Moret, B. M.

AU - Wyman, S.

AU - Bader, D. A.

AU - Warnow, Tandy

AU - Yan, M.

PY - 2001/3/23

Y1 - 2001/3/23

N2 - Phylogenies derived from gene order data may prove crucial in answering some fundamental open questions in biomolecular evolution. Yet very few techniques are available for such phylogenetic reconstructions. One method is breakpoint analysis, developed by Blanchette and Sankoff for solving the "breakpoint phylogeny." Our earlier studies confirmed the usefulness of this approach, but also found that BPAnalysis, the implementation developed by Sankoff and Blanchette, was too slow to use on all but very small datasets. We report here on a reimplementation of BPAnalysis using the principles of algorithmic engineering. Our faster (by 2 to 3 orders of magnitude) and flexible implementation allowed us to conduct studies on the characteristics of breakpoint analysis, in terms of running time, quality, and robustness, as well as to analyze datasets that had so far been considered out of reach. We report on these findings and also discuss future directions for our new implementation.

AB - Phylogenies derived from gene order data may prove crucial in answering some fundamental open questions in biomolecular evolution. Yet very few techniques are available for such phylogenetic reconstructions. One method is breakpoint analysis, developed by Blanchette and Sankoff for solving the "breakpoint phylogeny." Our earlier studies confirmed the usefulness of this approach, but also found that BPAnalysis, the implementation developed by Sankoff and Blanchette, was too slow to use on all but very small datasets. We report here on a reimplementation of BPAnalysis using the principles of algorithmic engineering. Our faster (by 2 to 3 orders of magnitude) and flexible implementation allowed us to conduct studies on the characteristics of breakpoint analysis, in terms of running time, quality, and robustness, as well as to analyze datasets that had so far been considered out of reach. We report on these findings and also discuss future directions for our new implementation.

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

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

M3 - Chapter

C2 - 11262975

AN - SCOPUS:0035234694

SP - 583

EP - 594

BT - Pacific Symposium on Biocomputing. Pacific Symposium on Biocomputing

ER -