DDmap: a MATLAB package for the double digest problem using multiple genetic operators.

Area of Science:

• Computational Biology
• Bioinformatics
• Genomics

Background:

• The double digest problem (DDP) is a critical NP-complete challenge in computational biology for DNA physical mapping.
• Existing algorithms for DDP are insufficient for fully resolving this complex problem.

Purpose of the Study:

• To introduce DDmap, an open-source MATLAB package designed to solve the DDP.
• To present a novel genetic algorithm for optimizing DDP solutions.
• To offer an approximate method for intractable DDP instances.

Main Methods:

• Development of DDmap, a MATLAB package implementing a novel genetic algorithm.
• Integration of six genetic operators to enhance solution searching.
• Application of a scaling-rounding-adjusting process for approximate solutions.

Main Results:

• DDmap achieves exact solutions for typical DDP instances within approximately one second.
• The performance of DDmap was validated on a standard DDP dataset.
• An explicit depiction of exact solutions for DDP instances was provided.

Conclusions:

• DDmap offers a rapid and effective solution for the DDP in computational biology.
• Fragment length significantly impacts the efficacy of genetic algorithms in DDP.
• Accompanying Maple code visualizes DDP solutions using nested pie charts.