一种基于分治的三维匹配问题DNA计算算法

 本文基于Aldeman-Lipton模型的生物操作与粘贴模型的解空间,提出一种三维匹配问题的DNA计算新模型;同时基于此模型和传统计算机中分治策略,提出一种求解三维匹配问题的DNA计算新算法.将提出的算法与已有文献结论的对比分析表明:本算法将穷举算法中的DNA链数从O(2ⁿ)减少至O(2^n/2)≈O(1.414ⁿ),同时生物操作数由O(n²)减少至O(15n+30q),测试试管数由所需的O(n)减少至O(1),最大链长由O(15n+45q)减少至O(15n/2+45q).因此,本算法理论上在试管级生化反应条件下能将求解三维匹配问题的规模从67(2⁶⁷≈10²²)提高到134(67×2=134).同时,与传统的穷举搜索算法相比,该算法具有高效的空间利用率及容错技术的优点.

A New DNA Computing's Algorithm for 3-Dimensional Matching Problem Based on Divide and Conquer Strategy

At present,it is how to decrease the DNA volume that plays an important role in the development of DNA computing.In this paper,for the objective to reduce the DNA volume of 3-Dimensional Matching Problem which is a famous NP-complete problem,an improved DNA computing model based on the operations in Adleman-Lipton's model and the solution space of the sticker-based model is put forward.Then,the divide and comquer is introduced into the DNA computing and a new DNA computing's algorithm is proposed.In a computer simulation,the DNA strands of maximum number required was O(1.414ⁿ),the time complexity was O(15×n+30×q),the test tube complesity was O(1) and the longest DNA strand was O(15n/2+45q).Hence,the scale of 3-Dimensional Matching Problem may be enlarged from 67 to 134.This new algorithm is highly space-efficient and error-tolerant compared to the conventional brute-force searching,and can be scaled-up to solve large and hard 3-Dimensional Matching Problem.By the approach,we can also show DNA computing's vast potentials for resolving NP problems.