A fast and exact algorithm for the median of three problem: a graph decomposition approach

Area of Science:

• Computational biology
• Graph theory
• Bioinformatics

Background:

• Previous work demonstrated adequate subgraphs for decomposing breakpoint graphs, accelerating the median problem.
• The median problem is crucial in computational biology for phylogenetic tree reconstruction.

Purpose of the Study:

• To investigate properties of adequate subgraphs with rank 3 for the median of three problem.
• To develop and evaluate an efficient algorithm for solving the median of three problem.

Main Methods:

• Proving properties of adequate subgraphs with rank 3.
• Inventorying algorithms for simple adequate subgraphs.
• Incorporating simple adequate subgraphs into the ASMedian algorithm.

Main Results:

• Identified key properties of adequate subgraphs with rank 3.
• Developed the ASMedian algorithm by integrating simple adequate subgraphs.
• ASMedian achieved dramatic speedups on simulated data, solving instances with thousands of genes rapidly.

Conclusions:

• Adequate subgraphs offer significant performance improvements for the median of three problem.
• ASMedian is a highly efficient algorithm for solving the median of three problem, even for large-scale genomic data.