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

Area of Science:

• Computational Biology
• Bioinformatics
• Genomics

Background:

• Breakpoint distance is a popular measure in phylogenetic studies for related species.
• The breakpoint median problem is central to genome rearrangement analysis but is NP-complete.
• Existing algorithms for three species include approximation and heuristic methods.

Purpose of the Study:

• To develop an exact, fixed-parameter algorithm for the breakpoint median problem.
• To provide provable performance bounds for the algorithm.
• To demonstrate the practical utility of the algorithm in breakpoint phylogeny.

Main Methods:

• Developed an exact, fixed-parameter algorithm for computing the breakpoint median.
• Analyzed the algorithm's time complexity: O((2.15)^d * n) for d breakpoints and n elements.
• Combined the algorithm with a novel tree construction heuristic for phylogenetic analysis.

Main Results:

• The algorithm computes breakpoint medians for three signed orderings with at most d breakpoints in O((2.15)^d * n) time.
• Experimental studies confirmed the algorithm's practical usefulness.
• The new approach to breakpoint phylogeny yielded competitive evolutionary trees.

Conclusions:

• The presented fixed-parameter algorithm offers an efficient and exact solution for the breakpoint median problem.
• This work advances breakpoint phylogeny by providing a practical and competitive method for constructing evolutionary trees.
• The algorithm's performance bounds and experimental validation highlight its significance in genome rearrangement studies.