DNA计算模型及应用综述.doc

《DNA计算模型及应用综述.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、DNA计算模型及应用综述摘要：自从Adieman博士最早利用DNA计算成功求解了7个顶点有向图的Ham订ton问题以来，DNA计算［1］被引入多个研究领域，成为当今科技发展的热点之一。首先介绍DNA计算的基本原理及编码方法，其次阐述了DNA计算的主要模型，再次总结了国内外研究学者应用DNA计算解决的实际问题，最后列举了DNA计算改进的相关方向。关键词：DNA计算；模型；NP完全问题；智能算法中图分类号：TP301.4文献标识码：ADoi：10.3969/j.issn.1003-6970.2012.05.056TheModelsandAppl

2、icationsofDNAComputingBalXue(ShandongNormalUniversityCollegeofmanagementscienceandEngineering,Jinan250014,China)[Abstrac]SinceDr.ad1emanusedDNacomputingtoachieveHPPwithsevenverticessuccessfully,DNacomputinghasbeenbroughtinvariousresearchareasandbecomeoneofthefocusesofscien

3、tificdevelopment.Firstly,thebasicprinciplesandcodingmethodsareintroduced,followingwiththemainmodelsofit.Inaddition,wesummeduptheapplicationsofDNacomputingtosolvepracticalproblems,finally,severalimproveddirectionsarelisted.[Keywords]DNacomputing；Model；theNP-completeproblem；

4、Intelligentalgorithm1DNA计算简介1.1DNA计算原理DNA是一种由许多脱氧核昔酸分子连接而成的高分子化合物，其中脱氧核昔酸由脱氧核糖、磷酸和含氮碱基三部分组成。因为碱基有腺嗥吟A、鸟嗥吟G、胸腺13密噪T和胞13密喘C四种类型，所以与之对应的核昔酸也有四种表现形式。DNA计算的基本原理是把需要运算的对象映射成DNA分子链,在生物酶的作用下生成初始数据池，然后按照一定的规则将原始问题高度并行地映射成DNA分子链的可控的生化过程，最后利用现代分子生物技术[2-9]获得最终运算结果[10]o1.2DNA编码方法Baum于1

5、996年提出了降低DNA序列间相似度的假设，随后Garzon等人定义了DNA计算中的编码问题。DNA编码方法主要包括模板-映射方法、最小长度子串方法和随机搜索方法，其中模板-映射方法是由Wisconsin大学的Frutos等人提出的，2003年，刘文斌在该方法的基础上提出了模板框的概念；Feldkamp等人提出了一种最小长度子串评价方法，通过限制子序列出现的次数降低了编码之间的相似程度；2003年，Tulpant提出了随机搜索编码方法，采用随机方式生成DNA编码解空间，然后根据约束条件筛选出解空间中较好的DNA编码序列。1DNA计算模型1.

6、1基于理论研究的DNA计算模型1996年，Roweis提出一种基于分子操作和随机访问内存的DNA计算粘贴模型，在运算过程中不需要酶的作用和DNA链的延伸，主要有合并、分离、设置和清除四种基本操作。随后，Kari等人在粘贴模型的基础上提出了粘贴系统的概念，由Paun等人[3,7,11]将其推广到更加普遍的形式上。2004年，许进等人对粘贴模型给予了更为详细的讨论。1987年，Head在利用形式语言对DNA序列进行分析的基础上提出了剪接系统的概念[1,3,7],Paun等人对该系统的通用性、计算能力和剪接运算等方面进行了详细的讨论[3,7,12

7、]o2001年，Benenson等人利用剪接系统研制出一台具有编程能力的有穷自动机，并说明了剪接系统是计算気备的。插入/删除模型是建立在上下文插入和删除基础上的抽象模型[3,4,11],Paun等人于1998年利用上下文插入文法描述了递归可列语言，2002年，Takahara在第8届国际DNA计算机会议上阐述了插入/删除系统的计算能力。k-臂模型是1999年由Jonoska等人提出的一种DNA计算模型，Seeman等人的研究结果表明3-臂和4-臂DNA分子是相当稳定的，而且k-臂DNA分子的3'端一般为单链延伸。发夹模型是通过巧妙的DNA编

8、码，使非可行解的DNA链在生化反应中形成发夹结构，通过DNA分子中BSTNI内切酶的识别位来清除这些发夹结构。2000年，Sakatomo等人利用该模型建立了一种求解可满足性问题