Breakpoint medians and breakpoint phylogenies: a fixed-parameter approach.
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.
Gramm
Jens
J
Wilhelm-Schickard-Institut für Informatik, Universität Tübingen, Federic Republic of Germany.
Niedermeier
Rolf
R
D000465:Algorithms; D005075:Biological Evolution; D002874:Chromosome Mapping / Q000379:methods*; D003198:Computer Simulation; D015321:Gene Rearrangement; D008957:Models, Genetic; D010802:Phylogeny; D016415:Sequence Alignment / Q000379:methods*; D017422:Sequence Analysis, DNA / Q000379:methods*; D012689:Sequence Homology, Nucleic Acid