DDmap：一个使用多种遗传算子的双酶切问题的 MATLAB 包。

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

机构信息

State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications, 10 West Tucheng Road, Haidian District, Beijing, 100876, China.

School of Computer Science, Communication University of China, 1 East of Dingfuzhuang Street, Chaoyang District, Beijing, 100024, China.

出版信息

BMC Bioinformatics. 2019 Jun 18;20(1):348. doi: 10.1186/s12859-019-2862-x.

DOI:10.1186/s12859-019-2862-x

PMID:31215408

原文链接:https://pmc.ncbi.nlm.nih.gov/articles/PMC6582610/

Abstract

BACKGROUND

In computational biology, the physical mapping of DNA is a key problem. We know that the double digest problem (DDP) is NP-complete. Many algorithms have been proposed for solving the DDP, although it is still far from being resolved.

RESULTS

We present DDmap, an open-source MATLAB package for solving the DDP, based on a newly designed genetic algorithm that combines six genetic operators in searching for optimal solutions. We test the performance of DDmap by using a typical DDP dataset, and we depict exact solutions to these DDP instances in an explicit manner. In addition, we propose an approximate method for solving some hard DDP scenarios via a scaling-rounding-adjusting process.

CONCLUSIONS

For typical DDP test instances, DDmap finds exact solutions within approximately 1 s. Based on our simulations on 1000 random DDP instances by using DDmap, we find that the maximum length of the combining fragments has observable effects towards genetic algorithms for solving the DDP problem. In addition, a Maple source code for illustrating DDP solutions as nested pie charts is also included.

摘要

背景

在计算生物学中，DNA 的物理作图是一个关键问题。我们知道双酶切问题（DDP）是 NP 完全问题。虽然已经提出了许多用于解决 DDP 的算法，但它仍然远未得到解决。

结果

我们提出了 DDmap，这是一个用于解决 DDP 的开源 MATLAB 软件包，它基于一种新设计的遗传算法，该算法在搜索最优解时结合了六个遗传算子。我们使用典型的 DDP 数据集来测试 DDmap 的性能，并以显式的方式描绘这些 DDP 实例的精确解。此外，我们还提出了一种通过缩放-舍入-调整过程来解决某些困难 DDP 场景的近似方法。