Algorithms and Hardness for Scaffold Filling to Maximize Increased Duo-Preservations

Area of Science:

• Genomics
• Bioinformatics
• Computational Biology

Background:

• Scaffold filling is essential for DNA assembly, aiming to reconstruct complete genomes from fragmented sequences.
• Existing genome comparison methods struggle with gene duplications, necessitating more precise similarity measurements.

Purpose of the Study:

• To introduce and analyze the problem of scaffold filling to maximize increased duo-preservations (SF-MIDP).
• To investigate the computational complexity of SF-MIDP and develop approximation algorithms.

Main Methods:

• Utilizing duo-preservation, a metric complementary to common string partition, for genome comparison.
• Analyzing SF-MIDP for both simple block-matching and general cases.
• Developing and evaluating approximation algorithms for SF-MIDP.

Main Results:

• SF-MIDP is solvable in linear time for block-matched scaffolds.
• The general SF-MIDP problem is MAX SNP-complete and cannot be approximated within a factor of [Formula: see text].
• A factor 2 approximation algorithm was developed, followed by an improved greedy algorithm with a factor of [Formula: see text].

Conclusions:

• Duo-preservation offers a novel approach for measuring genome similarity, particularly in the presence of gene duplications.
• Efficient approximation algorithms are crucial for tackling the computationally challenging SF-MIDP problem in practical genome assembly.