The SCJ Small Parsimony Problem for Weighted Gene Adjacencies

Area of Science:

• Comparative genomics
• Bioinformatics
• Computational biology

Background:

• Reconstructing ancestral gene orders is crucial in comparative genomics.
• Existing methods often focus on parsimony or scaffolding, aiming to reduce genome fragmentation.

Purpose of the Study:

• To develop an exact algorithm for the Small Parsimony Problem that integrates evolutionary cost with weighted ancestral gene adjacencies.
• To address the NP-hardness of this problem variant.

Main Methods:

• Introduced a novel objective function combining gene adjacency weights and the Single-Cut-or-Join (SCJ) evolutionary model.
• Developed a Fixed-Parameter Tractable algorithm based on Sankoff-Rousseau dynamic programming.
• Applied the algorithm to mammalian and bacterial genomic data.

Main Results:

• Demonstrated the NP-hardness of the weighted ancestral gene order reconstruction problem.
• The proposed algorithm effectively reduces fragmentation in reconstructed ancestral genomes.
• Incorporating adjacency weights significantly improves reconstruction accuracy.

Conclusions:

• The new algorithm offers an effective approach to reconstructing ancestral gene orders with reduced fragmentation.
• Weighted gene adjacencies, potentially derived from ancient DNA or probabilistic models, enhance ancestral genome reconstruction.
• The method provides a valuable tool for comparative genomics research.