Breakpoint medians and breakpoint phylogenies: A fixed-parameter approach.

Breakpoint medians and breakpoint phylogenies: A fixed-parameter approach. Gramm, J. & Niedermeier, R. Bioinformatics, 18 Suppl 2:S128–S139, 2002. Proc. of \emphEuropean Conference on Computational Biology (ECCB 2002)
abstract bibtex

With breakpoint distance, the genome rearrangement field delivered one of the currently most popular measures in phylogenetic studies for related species. Here, BREAKPOINT MEDIAN, which is NP-complete already for three given species (whose genomes are represented as signed orderings), is the core basic problem. For the important special case of three species, approximation (ratio 7/6) and exact heuristic algorithms were developed. Here, we provide an exact, fixed-parameter algorithm with provable performance bounds. For instance, a breakpoint median for three signed orderings over nelements that causes at most d breakpoints can be computed in time O((2.15)(d).n). We show the algorithm's practical usefulness through experimental studies. In particular, we demonstrate that a simple implementation of our algorithm combined with a new tree construction heuristic allows for a new approach to breakpoint phylogeny, yielding evolutionary trees that are competitive in comparison with known results developed in a recent series of papers that use clever algorithm engineering methods.

@Article{gramm02breakpoint,
  author    = {Jens Gramm and Rolf Niedermeier},
  title     = {Breakpoint medians and breakpoint phylogenies: A fixed-parameter approach.},
  journal   = {Bioinformatics},
  year      = {2002},
  volume    = {18 Suppl 2},
  pages     = {S128--S139},
  note      = {Proc. of \emph{European Conference on Computational Biology} (ECCB 2002)},
  abstract  = {With breakpoint distance, the genome rearrangement field delivered one of the currently most popular measures in phylogenetic studies for related species. Here, BREAKPOINT MEDIAN, which is NP-complete already for three given species (whose genomes are represented as signed orderings), is the core basic problem. For the important special case of three species, approximation (ratio 7/6) and exact heuristic algorithms were developed. Here, we provide an exact, fixed-parameter algorithm with provable performance bounds. For instance, a breakpoint median for three signed orderings over nelements that causes at most d breakpoints can be computed in time O((2.15)(d).n). We show the algorithm's practical usefulness through experimental studies. In particular, we demonstrate that a simple implementation of our algorithm combined with a new tree construction heuristic allows for a new approach to breakpoint phylogeny, yielding evolutionary trees that are competitive in comparison with known results developed in a recent series of papers that use clever algorithm engineering methods.},
  file      = {GrammNiedermeier_BreakpointMediansBreakpointPhylogenies_ECCB_2002.pdf:2002/GrammNiedermeier_BreakpointMediansBreakpointPhylogenies_ECCB_2002.pdf:PDF},
  keywords  = {fpt},
  owner     = {Sebastian},
  pmid      = {12385994},
  timestamp = {2006.12.15},
}

Downloads: 0

{"_id":"YsNfSZzCsAWSrxHWq","bibbaseid":"gramm-niedermeier-breakpointmediansandbreakpointphylogeniesafixedparameterapproach-2002","authorIDs":[],"author_short":["Gramm, J.","Niedermeier, R."],"bibdata":{"bibtype":"article","type":"article","author":[{"firstnames":["Jens"],"propositions":[],"lastnames":["Gramm"],"suffixes":[]},{"firstnames":["Rolf"],"propositions":[],"lastnames":["Niedermeier"],"suffixes":[]}],"title":"Breakpoint medians and breakpoint phylogenies: A fixed-parameter approach.","journal":"Bioinformatics","year":"2002","volume":"18 Suppl 2","pages":"S128–S139","note":"Proc. of \\emphEuropean Conference on Computational Biology (ECCB 2002)","abstract":"With breakpoint distance, the genome rearrangement field delivered one of the currently most popular measures in phylogenetic studies for related species. Here, BREAKPOINT MEDIAN, which is NP-complete already for three given species (whose genomes are represented as signed orderings), is the core basic problem. For the important special case of three species, approximation (ratio 7/6) and exact heuristic algorithms were developed. Here, we provide an exact, fixed-parameter algorithm with provable performance bounds. For instance, a breakpoint median for three signed orderings over nelements that causes at most d breakpoints can be computed in time O((2.15)(d).n). We show the algorithm's practical usefulness through experimental studies. In particular, we demonstrate that a simple implementation of our algorithm combined with a new tree construction heuristic allows for a new approach to breakpoint phylogeny, yielding evolutionary trees that are competitive in comparison with known results developed in a recent series of papers that use clever algorithm engineering methods.","file":"GrammNiedermeier_BreakpointMediansBreakpointPhylogenies_ECCB_2002.pdf:2002/GrammNiedermeier_BreakpointMediansBreakpointPhylogenies_ECCB_2002.pdf:PDF","keywords":"fpt","owner":"Sebastian","pmid":"12385994","timestamp":"2006.12.15","bibtex":"@Article{gramm02breakpoint,\n author = {Jens Gramm and Rolf Niedermeier},\n title = {Breakpoint medians and breakpoint phylogenies: A fixed-parameter approach.},\n journal = {Bioinformatics},\n year = {2002},\n volume = {18 Suppl 2},\n pages = {S128--S139},\n note = {Proc. of \\emph{European Conference on Computational Biology} (ECCB 2002)},\n abstract = {With breakpoint distance, the genome rearrangement field delivered one of the currently most popular measures in phylogenetic studies for related species. Here, BREAKPOINT MEDIAN, which is NP-complete already for three given species (whose genomes are represented as signed orderings), is the core basic problem. For the important special case of three species, approximation (ratio 7/6) and exact heuristic algorithms were developed. Here, we provide an exact, fixed-parameter algorithm with provable performance bounds. For instance, a breakpoint median for three signed orderings over nelements that causes at most d breakpoints can be computed in time O((2.15)(d).n). We show the algorithm's practical usefulness through experimental studies. In particular, we demonstrate that a simple implementation of our algorithm combined with a new tree construction heuristic allows for a new approach to breakpoint phylogeny, yielding evolutionary trees that are competitive in comparison with known results developed in a recent series of papers that use clever algorithm engineering methods.},\n file = {GrammNiedermeier_BreakpointMediansBreakpointPhylogenies_ECCB_2002.pdf:2002/GrammNiedermeier_BreakpointMediansBreakpointPhylogenies_ECCB_2002.pdf:PDF},\n keywords = {fpt},\n owner = {Sebastian},\n pmid = {12385994},\n timestamp = {2006.12.15},\n}\n\n","author_short":["Gramm, J.","Niedermeier, R."],"key":"gramm02breakpoint","id":"gramm02breakpoint","bibbaseid":"gramm-niedermeier-breakpointmediansandbreakpointphylogeniesafixedparameterapproach-2002","role":"author","urls":{},"keyword":["fpt"],"metadata":{"authorlinks":{}}},"bibtype":"article","biburl":"https://git.bio.informatik.uni-jena.de/fleisch/literature/raw/master/group-literature.bib","creationDate":"2019-11-19T16:50:42.006Z","downloads":0,"keywords":["fpt"],"search_terms":["breakpoint","medians","breakpoint","phylogenies","fixed","parameter","approach","gramm","niedermeier"],"title":"Breakpoint medians and breakpoint phylogenies: A fixed-parameter approach.","year":2002,"dataSources":["C5FtkvWWggFfMJTFX"]}