The median problems on linear multichromosomal genomes: graph representation and fast exact solutions

Area of Science:

• Computational Biology
• Bioinformatics
• Genomics

Background:

• The genome median problem is crucial for phylogenetic analysis but is NP-hard.
• Previous work provided solutions for circular genomes using decomposition.
• Extending these methods to linear multichromosomal genomes presents significant challenges.

Purpose of the Study:

• To extend exact median problem solutions to linear multichromosomal genomes.
• To address the multi-way capping problem in linear genome rearrangement.
• To develop an efficient algorithm for solving these complex genomic problems.

Main Methods:

• Representing the median problem using capped multiple breakpoint graphs.
• Extending adequate subgraphs to capped adequate subgraphs.
• Proving optimality-preserving decomposition theorems.
• Developing the exact ASMedian-linear algorithm for iterative subgraph detection and decomposition.

Main Results:

• The ASMedian-linear algorithm effectively solves the median and multi-way capping problems for linear genomes.
• The algorithm demonstrates rapid performance on simulated data with thousands of genes.
• Optimal or near-optimal solutions are achieved for median problems under reversal/HP distances.

Conclusions:

• The developed decomposition approach and ASMedian-linear algorithm provide efficient tools for linear genome rearrangement problems.
• This work advances phylogenetic analysis by enabling more accurate reconstruction of ancestral genomes.
• The algorithm offers a practical solution for complex genomic median and optimization tasks.