计算科学的新领域：DNA计算（Ⅲ）

DNA计算是应用分子生物技术进行计算的新方法.从理论上研究DNA计算方法，有利于推动理论计算科学的发展.本系列文章应用形式语言及自动机理论技术，系统地探讨了DNA分子的可计算性及其计算能力.本文主要介绍DNA剪接计算模型的文法结构和剪接计算方法，探讨了不同DNA剪接计算模型的计算能力，证明了所有图灵机可计算的函数理论上都可以通过DNA剪接计算模型来计算.     

信息安全中的DNA编码技术

DNA计算是一种模拟生物分子的结构并借助于分子生物技术进行计算的新模式。它引入了崭新的数据结构和计算方法,为解决NP完全问题提供了全新的途径。用DNA分子作为信息载体,以实现数据隐藏、认证、加密等安全技术。本文借鉴生物DNA的表达方式,定义了用户DNA、文件DNA的串结构,从而提高系统中信息安全控制的可靠性。     

DNA计算原理及系统分析

DNA计算是一种模拟生物分子DNA的结构并借助于分子生物技术进行计算的新方法,它开创了以化学反应作为计算工具的先例,具有广阔的应用前景。DNA计算的两个主要特点是计算的高度并行性和巨大的信息存储容量。该文简要介绍了DNA计算的原理及其数学计算的基本思想;对DNA计算的特点及其系统进行了分析。比较了DNA计算机与图灵机的异同;最后对DNA计算的发展前景进行展望。     

计算科学的新领域：DNA计算（Ⅰ）

DNA计算是应用分子生物技术进行计算的新方法。从理论上研究DNA计算方法，有利于推动理论计算科学的发展。本系列文章应用形式语言及自动机理论技术，系统地探讨了DNA分子的可计算性及其计算能力。本文主要介绍常用DNA分子操作方法，并根据DNA分子的结构及特点，给出了DNA分子的形式化描述。     

DNA计算机原理、进展及难点(Ⅳ):论DNA计算机模型

在DNA计算机研究中,所建模型的好坏直接影响着DNA计算中诸多问题,如编码的难易程度、整个生物操作或生化反应的设计、解空间的大小、计算时间多少、应用范围以及通用性的程度等.如何建立快速的、功能强的、具有一定通用性的DNA计算机模型,是从事DNA计算机研究者一直关注与感兴趣的难题.为此,该文将主要围绕着DNA计算机的模型建立展开讨论,重点讨论10年来所建立起来的一些主要模型.共分为三种类型:第一种是利用DNA分子结构与特性所建立起来的几种主要模型;第二种是利用生物操作方式所建立的三种模型:试管型、表面型与芯片型;第三种是所谓的DNA计算机模型.文中讨论了这些模型的基本原理、功能、优缺点以及应用的研究进展等.最后,对DNA计算机模型研究中的难点进行了分析,并给出了相应的解决思路.     

计算科学的新领域：DNA计算（Ⅱ）

DNA计算是应用分子生物技术进行计算的新方法。从理论上研究DNA计算方法，有利于推动理论计算科学的发展。本系列文章应用形式语言及自动机理论技术，系统地探讨了DNA分子的可计算性及其计算能力。本文主要介绍DNA分子粘接计算模型的文法结构和计算方法，探讨了不同粘接计算模型的计算能力，并证明了DNA有穷自动机与正规文法的等价性。     

图论中的DNA计算

DNA计算是一种模拟生物分子DNA结构并借助分子生物技术进行计算的新方法,其高度并行性和巨大的信息存储量为解决NP-完全问题提供全新的途径.介绍DNA计算的基本原理,详细介绍哈密顿图的DNA算法以及图着色问题的表面DNA计算,最后介绍DNA计算在图论中的进展以及DNA计算存在的问题.     

DNA计算中的信息安全技术

DNA计算是一种模拟生物分子的结构并借助于分子生物技术进行计算的新模式。它引入了崭新的数据结构和计算方法,为解决NP完全问题提供了全新的途径。由于DNA计算具有信息处理的高并行性、低能耗及高存储密度等优点,对传统的基于计算安全的密码体系提出了挑战。DNA密码便是近年来伴随着DNA计算的研究而出现的密码学新领域。用DNA分子作为信息载体,以实现数据隐藏、认证、加密等安全技术。在简要回顾DNA计算原理的基础上,详细分析了基于DNA的一次一密方案以及Boneh用DNA计算机破解DES的方法;最后探讨在DNA计算中的信息安全技术。     

DNA密码研究现状及展望

密码学作为信息安全的重点,一直以来都是讨论的热点。DNA分子强大的存储能力以及DNA分子计算的超低能耗和较快的并行处理速度,使DNA分子计算迅速受到广泛关注。DNA分子计算涉及生物、计算机、数学等领域,目前已出现许多DNA分子计算的研究方向。特别是在密码模型研究方面,利用DNA分子计算能力破解传统密码系统,结合新技术与现有技术,在传统密码系统的基础上形成更加可靠稳定的新密码系统,这给现代密码系统带来了机遇和挑战。文章描述了利用DNA分子构造计算模型对DES、RSA、NTRU等传统密码机制进行破解,结合一次性密码本等密码原理提出了新的加密解密模型,总结了当前DNA密码研究存在的不足,并展望了其在信息安全领域的发展前景。     

基于DNA计算的分子下推自动机(英文)

DNA分子计算的工作原理是对生物系统进行编码,以生物化学反应为基础,利用生物技术实现生物系统的状态转移来推进计算过程．2001年以色列的Yaakov Benenson等人在基于DNA计算的发卡模型实现了具有状态转移功能的分子有限状态自动机,国内则有利用DNA计算的方法构造可编程分子下推存储器的相关研究．该存储器基于分子自动机的原理,能按一定逻辑进行自组装,是一种纳米尺度的生物存储机构．文中首先通过在分子有限自动机上扩展一个分子下推存储器从而获得了一种简单的分子下推自动机,并基于该下推自动机提出了一类语言的分子自动机解法．接着提出了两种改进的分子下推自动机的模型,通过增加模型复杂度,分别解决了基本型分子下推自动机存在输人字符串限制和输入分子形式不统一的问题．计算理论表明,该种下推自动机的计算能力超过了已有的有限自动机．     

可满足问题的分子信标计算模型(英文)

分子信标（Molecular Beacon）是一种发夹状的荧光探针,它可以特异地和那些与分子信标的环（Loop）互补的核酸靶序列杂交,具有单个碱基错配的检测能力．肽核酸（Peptide Nucleic Acid）是人工合成的核酸（DNA）的类似物．PNA骨架为酰胺键,与DNA补链杂交更稳定,可以阻止聚合酶延伸反应．文中将可满足问题的约束变量编码于分子信标的环部识别区,通过分子信标与使得给定范式为真的变量的PNA补链杂交,再利用PNA链可以阻止聚合酶延伸反应的性质,用限制性内切酶EcoRI降解对应于非解的分子信标,最后通过加热表面使分子信标构形发生变化,产生荧光读解．提出的可满足问题的分子信标计算模型具有可靠性高、无需观察和记录计算的中间结果、读解简单等优点．     

图的最大团与最大独立集粘贴DNA计算模型

粘贴模型(stickermodel)是DNA计算中一个很重要的模型.其主要原理就是采用单双链混合型DNA分子进行编码,其优点在于在生物操作过程中不需要DNA链的延伸,不需要生物酶的作用以及DNA链可重复使用等,因此引起了来自不同学科的学者们的广泛关注与兴趣.文中提出了一种求解图的最大团问题的DNA计算模型,该模型采用了两种基本并行计算处理思想,一种是将图分解成小的子图来处理的并行思想;另一种是进行并行生物操作.     

DNA计算机原理、进展及难点(V):DNA分子的固定技术

在DNA计算机的研制中,DNA分子的固定是首先需要处理的一个最为基本的技术问题.事实上,DNA分子的固定技术不仅是生物计算的一个基本技术,而且是整个基因工程、生物芯片,甚至某些疾病诊疗的基础.基于此,文中将对DNA分子的固定技术给予较为系统的研讨,包括基本原理、具体方法等.文中引入了"DNA分子固定系统"的结构体系,并对该结构体系中载体子系统、固定剂子系统、标记子系统这3个主要子系统进行了详细的论述.     

数制转换的DNA计算模型

本文主要研究十进制与二进制互换的DNA算法。利用DNA分子的数制转换库,根据进制转换的一种并行计算方法,通过编码不同结构的数制转换DNA分子来构造DNA计算的自装配模型。该模型可以解决不同进制数的自动转换问题。本文阐明了数制转换库的结构,并给出了转换库的空间复杂度。     

DNA计算中的数据与计算模型

对DNA计算的通用性及单链、双链、粘性末端、发夹、质粒、k-臂DNA分子等各种数据作了简单介绍,并对基于DNA分子结构特性和基于DNA计算机研制过程两个方面的DNA计算模型进行了分析对比。针对各种不同的DNA数据及特性,提出了混合DNA计算模型的研究思路,并从不同角度论述了混合DNA计算模型的可行性。     

微流控制系统在DNA计算中的应用

DNA计算系统以人工合成或自然存在的DNA分子作为信息存储的媒介,通过分子生物工程技术例如PCR、凝胶电泳、酶反应实现计算过程。文章简要介绍了DNA计算的原理、特点及研究概况,从对DNA及蛋白质分子的操控及检测两个方面详细分析了微流控制系统在DNA计算中的应用。研究了生物芯片在集成DNA计算系统中的作用,随着可集成的功能通用化、结构三维化生物芯片系统的出现,基于生物芯片的DNA计算系统将可能成为DNA计算机的一种重要实现途径。     

基于DNA Tiles自组装的布尔逻辑运算

大量研究工作表明,DNA tiles自组装现象是分子生物计算过程中一个很重要的计算方式.分子自组装的基本特点在于由许多小分子在一定机理的作用下,自动形成更大规模的超级分子结构的过程.自组装用于计算,在于这种组装模式可以抽象成一个自动化的系统,只需根据问题的需要设计好输入,再将其输入到运算系统,经过分子自组装过程,最后能生成问题的解.文中基于这样的运算机理,在DNA tiles自组装这个计算平台上,尝试做布尔逻辑运算,针对4变量4句子的布尔逻辑问题,提出一个DNA tiles自组装自动化运算系统.     

DNA自组装的可满足性问题模型

DNA自组装技术在DNA计算和纳米技术领域都发挥着极其重要的作用,许多小规模NP完全问题都可以通过自组装模型得以解决.文中以可满足问题为模型,通过构造范式中变量的特殊补链,使其与初始数据库中初始DNA链发生杂交反应,形成发夹结构,利用形成发夹结构的DNA链与没形成发夹结构的DNA链长度不同的特点,通过凝胶电泳将这些带发夹的DNA链提取出来;然后加入与这些特殊补链完全互补的DNA链,在一定温度下,通过碱基互补配对原则,发夹结构又将被重新打开.该模型充分利用了DNA分子间的自组装能力,在计算过程中只需要用到凝胶电泳操作,在一定程度上大大减少了因生物操作过多而引起的各种实验误差.     

DNA计算机:原理、进展及难点(Ⅱ)计算机"数据库"的形成--DNA分子的合成问题

基于生化反应机理的DNA计算机模型引起了科学领域内许多不同学科学者们的关注与兴趣．DNA计算已经成为国际科学研究前沿领域内的一个新热点．DNA计算机的研制需要诸如生物工程、计算机科学、数学、物理、化学、信息科学、微电子技术、激光技术以及控制科学等许多学科的共同协作攻关．作者以系列文章的形式拟对DNA计算机的基本原理、研究进展、DNA计算的模型以及当前研究中的难点给予研讨．该文属第二篇,重点讨论DNA计算机研制中DNA分子的合成问题．DNA分子的合成问题不仅是DNA计算中生物操作过程首先要处理的问题,而且是DNA计算机研制中必须要解决的问题,因为最终实用化的DNA计算机应是一种全自动化的．如何将DNA分子的合成过程与编码、其它生化操作自动地衔接起来是全自动化DNA计算机当前研究的关键难题．若要解决这个问题,人们必须很熟悉有关DNA分子合成的基本原理以及合成技术．这也是该文的动机．     

基于环形DNA分子的一种求解最大集团的计算模型

文中提出了一种基于环形DNA分子的新型计算模型.该模型的核心构成包括环形DNA分子,链霉亲和素包被的磁珠及环化酶.通过应用该模型解决了一个5个顶点的最大团问题,证明了该模型的可行性.在整个计算过程中,真解的搜索是借助于磁珠和环化酶,DNA分子结构在线性和环形之间相互转化.环形DNA分子的应用极大地减少了计算所需的时间和空间,算法的时间和空间复杂度均为O(n+m).对于解决一个n个节点的最大团问题,这种算法和枚举型算法相比,在搜索过程中所需试管数较少,只需n+1个试管,而利用枚举型算法则需要2n个试管.另外,文中构建的非枚举型初始解空间大大提高了DNA计算机的存储和计算能力.在将来,这种新型的DNA计算模型或许会成为一种解决某些NP完全问题的有效工具.