基于自组装纳米颗粒探针的最小顶点覆盖问题的dna计算模型

《基于自组装纳米颗粒探针的最小顶点覆盖问题的dna计算模型》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、基于自组装纳米颗粒探针的最小顶点覆盖问题的DNA计算模型麵艳殿志禅赵鑫月安徽理工大学数学与大勤DNA自组装技术为DNA计算的发展带来丫一些新的启发。目前，解决各种NP完全问题的方法有多种多样的计算模型，其中有些是非常有用的，可以解决复杂的NP完全问题。在本文中，在自组装纳米颗粒探针的基础上，介绍了关于最小顶点覆盖问题的一种新的DNA计算模型。将给定问题的变量0或1所有可能的组合，编码在自组装纳米探针的识别区，通过靶序列的杂交来判断其可行解。相对于传统的DNA计算模型，该模型具有方便、灵敏、稳定性高的优点。

2、关键词：DNA计算;自组装;纳米颗粒;最小顶点覆盖问题;基金：国家自然科学基金项目“基于分子信标微流控芯片的大数据存储与挖掘”(61702008):国家自然科学基金项目“DNA自组装模型在生物传感器设计中的研究与探索”(61672001)DNAComputingModelBasedonSelf-assembledNano-particleProbesSolvingtheMinimumVertexCoverageProblemGONGCheng-yanYINZhi-xiangZHAOXin-yueMathe

3、maXicsandBigDataInstitute，AnhuiUniversityofScienceandTechnology;Abstract：DNAself-assemblytechnologyhasbroughtsomenewinsightsintothedevelopmentofDNAcomputing.Atpresent,thereareavarietyofcomputationalmodelsforsolvingvariousNP—completeproblems,someofwhichare

4、veryusefulandcansolvecomplexNP-completeproblems.Inthispaper,anewDNAcomputingmodelwithminimalvertexcoverageproblemisintroducedonthebasisofself-assemblednano-particleprobes.Allthepossiblecombinationsofvariables0or1ofthegivenproblemareencodedintherecognition

5、regionoftheself-assemblednano-particleprobes,andthefeasiblesolutionisjudgedbythehybridizationofthetargetsequence.ComparedwiththetraditionalDNAcalculationmodel,themodelisconvenient,sensitiveandstable.Keyword：DNAcomputing;self-assembled;nano-particle;minimu

6、mvertexcoverageproblem;自从Adieman在哈密尔顿路径问题上的开创性I:作以来，基丁•DNA的计算领域已经有了许多研宄成果。采用DNA计算方法可用来解决许多组合优化问题，比如可满足问题m、最大团问题m、最大独立集问题m等。最小顶点覆盖（MVC）问题出现在各种重要成用中，包括计算生物化学中的多个序列比对、信息检索和调度问题等，探索一种更有效的解决最小顶点覆盖问题的方法有实际意义。2004年，高林、许进给出了解决最小顶点覆盖问题的DNA分子算法位1;2006年，周康、许进给出了解决最小

7、顶点覆盖问题的闭环DNA算法£61；同年，X.Xu和J.Maxw给出了解决最小顶点覆盖问题的模拟退火算法121;2008年，宁爱兵等给出了解决最小顶点覆盖问题的快速降解算法M;2010年，金婷婷等给出丫解决最小顶点覆盖问题的竞争决策算法M;2011年，ZhangX等用三维自组装模型解决最小顶点覆盖问题等0虹。基于以上研宄背景，FeiLi等在自组装纳米颗粒探针的基础上提出了解决0-1规划问题和SAT问题的新的DNA计算模型［11-12］，也是第一次将纳米颗粒与寡聚核卄酸结合到DNA计算模型中。本文在此DNA

8、计算模型基础上探讨最小顶点覆盖问题。1图的最小顶点覆盖问题1.1图的最小顶点覆盖定义基本定义:给定一个简单无向图G=（V，E），K是顶点集V的一个子集，并且每条边都至少有一个顶点在K中，那么称K是图G的一个顶点覆盖。如果G不存在覆盖K’使得

9、K’

10、〈

11、K

12、，那么覆盖K称为G的最小顶点覆盖。简而言之，图的最小顶点覆盖是指在给定的图屮找到一个顶点最小集，使得其能覆盖给定的图的所有边。对于任意一个有n个顶点、m条边的无向图G=（V,