基于DNA计算模型的几个NP完全问题的研究
|
摘要
DNA计算,又称为生物分子计算,是基于生化反应的一种全新的计算模式。对于复杂的NP完全问题,DNA计算机与传统晶体管计算机相比,具有其无可比拟的优势,如:高度并行性、巨大的存储容量、超低的能耗和快的运行速度。因此,DNA计算方法及计算理论的研究对分子计算机的实现具有重要意义,近期的研究也表明,DNA计算在特定的复杂问题或领域里已显示出极大的潜力,并具有光明的应用前景。
1994年,美国南加州大学的Adleman教授用生化实验开创性地解决了七个顶点的有向哈密尔顿路径问题(Directed Hamilton Path Problem,DHPP)。之后,DNA计算迅速成为活跃的科学研究领域,有关DNA计算的科研工作也迅速在许多国家展开。研究的内容涉及DNA计算模型、一些NP问题的DNA算法、数据加密、智能控制、DNA数据存储、DNA计算的复杂性、分子高级语言、DNA计算方法与各种软科学的结合或集成等等。不但受跨学科研究所限,而且由于生物实验过程的复杂性,实验环境难以搭建,因此,虽然众多研究中已取得较为丰硕的成果,但目前的研究还是以理论研究居多。但仅在DNA计算的理论研究领域,就有许多经典的图论问题、组合优化问题、数学问题等可以用DNA计算方法来解决,即便有些问题已有DNA计算方法,但仍有可改进之处。
但是,研究DNA计算方法最终是为了研制出有应用价值的DNA计算机。所以,DNA计算中生物实验操作、实验装置、实验环境、理论与实践的联接与融合就显得尤为重要,这也应该是DNA计算领域里众多专家、学者进一步努力的方向。
粘贴模型和剪接模型是DNA计算中的两种最主要的模型。粘贴模型是一种通用计算机系统,该模型有着与剪接模型同样的计算能力,而且具有不需要延伸DNA链、不需要酶的参与以及材料可以重复利用等优点。因此,有关粘贴模型的研究开展得比较快,许多问题的粘贴DNA算法也相继被提出。
本文就是以DNA计算的粘贴模型为基础,解决了一些困难的NP完全问题,并对这些问题的算法进行了实验仿真。
(1)基于Adleman解决Hamilton问题的思路详细求解顶点的最小覆盖(Minimun Vertex Cover Problem,MVCP)问题。该算法首先生成了满足顶点覆盖的所有可满足解,然后在可满足解中直接分离出最小顶点覆盖的解,这样大大提高了实验的效率与分离解的准确性。
(2)基于DNA计算的粘贴模型,通过把逻辑演算问题转化为对应的开关网络图和Lipton模型的接触网络图,借鉴Lipton模型求解可满足性问题的方法解决了一个经典的逻辑演算问题,进一步开阔了DNA计算解决离散数学中各种问题的思路。
(3)粘贴系统是将Watson-Crick互补原理用于DNA计算的抽象的计算模型,是一种基于粘贴运算的语言生成器。基于粘贴系统将旅行商(TravalSalesman Problem,TSP)问题转化为求赋权图中权值最小的Hamilton圈问题,按照这一思路详细求解了此NP完全问题。同时,对问题编码进行了进一步完善。
在解决以上三个问题时,文中都给出了具体问题的实例模型、编码、算法的详细描述,并对TSP问题进行仿真试验得出问题的正确解,从而,说明了算法的可行性和有效性。
声明:由于DNA计算涉及生物实验,受实验环境所限,本文偏向理论研究,请诸位能予以谅解。
DNA computing, which is also called, is a completely new calculation model which is based on Biochemistry Reaction. DNA computer is much better than traditional transistor computer as for complex NP-complete problem, for example, highly parallelism, huge data storage, extraordinary low energy consume, quick run speed. Consequently the research of DNA computing methods and theory has great significance to the realization of molecular computer. Recent researches also show that DNA computing has the great potential and good prospect in the specific complex area.
In 1994, professor Adleman in South California University solved the Directed Hamilton Path with seven points (DHPP) Problem using biochemistry experiment. Form then on, DNA computing rapidly becoming the active scientific research field, and the research of DNA computing is also developed in many countries. The contents involved the DNA computing models, the algorithm some NP problems, data encryption, intelligence control, DNA data storage, the complexity of DNA computing, molecule high-level language, the combination or integration of DNA computing methord and all sorts of soft science and etc. Although a lot of the researches have already got plentiful achievements, most of them remained on theoretical degree Because researcher not only get the limitation of across mutil-subjet, but also the difficult build on experiment condition due to the complexity of biological experiment. Only in theoretical research field of DNA computing, there are many DNA algorithms of several classical problems on graph, combinatorics and mathematics. There are DNA algorithms of some problems, but still to be improved.
However, studying on DNA computing is to build the DNA computer of great application value. So, to DNA computing, experiment manipulation, experiment equipment, experiment condition and combination in theory and practice are of great importance, which is also the direction of further study.
Sticker model and splicing model are two of the important DNA computing models. Sticker model is a universal computer system. Peer computing capacity to splicing model, use of fixed-length DNA strands, free of enzymes and strands expanding, repeated use of materials caused researches on sticker model making a rapid development, and DNA algorithms of many problems were proposed, too.
The paper solved some difficult NP-complete problems, according to the sticker model of DNA computing, and simulated the algorithms of the experiment.
(1) A DNA algorithm based on Adleman model for Hamilton problems was proposed to solve Minimun Vertex Cover Problem in detail. At first, the algorithm produces all satifiable results of the SAT problem, then, right results are straightly separated among these results. In this way, the experiment efficiency and results accuracy are greatly advanced.
(2) To a classical logic calculus problem, using the ideal which Lipton solved the SAT problem, we proposed a DNA algorithm based on sticker model. By improved algorithm, problem is transformed corresponding open-close network graph and contact network graph. Further, thoughtway of solving Discrete Mathematic problems is broaded greatly by use of DNA computing.
(3) Sticker system is a abstract model which use the Watson-Crick complementary principle in DNA computing, it is also a language generator based on sticker calculation. Traval Salesman Problem was convert into a problem of seeking the Hamilton cilcle of the smallest weight in graph, this way solved the NP-complete problem and further improved the coding.
In solving the above problems, detailed model, coding and prescription of the methods are presented and correct answer of TSP are obtained through simulate experiment. Thus the feasibility and validity of the algorithm is proved.
Statement: Because DNA computing relate to biological experiment, this paper make emphases on theoretical research by the limitation of experiment environment. Please you make understanding.
1994年,美国南加州大学的Adleman教授用生化实验开创性地解决了七个顶点的有向哈密尔顿路径问题(Directed Hamilton Path Problem,DHPP)。之后,DNA计算迅速成为活跃的科学研究领域,有关DNA计算的科研工作也迅速在许多国家展开。研究的内容涉及DNA计算模型、一些NP问题的DNA算法、数据加密、智能控制、DNA数据存储、DNA计算的复杂性、分子高级语言、DNA计算方法与各种软科学的结合或集成等等。不但受跨学科研究所限,而且由于生物实验过程的复杂性,实验环境难以搭建,因此,虽然众多研究中已取得较为丰硕的成果,但目前的研究还是以理论研究居多。但仅在DNA计算的理论研究领域,就有许多经典的图论问题、组合优化问题、数学问题等可以用DNA计算方法来解决,即便有些问题已有DNA计算方法,但仍有可改进之处。
但是,研究DNA计算方法最终是为了研制出有应用价值的DNA计算机。所以,DNA计算中生物实验操作、实验装置、实验环境、理论与实践的联接与融合就显得尤为重要,这也应该是DNA计算领域里众多专家、学者进一步努力的方向。
粘贴模型和剪接模型是DNA计算中的两种最主要的模型。粘贴模型是一种通用计算机系统,该模型有着与剪接模型同样的计算能力,而且具有不需要延伸DNA链、不需要酶的参与以及材料可以重复利用等优点。因此,有关粘贴模型的研究开展得比较快,许多问题的粘贴DNA算法也相继被提出。
本文就是以DNA计算的粘贴模型为基础,解决了一些困难的NP完全问题,并对这些问题的算法进行了实验仿真。
(1)基于Adleman解决Hamilton问题的思路详细求解顶点的最小覆盖(Minimun Vertex Cover Problem,MVCP)问题。该算法首先生成了满足顶点覆盖的所有可满足解,然后在可满足解中直接分离出最小顶点覆盖的解,这样大大提高了实验的效率与分离解的准确性。
(2)基于DNA计算的粘贴模型,通过把逻辑演算问题转化为对应的开关网络图和Lipton模型的接触网络图,借鉴Lipton模型求解可满足性问题的方法解决了一个经典的逻辑演算问题,进一步开阔了DNA计算解决离散数学中各种问题的思路。
(3)粘贴系统是将Watson-Crick互补原理用于DNA计算的抽象的计算模型,是一种基于粘贴运算的语言生成器。基于粘贴系统将旅行商(TravalSalesman Problem,TSP)问题转化为求赋权图中权值最小的Hamilton圈问题,按照这一思路详细求解了此NP完全问题。同时,对问题编码进行了进一步完善。
在解决以上三个问题时,文中都给出了具体问题的实例模型、编码、算法的详细描述,并对TSP问题进行仿真试验得出问题的正确解,从而,说明了算法的可行性和有效性。
声明:由于DNA计算涉及生物实验,受实验环境所限,本文偏向理论研究,请诸位能予以谅解。
DNA computing, which is also called, is a completely new calculation model which is based on Biochemistry Reaction. DNA computer is much better than traditional transistor computer as for complex NP-complete problem, for example, highly parallelism, huge data storage, extraordinary low energy consume, quick run speed. Consequently the research of DNA computing methods and theory has great significance to the realization of molecular computer. Recent researches also show that DNA computing has the great potential and good prospect in the specific complex area.
In 1994, professor Adleman in South California University solved the Directed Hamilton Path with seven points (DHPP) Problem using biochemistry experiment. Form then on, DNA computing rapidly becoming the active scientific research field, and the research of DNA computing is also developed in many countries. The contents involved the DNA computing models, the algorithm some NP problems, data encryption, intelligence control, DNA data storage, the complexity of DNA computing, molecule high-level language, the combination or integration of DNA computing methord and all sorts of soft science and etc. Although a lot of the researches have already got plentiful achievements, most of them remained on theoretical degree Because researcher not only get the limitation of across mutil-subjet, but also the difficult build on experiment condition due to the complexity of biological experiment. Only in theoretical research field of DNA computing, there are many DNA algorithms of several classical problems on graph, combinatorics and mathematics. There are DNA algorithms of some problems, but still to be improved.
However, studying on DNA computing is to build the DNA computer of great application value. So, to DNA computing, experiment manipulation, experiment equipment, experiment condition and combination in theory and practice are of great importance, which is also the direction of further study.
Sticker model and splicing model are two of the important DNA computing models. Sticker model is a universal computer system. Peer computing capacity to splicing model, use of fixed-length DNA strands, free of enzymes and strands expanding, repeated use of materials caused researches on sticker model making a rapid development, and DNA algorithms of many problems were proposed, too.
The paper solved some difficult NP-complete problems, according to the sticker model of DNA computing, and simulated the algorithms of the experiment.
(1) A DNA algorithm based on Adleman model for Hamilton problems was proposed to solve Minimun Vertex Cover Problem in detail. At first, the algorithm produces all satifiable results of the SAT problem, then, right results are straightly separated among these results. In this way, the experiment efficiency and results accuracy are greatly advanced.
(2) To a classical logic calculus problem, using the ideal which Lipton solved the SAT problem, we proposed a DNA algorithm based on sticker model. By improved algorithm, problem is transformed corresponding open-close network graph and contact network graph. Further, thoughtway of solving Discrete Mathematic problems is broaded greatly by use of DNA computing.
(3) Sticker system is a abstract model which use the Watson-Crick complementary principle in DNA computing, it is also a language generator based on sticker calculation. Traval Salesman Problem was convert into a problem of seeking the Hamilton cilcle of the smallest weight in graph, this way solved the NP-complete problem and further improved the coding.
In solving the above problems, detailed model, coding and prescription of the methods are presented and correct answer of TSP are obtained through simulate experiment. Thus the feasibility and validity of the algorithm is proved.
Statement: Because DNA computing relate to biological experiment, this paper make emphases on theoretical research by the limitation of experiment environment. Please you make understanding.
引文
[1]李承祖,量子通信和量子计算机[M],国防科技大学出版社,2000,102-130
[2]许进,DNA计算与运筹学发展的新机遇《中国运筹学会第六届学术交流会论文集》(上卷)(主编:章祥荪,王建方,刘宝碇,刘德刚),Global-Link Publishing Company香港,2000:43-54(注:特邀大会主题报告)
[3]Lipton R.J,DNA Solution of Hard Computation Problems,Science,1995,268(4):542-545
[4]Adleman L.M,Molecular computation of solutions to combinatorial problems[J],Science,1994,266(5187),1021-1024
[5]石晓龙 许进,DNA计算与背包问题[J],计算机工程与应用,2003,27,44
[6]Lipton R J,DNA solution of hard computational problem[J],Science,1995,2 68,542-545
[7]许进等,DNA计算机原理、进展及难点(I):生物计算系统及其在图论中的应用,计算机学报,2003,26(1),1-11
[8]黄布毅,DNA计算中若干理论问题的研究[学位论文],2005,4-29
[9]J.萨姆布鲁克E.E弗里奇T.曼尼阿蒂斯等译,分子克隆实验指南(第二版),北京,科学出版社,1999
[10]Paun G,DNA computing based on splicing:Universality'results.Theoretical Computer Science,2000,231(2),275-296
[11]Gao,X.,Yo,P.,Keith,A.,Ragan,T.J.and Harris,T.K.(2003)Thermodynamically balanced inside-out (TBIO)PCR-based gene synthesis:a novel method of primer design for highfidelity assembly of longer gene sequences.Nucleic Acids Res,31,143
[12]Gibbons A,Algorithmic Graph Theory[M],Cambridge London,Cambridge University Press,1985
[13]肖绚 胡鸿豪,DNA计算模型发展分析[J],计算机应用,2004,24(9),123-126
[14]许进 王淑栋 潘林强(译),DNA计算一种新的计算模式[M],北京,清华大学出版社,2004
[15]李人厚 余文,关于DNA计算的基本原理与探讨,计算机学报,2001,24(9)972-978
[16]顾大鹏,孙野青,DNA分子计算机研究现状,哈尔滨工业大学学报,2005,37(8)
[17]董亚非 王淑栋 许进,DNA计算原理及系统分析,计算机工程与应用.2003,70-72
[18]丁建立 陈增强 袁著祉,DNA计算与 DNA计算机研究进展与展望,计算机科学,2003 vol.3019-22
[19]Wang Zhaocai Xiao Dongmei Li Wenxia,A DNA procedure for solving the shortest path problem,2006
[20]Wu Haoyang,An improved surface-based method for DNA computation,2001
[21]Qiu Zhiquan Frank Lu Mi,new approach to advance the DNA computing,2003
[22]Ji Youn Lee Soo-Yong Shinb Tai Hyun Park etc,Solving traveling salesman problems with DNA,2004
[23]曾垂省 闫玉华 陈晓明,DNA计算机原理、现状及发展[J],生物技术通报,2004
[24]许进 董亚非 魏小鹏,粘贴DNA计算机模型(Ⅰ):理论,科学通报,2004,49(3),568-573
[25]许进 李三平 董亚非等,粘贴DNA计算机模型(Ⅱ):应用,科学通报,2004,49(4),299-307
[26]Braich Ravinderjit S.Nickolas Chelyapov.Cliff Johnson.etal,Solution of a 20-variable 3-SAT problem on a DNA computer,Science,2002,296,499-502
[27]K.H.Zimmermann,Efficient DNA algorithms for NP-complete graph problems,Computer Physics Communications,2002,144(3),297-309
[28]CARLOC MALEY,DNA Computation:Theory,Practice and Prospects[J],Evolutionary Computation,1998,6(3),201-229
[29]董亚非 谭刚军 张社民,基于粘贴系统求解TSP问题,系统仿真学报,2005,17(6),1299-1302,1306
[30]洪龙,Hamilton圈问题的DNA算法[J],南京航空航天大学学报,2006,38(2),222-226
[31]高琳 许进,图的顶点着色问题的DNA算法[J],电子学报,2003,31(4),494-497
[32]王淑栋 许进 董亚非,图的最小顶点覆盖问题的面上DNA解法[J],小型微型计算机系统,2004,25(2)
[33]董亚非 张家秀 殷志祥,最小顶点覆盖问题的改进粘贴模型[J],电子与信息学报,2005,27(4)
[34]朱翔鸥 刘文斌 孙川等,基于可满足解空间的DNA算法-解决最小顶点覆盖问题[J],计算机工程与应用,2005,31,46-48
[35]董亚非,若干DNA计算粘贴模型的研究,[学位论文],2004,35-53
[36]王淑栋,四类DNA计算模型中一些理论与应用的研究,[学位论文],华中科技大学,2004,69-73
[37]Lia Dafa Lib Xiangrong Hongtao Huangc etc,Scalability of the surface-based DNA algorithm for 3-SAT,2006,96-98
[38]Qiu Zhiquan Frank Mi Lu,A new approach to advance the DNA computing,2003,177-189
[39]孙风芝 马占春 刘建群 丛惠敏,浅析离散数学在计算机科学中的应用[J],平顶山师专学报,2004,18(5),62-64
[40]张家秀 殷志祥,离散数学中的DNA计算[J],计算机工程与应用,2003,28,128-133
[41]Kari L Paun G Rozenberg G et al,DNA computing sticker systems and universality[J],Acta Informatica,1998,35,401-420
[42]Roweis S et al.A sticker-based model for DNA computation[J,Journal of Computational Biology,1998,(4):615-629
[43]Lipton Richard J,DNA Solution of Hard Computation Problems[J],Science,1995,268,583-585
[44]Zhang Jia-xiu,Hamilton Graph Based on DNA Computing[J],CHINESE QUARTERLY JOURNAL OF MATHEMATICS,2004,19(1),79-83
[45]刘文斌 王淑 许进,可满足(SAT)问题的几种DNA计算模型[J],小型微型计算机系统,2004,25(7),1321-1325
[46]殷志祥 许进 潘林强,DNA计算在图论中的应用[J],自然科学进展,2003(5),462-465
[47]殷志祥 刘文斌 董亚非,DNA计算在组合优化中的应用及其复杂性[J],系统工程与电子技术,2003,25(4),427-431
[48]周康 许进,最小顶点覆盖问题的闭环DNA算法[J],计算机工程与应用,2006,42(20),7-9
[49]刘向荣 刘文斌 许进,激光诱导荧光技术在DNA计算输出中的应用[J],计算机工程与应用.2005,41(1),38-42.
[50]潘林强 董亚非 许进等,求解节点网络的DNA算法,华中科技大学学报(自然科学版),Vol.31.No.3,Mar.2003,69-71
[51]费培之,图和网络及其应用[M],四川,四川大学出版社,1996,102-110
[52]刘文斌,DNA计算中的编码问题及模型研究.[学位论文],华中科技大学,2003,56-69
[53]王淑栋等,图的最小顶点覆盖问题的质粒DNA计算模型[J],Huazhong Univ.of Sci.＆Tech.(Nature Science Edition),Vol.32,No.11,Nov,2004,59-61
[54]Gao L.Xu J,DNA Solution of Vertex Cover Problem Based on Sticker Model,Chinese Journal of Electronics,2002,Ⅱ(2),280-284
[55]Natasa Jonoska,Trends in Computing with DNA[J],Comput.Sci.& Technol,Jan,2004,Vol.19,No.1
[56]徐士良,数值分析与算法[M],机械工业出版社,2003,289-301
[57]王晓东,算法设计与分析[M],消华大学出版社,2003,314
[58]周康 刘文斌 许进,TSP的DNA算法[J],系统工程与电子技术,2007,29(2),316-319
[59]韩爱丽 朱大铭,基于一种新的边权编码方案的中国邮递员问题的DNA计算模型[J],计算机研究与发展,2007,44(6),1053-1062
[60]王伟 殷忠祥,基于粘贴系统的有向哈密顿路问题分析[J],计算机工程与应用,2007,43(26)
[61]王兆才 肖冬梅 贺林,旅行商问题的DNA算法[J],计算机工程与应用。2006.30,81-83
[62]周康 强小利 周小军,求解TSP算法,计算机工程与应用[J],2007,43(29)
[63]马莹,图论中的DNA计算,计算机与数字工程[J],2007,35(8),100-102
[64]殷志祥 张家秀,图论中的DNA计算模型,系统工程与电子技术[J],2007,29(7),1159-1163
[65]马季兰 杨玉星 孙承意,粘贴DNA模型的多极分离技术及其应用[J],计算机工程与设计,2007,28(13),3039-3041
[66]周康 许进,最小顶点覆盖问题的闭环DNA算法[J],计算机工程与应用,2006,20,7-9,28
[2]许进,DNA计算与运筹学发展的新机遇《中国运筹学会第六届学术交流会论文集》(上卷)(主编:章祥荪,王建方,刘宝碇,刘德刚),Global-Link Publishing Company香港,2000:43-54(注:特邀大会主题报告)
[3]Lipton R.J,DNA Solution of Hard Computation Problems,Science,1995,268(4):542-545
[4]Adleman L.M,Molecular computation of solutions to combinatorial problems[J],Science,1994,266(5187),1021-1024
[5]石晓龙 许进,DNA计算与背包问题[J],计算机工程与应用,2003,27,44
[6]Lipton R J,DNA solution of hard computational problem[J],Science,1995,2 68,542-545
[7]许进等,DNA计算机原理、进展及难点(I):生物计算系统及其在图论中的应用,计算机学报,2003,26(1),1-11
[8]黄布毅,DNA计算中若干理论问题的研究[学位论文],2005,4-29
[9]J.萨姆布鲁克E.E弗里奇T.曼尼阿蒂斯等译,分子克隆实验指南(第二版),北京,科学出版社,1999
[10]Paun G,DNA computing based on splicing:Universality'results.Theoretical Computer Science,2000,231(2),275-296
[11]Gao,X.,Yo,P.,Keith,A.,Ragan,T.J.and Harris,T.K.(2003)Thermodynamically balanced inside-out (TBIO)PCR-based gene synthesis:a novel method of primer design for highfidelity assembly of longer gene sequences.Nucleic Acids Res,31,143
[12]Gibbons A,Algorithmic Graph Theory[M],Cambridge London,Cambridge University Press,1985
[13]肖绚 胡鸿豪,DNA计算模型发展分析[J],计算机应用,2004,24(9),123-126
[14]许进 王淑栋 潘林强(译),DNA计算一种新的计算模式[M],北京,清华大学出版社,2004
[15]李人厚 余文,关于DNA计算的基本原理与探讨,计算机学报,2001,24(9)972-978
[16]顾大鹏,孙野青,DNA分子计算机研究现状,哈尔滨工业大学学报,2005,37(8)
[17]董亚非 王淑栋 许进,DNA计算原理及系统分析,计算机工程与应用.2003,70-72
[18]丁建立 陈增强 袁著祉,DNA计算与 DNA计算机研究进展与展望,计算机科学,2003 vol.3019-22
[19]Wang Zhaocai Xiao Dongmei Li Wenxia,A DNA procedure for solving the shortest path problem,2006
[20]Wu Haoyang,An improved surface-based method for DNA computation,2001
[21]Qiu Zhiquan Frank Lu Mi,new approach to advance the DNA computing,2003
[22]Ji Youn Lee Soo-Yong Shinb Tai Hyun Park etc,Solving traveling salesman problems with DNA,2004
[23]曾垂省 闫玉华 陈晓明,DNA计算机原理、现状及发展[J],生物技术通报,2004
[24]许进 董亚非 魏小鹏,粘贴DNA计算机模型(Ⅰ):理论,科学通报,2004,49(3),568-573
[25]许进 李三平 董亚非等,粘贴DNA计算机模型(Ⅱ):应用,科学通报,2004,49(4),299-307
[26]Braich Ravinderjit S.Nickolas Chelyapov.Cliff Johnson.etal,Solution of a 20-variable 3-SAT problem on a DNA computer,Science,2002,296,499-502
[27]K.H.Zimmermann,Efficient DNA algorithms for NP-complete graph problems,Computer Physics Communications,2002,144(3),297-309
[28]CARLOC MALEY,DNA Computation:Theory,Practice and Prospects[J],Evolutionary Computation,1998,6(3),201-229
[29]董亚非 谭刚军 张社民,基于粘贴系统求解TSP问题,系统仿真学报,2005,17(6),1299-1302,1306
[30]洪龙,Hamilton圈问题的DNA算法[J],南京航空航天大学学报,2006,38(2),222-226
[31]高琳 许进,图的顶点着色问题的DNA算法[J],电子学报,2003,31(4),494-497
[32]王淑栋 许进 董亚非,图的最小顶点覆盖问题的面上DNA解法[J],小型微型计算机系统,2004,25(2)
[33]董亚非 张家秀 殷志祥,最小顶点覆盖问题的改进粘贴模型[J],电子与信息学报,2005,27(4)
[34]朱翔鸥 刘文斌 孙川等,基于可满足解空间的DNA算法-解决最小顶点覆盖问题[J],计算机工程与应用,2005,31,46-48
[35]董亚非,若干DNA计算粘贴模型的研究,[学位论文],2004,35-53
[36]王淑栋,四类DNA计算模型中一些理论与应用的研究,[学位论文],华中科技大学,2004,69-73
[37]Lia Dafa Lib Xiangrong Hongtao Huangc etc,Scalability of the surface-based DNA algorithm for 3-SAT,2006,96-98
[38]Qiu Zhiquan Frank Mi Lu,A new approach to advance the DNA computing,2003,177-189
[39]孙风芝 马占春 刘建群 丛惠敏,浅析离散数学在计算机科学中的应用[J],平顶山师专学报,2004,18(5),62-64
[40]张家秀 殷志祥,离散数学中的DNA计算[J],计算机工程与应用,2003,28,128-133
[41]Kari L Paun G Rozenberg G et al,DNA computing sticker systems and universality[J],Acta Informatica,1998,35,401-420
[42]Roweis S et al.A sticker-based model for DNA computation[J,Journal of Computational Biology,1998,(4):615-629
[43]Lipton Richard J,DNA Solution of Hard Computation Problems[J],Science,1995,268,583-585
[44]Zhang Jia-xiu,Hamilton Graph Based on DNA Computing[J],CHINESE QUARTERLY JOURNAL OF MATHEMATICS,2004,19(1),79-83
[45]刘文斌 王淑 许进,可满足(SAT)问题的几种DNA计算模型[J],小型微型计算机系统,2004,25(7),1321-1325
[46]殷志祥 许进 潘林强,DNA计算在图论中的应用[J],自然科学进展,2003(5),462-465
[47]殷志祥 刘文斌 董亚非,DNA计算在组合优化中的应用及其复杂性[J],系统工程与电子技术,2003,25(4),427-431
[48]周康 许进,最小顶点覆盖问题的闭环DNA算法[J],计算机工程与应用,2006,42(20),7-9
[49]刘向荣 刘文斌 许进,激光诱导荧光技术在DNA计算输出中的应用[J],计算机工程与应用.2005,41(1),38-42.
[50]潘林强 董亚非 许进等,求解节点网络的DNA算法,华中科技大学学报(自然科学版),Vol.31.No.3,Mar.2003,69-71
[51]费培之,图和网络及其应用[M],四川,四川大学出版社,1996,102-110
[52]刘文斌,DNA计算中的编码问题及模型研究.[学位论文],华中科技大学,2003,56-69
[53]王淑栋等,图的最小顶点覆盖问题的质粒DNA计算模型[J],Huazhong Univ.of Sci.＆Tech.(Nature Science Edition),Vol.32,No.11,Nov,2004,59-61
[54]Gao L.Xu J,DNA Solution of Vertex Cover Problem Based on Sticker Model,Chinese Journal of Electronics,2002,Ⅱ(2),280-284
[55]Natasa Jonoska,Trends in Computing with DNA[J],Comput.Sci.& Technol,Jan,2004,Vol.19,No.1
[56]徐士良,数值分析与算法[M],机械工业出版社,2003,289-301
[57]王晓东,算法设计与分析[M],消华大学出版社,2003,314
[58]周康 刘文斌 许进,TSP的DNA算法[J],系统工程与电子技术,2007,29(2),316-319
[59]韩爱丽 朱大铭,基于一种新的边权编码方案的中国邮递员问题的DNA计算模型[J],计算机研究与发展,2007,44(6),1053-1062
[60]王伟 殷忠祥,基于粘贴系统的有向哈密顿路问题分析[J],计算机工程与应用,2007,43(26)
[61]王兆才 肖冬梅 贺林,旅行商问题的DNA算法[J],计算机工程与应用。2006.30,81-83
[62]周康 强小利 周小军,求解TSP算法,计算机工程与应用[J],2007,43(29)
[63]马莹,图论中的DNA计算,计算机与数字工程[J],2007,35(8),100-102
[64]殷志祥 张家秀,图论中的DNA计算模型,系统工程与电子技术[J],2007,29(7),1159-1163
[65]马季兰 杨玉星 孙承意,粘贴DNA模型的多极分离技术及其应用[J],计算机工程与设计,2007,28(13),3039-3041
[66]周康 许进,最小顶点覆盖问题的闭环DNA算法[J],计算机工程与应用,2006,20,7-9,28