计算机学报杂志 北大期刊 CSCD期刊 统计源期刊

计算机学报 2008年第12期杂志 文档列表

计算机学报杂志研究论文与技术报告

经典Ramsey数DNA计算模型（Ⅰ）：位序列计算模型2073-2080

摘要：Ramsey数问题是组合数学乃至整个数学中最具魅力的研究领域，也是最困难的数学问题之一．对于经典Ramsey数，至今只有9个Ramsey数得到解决．按照传统的算法，其搜索空间太大，当前的电子计算机无法胜任．研究表明，DNA计算在求解困难的NP一完全问题上优于电子计算机．目前已经建立了众多求解NP-完全问题的DNA计算模型，但未见到用于求解Ramsey数的DNA计算模型．作者建立了一种新颖的DNA计算模型，用于一般经典Ramsey数的求解．全文共分两篇，该文属首篇，建立了一种可适用于DNA计算模式的所谓的求解Ramsey数的位序列计算模型，其中的位序列是以图的相邻矩阵下三角阵中行从左到右、列从上到下的排列次序．文中重点对该模型的机理与使用方法进行了分析研究．

经典Ramsey数DNA计算模型（Ⅱ）：基于位序列的DNA计算模型2081-2089

摘要：Ramsey数问题是组合数学乃至整个数学中最具魅力的研究领域，也是最困难的数学问题之一．对于经典Ramsey数，至今只有9个Ramsey数得到解决．按照传统的算法，其搜索空间太大，当前的电子计算机无法胜任．研究表明，DNA计算在求解困难的NP-完全问题上优于电子计算机．目前已经建立了众多求解NP-完全问题的DNA计算模型，但未见到用于求解Ramsey数的DNA计算模型．作者建立了一种新颖的DNA计算模型，用于一般经典Ramsey数的求解．全文共分两篇，该文属第二篇，在首篇工作的基础上，建立了所谓的经典Ramsey数位序列DNA计算模型，文中对模型的存储库的建立、解的检测子系统以及运算子系统等问题展开了较为详细地讨论，并给出了使用该模型求解经典Ramsey数详细的方法与步骤．

脉冲神经膜计算系统的研究进展及展望2090-2096

摘要：脉冲神经膜计算系统是膜计算的一个新分支，不仅具有计算机科学研究意义，而且在生物建模和仿真方面有潜在的应用价值．文中介绍了脉冲神经膜计算系统的基本概念并给出了脉冲神经膜计算系统的一个例子；除了介绍标准脉冲神经膜计算系统外，还介绍若干广义的脉冲神经膜计算系统；概述了脉冲神经膜计算系统计算完备性和计算有效性两个方面的主要结果；指出了进一步研究脉冲神经膜计算系统的两个方向．

利用脱氧核酶调控基因表达的DNA计算模型研究2097-2102

摘要：用于逻辑调控基因表达分子自动机的研究是DNA计算的重要研究领域．文中将脱氧核酶技术应用于DNA计算研究当中，利用脱氧核酶的特性，特别是可以作为反义药物的特点，作为构建分子自动机的主要材料，设计了调控基因H—ras表达的DNA计算模型，而且模型也可适用于其它过表达基因的调控．结合DNA计算具备的高度并行性和智能性的优点，该模型为DNA计算在基因表达调控方面的应用做了进一步探索．

活体生物计算模型的研究进展及展望2103-2108

摘要：活体生物计算模型是基于生物体内各种生化分子以特定的形式互相协作、处理信息的能力而出现的一种新的计算模型．由于其计算组成部件是直接镶嵌在生物活体里面，并且显示具有一定的计算能力，这可以使人们深人研究生物体信息处理能力以及获得对这种能力的有效控制．该文介绍了近几年几类体内生物计算模型，用于求解NP完全问题、基因逻辑电路、分子自动机研究状况，并对未来的发展方向进行了展望．

基于压电基因传感器的DNA计算2109-2115

摘要：压电基因传感器是一种新型的生物传感器，它把压电传感器的灵敏性和DNA杂交反应相结合．与传统的基因检测技术相比，它具有结构简单、无需标记、检测时间短、检测信号易处理等特点．将它用于分子运算，与常规的DNA芯片相比，它的检测结果更易于进行自动化处理，因此便于构建大规模的分子运算机器．文中在压电基因传感器和新兴学科DNA计算的基础上，给出了解决0-1规划问题新的DNA计算方法，并指出以前两种基于表面DNA计算在解决这一问题时的不足．与以往的DNA计算方法相比其输出的是电信号，因此具有操作易自动化、识别解更方便和高信息量的优点．与使用常规DNA芯片的表面DNA计算相比，使用压电基因传感器进行DNA计算可以克服可行解识别困难的问题．压电基因传感器技术有望成为新的分子运算工具，可作为构建自动化的DNA计算机的基础．

基于DNA计算自组装模型的Diffie—Hellman算法破译2116-2122

摘要：DNA自组装计算模型是近年来引人关注的计算模型，已有基于自组装模型的二进制加法、乘法以及有限域中的加法和乘法的讨论．文中利用DNA自组装模型设计的模乘系统，实现了素数P的本原根g连续乘方后模p的数的排列，从而可以在线性时间内求解离散对数，为破译Diffie—Hellman密钥交换算法提供了新的生物方法．该模乘系统使用了Θ（p）种自组装类型，组装的时间复杂度为Θ（p-1）．系统最后组装结果提取出报告链后，经过PCR和凝胶电泳读取离散对数结果．该模型扩展了DNA自组装计算模型的应用，为求取离散对数提供了新思路．

基于粘贴和删除系统的图着色问题分析2123-2128

摘要：图着色问题是图与组合优化中的一个NP-完全问题．现有算法在求解图着色问题时，计算复杂性随着待解问题规模的增大呈指数增长．粘贴系统和删除系统是分别基于粘贴运算和删除运算的两种语言生成器．文中将图着色问题和图的坏边数结合起来，将图着色问题转化成搜索最长序列的问题，然后利用粘贴系统和删除系统的并行性，得到了图的色数及其所有色类．与已有求解图着色问题的DNA算法相比，新的算法具有较低的复杂性．

基于自组装DNA计算的NTRU密码系统破译方案2129-2137

摘要：自组装DNA计算在解决NP问题，尤其在破译密码系统方面，具有传统计算机无法比拟的优势．文中提出了一种用自组装DNA计算破译NTRU公钥密码系统的方法．针对NTRU密码系统的特点，采用DNA瓦片编码信息，借助于瓦片间的粘性末端进行自组装，给出了求解多项式卷积运算的实现方案．在此基础上，通过引入非确定性的指派瓦片，提出了一种破译NTRU系统的非确定性算法．通过创建数以亿计的参与计算的DNA瓦片，该算法可以并行地测试每个可能的密钥，以高概率地输出正确密钥．该方法最大的优点是充分利用了DNA瓦片具有的海量存储能力、生化反应的巨大并行性以及组装的自发有序性．理论分析表明，该方法具有一定的可行性．

DNA自组装技术的研究进展及难点2138-2148

摘要：近年来，DNA自组装成为DNA计算及纳米材料科学等领域研究的热点，它关系着DNA计算机的发展．DNA分子如何组装已成为许多学者关注的焦点．为此，文中主要围绕着DNA分子组装成的初级元件的类型：一条长的DNA单链、多条短寡核苷酸链和自组装单元，重点从自组装的初级元件形成的一维、二维及三维结构上讨论DNA自组装技术与方法．文中讨论了这些技术的原理及应用的研究进展，并且分析了DNA自组装应用于DNA计算的主要难点及解决方案．首先，编码的好坏决定着实验是否能实施；其次，DNA单链之间组装的角度及初级原件之间的连接是影响自组装体产量的关键因素；从具体的实验操作上看，每条DNA单链的浓度比例及退火温度则决定着自组装的成败．随着学科之间的高度交叉，DNA自组装将是材料学、信息学、生物学等领域的重要研究方向，也是推动DNA计算机发展的重要手段．

DNA计算中核酸序列设计方法比较研究2149-2154

摘要：DNA计算是将现实问题进行编码，映射到DNA分子上，然后通过分子生物实验产生出代表问题解的DNA分子，最后通过检测技术提取出该DNA分子．高质量的DNA编码可以尽可能避免或减少计算过程中出现的错误，并使检测阶段易于提取出代表问题解的DNA分子．文中对基于汉明距离和基于自由能的DNA核酸编码方法进行研究，分析了两类方法的约束条件对DNA编码质量的影响，比较了两类方法排除非特异性杂交的完备性和计算量，进一步分析了两类方法编码DNA序列的效率．通过分析和比较得到，两类DNA计算编码方法都能有效地限制DNA分子间的非特异性杂交，其中基于汉明距离的DNA编码方法的计算量比较小，但是它仅能近似地估计DNA分子间杂交的热力学稳定性，不能完全替代最小自由能的编码方法．在满足DNA计算试验精度要求的条件下，采用基于汉明距离的DNA编码设计方法不仅能有效地的挑选出特异性杂交和非特异性杂交的DNA序列，还能有效地减少计算量，从而提高DNA序列设计的效率．

求解0-1规划问题的DNA计算模型2155-2159

摘要：DNA计算是以DNA分子作为数据的一种新型计算模式．在DNA计算中首要面对的问题是编码问题．文中提出了一种双编码方法，利用这种编码方法可以使得在DNA计算的读解过程类似于DNA测序过程，容易实现自动化操作．基于该编码方法所建立的DNA计算模型可用于求解0-1规划问题，只需4次PCR反应即可读取问题的可行解．与其他DNA计算模型相比，该模型具有操作简单、易于实现的优点．

DNA纳米结构自装配的语言能力分析2160-2167

摘要：文中研究了DNA分子杂交的内在计算能力．一方面，文中基于Winfree先前关于线性分子自装配仅能产生正则语言工作的基础上，进一步扩展证明了线性自装配通过杂交分别表示左、右线性派生的线性分子，也能产生线性语言．另一方面，文中定义了一种新的通过上下文无关语言通过自装配产生线性语言的方法，即证明了等价于上下文无关语言的特定序列集能通过1-，2-，3-粘头分子的混合自装配产生线性语言，同时，这是对Winfree关于树状纳米结构自装配等价于上下文无关语言理论的一个较好的补充．

基于DNA计算的分子下推自动机2168-2172

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

一种改进的最大团问题DNA计算机算法2173-2181

摘要：随着DNA计算的不断发展，如何克服穷举算法带来的指数爆炸问题已成为DNA计算领域的重要研究目标之一．将图灵机中的剪枝算法设计技术应用于最大团问题的DNA计算中，提出一种最大团问题的新DNA计算机算法．算法由顶点度数搜索器、团生成器、稀疏图与稠密图并行搜索器以及最大团搜索器组成．与已有文献同类算法的对比分析表明：文中算法在保持多项式操作时间的条件下，将求解n个顶点的最大团问题所需DNA分子链数从现有文献的O（2^n）减少至O（√3^n），同时文中算法还具有高效的空间利用率及容错能力的优点．

赋权图上优化问题的DNA计算方法研究2182-2192

摘要：对赋权图上经典优化问题的DNA计算方法进行探讨，改进原有DNA计算模型中的权值编码方法，提出一些新的DNA编码方法及DNA算法．具体地说，通过设计赋权无向图的相对长度图给出了旅行商问题的一种相对长度DNA编码方法及DNA算法，通过设计赋权无向图的广义边图给出了中国邮递员问题的一种广义边图DNA编码方法及DNA算法，通过选取DNA序列的最佳逆补比对给出了最小生成树问题的一种基于逆补比对的DNA编码方法及DNA算法，通过设计从顶点覆盖问题到Hamilton回路问题的一种改进多项式变换给出了顶点覆盖问题的一种基于多项式变换的DNA编码方法及DNA算法．所设计的DNA计算方法提高了DNA计算中表示数值和处理数值的能力．

基于动态遗传算法的DNA序列集合设计2193-2199

摘要：DNA编码序列的质量与数量直接影响着DNA计算的可靠性和规模，如何找到尽可能好的及尽可能多的DNA序列用于实际的应用一直是DNA计算的一个核心问题．文中首先介绍了研究DNA编码和DNA序列集合对DNA计算的意义，并给出了DNA序列设计的汉明距离和反汉明距离约束条件的定义．DNA序列集合的研究对DNA计算的可靠性和规模有着重要的影响，因此文中利用遗传算法和动态遗传算法来设计满足上述约束条件的DNA序列集合，通过对两种方法所得结果的比较，证明了动态遗传算法明显优于遗传算法．与此同时，将文中所得到的实验结果与前人的研究成果进行比较可知，文中的结果大幅提高了DNA编码的上界，从而进一步缩小了DNA编码界的取值范围．并且文中所给出的实验结果，对以后DNA编码的理论界的研究以及编码理论中关于4元码界的研究，提供了重要的参考值．

背包问题DNA算法的反应设计及其生物实现2207-2214

摘要：有关背包问题的DNA算法近年来得到重视，文中实现了求解背包问题的并行搜索解的实验，通过最优的方法完成有限容量背包的物品选择．展示了面向反应的DN段设计，计算过程为溶液DNA高效连接反应，反应结果分别用定量（PCR）和定性（测序）两种方法检测．文中的方法适用于多重约束条件的优化问题．