Linearization of ancestral multichromosomal genomes.

Area of Science:

• Computational Biology
• Bioinformatics
• Genomics

Background:

• Ancestral genome reconstruction often relies on binary matrices and the Consecutive-Ones Property (C1P).
• The Linearization Problem, aiming to find maximum weight row subsets with C1P, is generally intractable for simple genome models (linear or single circular chromosome).

Purpose of the Study:

• To explore a relaxed version of the Linearization Problem allowing for ancestral genomes with multiple linear or circular chromosomes.
• To determine the computational complexity of this relaxed problem and establish tractability boundaries.

Main Methods:

• Reduction of the relaxed Linearization Problem for binary matrices of degree two to a matching problem.
• Analysis of complexity for matrices with row degrees 2 and 3 without multiplicity or weights.

Main Results:

• The relaxed Linearization Problem is polynomially solvable for binary matrices of degree two (representing adjacencies), even with bounded column multiplicity (duplicated genes).
• The problem becomes NP-complete for matrices with row degrees 2 and 3, without multiplicity and weights, defining sharp tractability limits.

Conclusions:

• Relaxing the genome definition transforms an intractable problem into a tractable one, similar to the breakpoint median problem.
• The developed algorithms are applicable to biological contexts like bacterial genomes with multiple replicons and can serve as heuristics for harder problem variants.
• This research enhances the understanding of linearization techniques in ancestral genome structure inference.