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

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

赋权图上优化问题的DNA计算方法研究(英文)

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

可满足性问题的三维DNA图结构算法

论文提出用三维图结构解决DNA分子计算问题,给出了解决3-SAT问题的方法。在所提出的方法中,算法所要求的步骤与公式中变量的数目相等。     

基于BP神经网络的DNA解链温度预测模型

在DNA计算中,为了确保计算过程的可靠性,要求编码信息的DNA序列必须具有相似的热力学稳定性。解链温度是目前评价DNA序列热力学稳定性的一个主要的参数,目前,生物工程中常用的各种预测方法都存在某些序列的误差偏大的缺点,因此难以满足像DNA计算这种大量DNA序列进行各种生化反应的计算过程的要求。论文以DNA序列的邻近法参数为基础,建立了一个基于BP神经网络的解链温度的预测模型。计算结果表明,DNA序列的解链温度的误差可以达到±5.5℃的范围。     

DNA计算与DNA密码

DNA计算作为一种新型计算模式,目前在理论和实践方面取得了若干初步成就。得益于DNA计算,密码学新领域——DNA密码也得到一定发展。DNA密码的安全性可以不依赖于计算困难问题,并且能够充分利用DNA分子所具有的超高存储密度、超低的能量消耗以及超大规模并行计算潜力。本文介绍了DNA计算的基本原理,DNA密码的基本特征,给出DNA计算和DNA密码的实例,并简要分析目前存在的问题及未来的展望。     

离散数学中的DNA计算

由于电子计算机的存贮量小,运算速度慢,智能化低,特别是制造工艺趋于极限。最近,采用计算的可能性引起了人们的广泛关注,尤其是它的良好的并行性。离散数学中的逻辑演算有着广泛的应用,特别是在信息处理方面。论文给出了一个运用图论和DNA计算的方法,解决较复杂的逻辑演算问题。     

哈密顿回路问题的DNA表面计算模型

基于生化反应原理的DNA计算具有强大的并行运算能力,DNA计算机在求解NP问题上存在着硅计算机无法比拟的先天的优越性。论文采用荧光标记的策略,给出了一种新的哈密顿回路问题的DNA表面计算模型。该模型首先将问题解空间的DNA分子固定在固体载体上,然后通过进行相应的生化反应来求得哈密顿回路问题的所有解。在新模型中,解空间的生成过程与边的排列顺序无关。     

DNA并行计算中的B-树数据结构的设计与实现

DNA分子特性使得DNA计算具有极大的存储密度和高度的计算并行性。不管何种计算模型,DNA分子的选择和DNA编码都十分重要。提出了DNA计算中的B-树的数据结构设计方法。首先给出了B-树定义及其操作的形式化描述,接着介绍了本计算模型采用的3D结构DNA分子——k-arms分子结构,详细给出了一棵m阶B-树的构造步骤,最后实现了其查找、插入和删除等操作。提出了DNA分子计算的3D结构和分治策略,具有一定的可扩展性和并行性,对DNA计算的其他模型有参考价值。     

DNA计算与背包问题

该文通过对背包问题这一典型的NP完全问题的DNA计算研究,针对属于组合优化一类的ZKP问题给出了一种DNA计算方法,该算法解决了组合优化一类DNA计算的加权赋值问题,并根据DNA计算的特点给出了一般加权赋值型组合优化问题的DNA计算模式。     

粘贴与删除系统求解最短有向路的DNA计算模型

最短有向路问题是在一个有向网络中的两个指定顶点之间找出一条具有最小权的有向路,它在工程实践中具有广泛的应用。粘贴系统与删除系统是DNA计算形式模型中的两种基本模型。论文利用粘贴与删除系统的巨大并行性给出了求解图最短有向路问题的DNA计算模型及其实现算法。     

DNA计算模型的研究

DNA计算模型在DNA计算的各个研究领域中占有重要的地位,对DNA计算模型进行研究是有意义的。首先回顾了DNA计算模型的发展历史;然后从DNA的基本结构入手研究了DNA计算的机理,并对DNA计算的过程进行了详细分析,从而归纳出DNA计算模型的基本概念;再对DNA计算模型按照DNA计算的物质形态进行了分类并对每一类DNA计算模型的理论及其应用进行了详细的分析。     

一种新的求解最小生成树问题的DNA算法

基于生化反应的生物智能计算是现阶段计算领域研究的热点,DNA计算是通过DNA分子之间的生化反应来进行计算的一种计算模式,凭借运算巨大的并行性和海量存储的优势,DNA计算在解决复杂运算问题方面的计算能力显而易见。设计了一种利用DNA计算来求解图的最小生成树的计算模型,采用一种特殊的编码方式来对顶点,边和权值进行编码,并且描述了MSTP解的计算过程。     

浅析DNA计算及其发展状况

近年来,基于生化反应机理的DNA计算模型受到科学领域内许多不同学科领域学者们的关注。DNA计算已经形成国际科学前沿领域内研究的一个新的热点。该文主要讨论了DNA计算的原理,综述了DNA计算的特点、DNA计算模型,并指出了DNA计算研究中存在的问题,最后就DNA计算的发展前景进行了展望。     

Bio-soft computing with fixed-length DNA to a group control optimization problem

A bio-soft computing method with fixed-length DNA to solve a group control optimization problem is presented in this paper. In the example of a multi-elevator dispatching problem, fixed-length DNA strands are used in representing the nodes and costs, where the costs are varied by the melting temperature of DNA strands. The optimal solution to a 6-story 2-elevator dispatching problem is searched by biochemical techniques based on the thermodynamic properties of designed DNA strands. This research has shown the potential of bio-soft computing solving the engineering applications, and could be implemented in the future bio-systems.     

DNA分子计算模型

The field of practical DNA computing opened in 1994 with Adleman's paper,in which a laboratory experi-ment involving DNA molecules was used to solve a small instance of the Hamiltonian Path problem. The characteris-tic of this computation is its powerful ability in parallelism,its huge storage and high energy efficiency. This paper mainly introduces the principles of DNA computing and the sticker computing model.     

DNA计算机原理、进展及难点（I）：生物计算机系统及其在图论中的应用

基于生化反应机理的DNA计算机模型受到科学领导内许多不同科学者们的关注与兴趣。DNA计算已经形成国际科学前沿领域内研究的一个新的热点。DNA计算机的研制需要诸如生物工程、计算机科学、数学、物理、化学、信息科学、微电子技术、激光技术以及控制科学等许多学科的共同协作攻关。该系列文章拟对DNA计算机的基本原理、研究进展DNA计算的模型以及当前研究中的难点给予研讨。该文属首篇，重点讨论了DNA计算机的基本原理，引入了生物计算系统的概念，并较系统地讨论了DNA计算模型在图与组合优化中的研究进展。     

Aqueous Computing: A Survey with an Invitation to Participate

The concept of aqueous computing is presented here,first infull generality,and afterward,using an implementation in a specific enzymatic technology.Aqueous computing arose in the context of biomoloecular (DNA) computing,but the concept is independent of the specifics of its biochemical origin.Alternate technologies for realizing aqueous computing are being considered for future implementation.A solution of an instance of the Boolean satisfiability problem,(SAT),is reported here that provides a new example of an aqueous computation that has been carried out successfully.This small instance of the SAT problem is sufficiently complex to allow our current enzymatic technology to be illustrated in detail.The reader is invited to participate in the rich interdisciplinary activity required by wet lab computing.A project is suggested to the reader for determining the three-colorings of a graph.The basic operations required for this project are exhibited in the solution of the SAT example reported here.     

基于DNA计算的RSA密码系统攻击方法

针对RSA公钥密码体制的陷门库特点,提出一种新的DNA计算模型：并类计算模型,阐述基于该模型的RSA密码系统的攻击方法。该方法采用DNA分子编码陷门库与公钥,通过组合、设置、分离、清除等操作筛选出陷门,由电泳确定陷门的值,再用陷门计算私钥的值。该方法所需的时间复杂度为O(1bn)3,DNA分子的体积不超过1 m3。     

DNA逻辑计算模型的研究现状与展望

DNA计算因其优异的计算能力已经成为当前研究热点,DNA逻辑计算模型是DNA计算体系与运算实现的重要依托。按应用技术将现有DNA逻辑计算模型进行分类：基于链置换的DNA逻辑计算模型、基于核酶的DNA逻辑计算模型、基于G-quadruplex的DNA逻辑计算模型、基于DNA自组装的逻辑计算模型、基于其他分子技术和分子材料的DNA逻辑计算模型。首先阐述了DNA逻辑计算的研究背景和研究目的以及现阶段在生物分子检测、疾病诊断、多因素分析和生物成像等领域的应用并简述其相关概念;然后梳理各DNA逻辑计算模型的研究历史和现状,分析各类逻辑计算模型所应用的分子操控技术和分子材料以及优缺点和应用前景;最后归纳总结DNA逻辑计算领域当前研究热点和发展前景,为未来提出全新的计算方式奠定基础,为信息、医疗等领域提供更好的服务。     

Protein output for DNA computing

In recent years, several strategies for DNA based molecular computing have been investigated. An important area of research is the detection and analysis of output molecules. We demonstrate how DNA computing can be extended with in vivo translation of the output. In the resulting proteins, the information per kilogram is about 15-fold higher than in the original DNA output. The proteins are therefore of correspondingly smaller mass, which facilitates their subsequent detection using highly sensitive mass spectrometry methods. We have tested this approach on an instance of the Minimal Dominating Set problem. The DNA used in the computation was constructed as an open reading frame in a plasmid, under the control of a strong inducible promoter. Sequential application of restriction endonucleases yielded a library of potential solutions to the problem instance. The mixture of plasmids was then used for expression of a protein representation. Using MALDI-TOF mass spectrometry, a protein corresponding to the correct solution could be detected. The results indicate the feasibility of the extension of DNA computing to include protein technology. Our strategy opens up new possibilities for both scaling of DNA computations and implementations that employ output of functional molecules or phenotypes.