Heuristics for the inversion median problem

Area of Science:

• Genomics
• Phylogenetics
• Computational Biology

Background:

• Genome rearrangements are crucial for phylogenetics and comparative genomics.
• The median problem, finding a median genome from three given genomes, is fundamental.
• Existing heuristics for the inversion median problem, like MGR, have limitations.

Purpose of the Study:

• To develop a unifying framework for median heuristics.
• To introduce a novel, highly efficient heuristic for the inversion median problem.
• To address the computational bottleneck in whole-genome comparative studies.

Main Methods:

• Developed a unifying framework to analyze and order existing median heuristics.
• Introduced a new heuristic (ASM) that leverages input data throughout computation.
• Conducted extensive experiments to compare ASM with existing methods.

Main Results:

• The new heuristic, ASM, demonstrates superior accuracy and significantly faster running times compared to existing methods.
• ASM typically yields solutions within 1% of optimal.
• ASM efficiently handles large genomes (25,000 genes) in seconds to minutes, unlike MGR which can take days for smaller datasets.

Conclusions:

• ASM effectively resolves the computational challenges associated with finding inversion medians.
• The new heuristic provides near-optimal solutions rapidly, even for the largest genomes.
• This advancement facilitates more efficient whole-genome comparative studies.