Linearization of Median Genomes Under the Double-Cut-and-Join-Indel Model

Area of Science:

• Computational Biology
• Bioinformatics
• Genomics

Background:

• The median genome problem aims to find a genome that minimizes evolutionary distance to a set of given genomes.
• Reconstructing a median genome with linear chromosomes is computationally intractable.
• Efficient algorithms exist for a relaxed version allowing circular chromosomes.

Purpose of the Study:

• To develop a method for constructing an approximate solution to the intractable median genome problem with linear chromosomes.
• To provide a bound on the approximation error of the proposed method.
• To gain insights into the combinatorial structure of genome transformations, particularly concerning circular chromosomes.

Main Methods:

• Proposing a novel method to derive an approximate linear median genome from a circular median genome solution.
• Analyzing and proving a bound on the approximation error of the proposed method.
• Investigating the combinatorial aspects of genome rearrangements leading to circular chromosomes.

Main Results:

• A method for constructing an approximate linear median genome from a circular median genome solution is presented.
• A theoretical bound on the approximation error of this method is established.
• The method offers new perspectives on the combinatorial structure of genome transformations and the emergence of circular chromosomes.

Conclusions:

• The proposed method provides a viable approach to approximate solutions for the linear median genome problem.
• The findings contribute to understanding the evolutionary processes involving circularization of chromosomes.
• This work bridges the gap between efficient solutions for circular genomes and the more complex linear genome reconstruction problem.