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.     

Application of Mismatch Detection Methods in DNA Computing

In many implementations of DNA computing, reliable detection of hybridization is of prime importance. We have applied several well-established DNA mutation scanning methods to this problem. Since they have been developed for speed and accuracy, these technologies are very promising for DNA computing. We have benchmarked a heteroduplex migration assay and enzymatic detection of mismatches on a 4 variable instance of 3SAT, using a previously described blocking algorithm. The first method is promising, but yielded ambiguous results. On the other hand, we were able to distinguish all perfect from imperfect duplexes by means of a CEL I mismatch endonuclease assay.     

DNA computing approach for automated test pattern generation for digital circuits

Testing of digital circuits is a compute intensive problem. This article deals with the problem of automated test pattern generation for large digital circuits. A new evolutionary approach based on DNA computing is presented, which exploits the computational power of DNA molecules to solve the problem. A Boolean formula in conjunctive normal form is extracted from the circuit under test and then the proposed algorithm based on DNA computing is used to find the solution satisfying that formula. Exploiting the massive parallelism and recombination properties of DNA molecules, a test vector is found in polynomial time i.e., O (nk). Its effectiveness in terms of Fault coverage, CPU time and Test vector generated is compared with some existing classical approaches like simulated annealing and genetic algorithms.     

Incorporation and use of modified nucleotides in aqueous DNA computing

The concept of aqueous computing involves the use of large numbers of initially identical molecules to serve as memory registers in a fluid environment. Here, we test a new approach to aqueous computing where modified nucleotides are used to “write” on double-stranded DNA molecules to establish the logical values of true or false for a set of clauses. We introduce an implementation scenario where binding proteins specific to each modification can be used to selectively isolate DNA fragments with these modified nucleotides. In addition, we present initial results showing successful incorporation and detection of modifications. We have successfully labeled DNA fragments with four modifications, specifically Alexa Fluor-488, BODIPY-FL, biotin, and digoxigenin using polymerase chain reaction. The first two produce fluorescent molecules that can be distinguished by their color. We have confirmed that binding proteins or antibodies to these four modifications are specific and do not detect the other modifications. We have also successfully separated the DNAs labeled with Alexa Fluor and biotin using binding proteins. We present attempts at rebinding these modified molecules to a second binding protein; the equivalent of applying more than one clause to a set of values. We have found some challenges with this approach that likely can be resolved with further work. As there are millions of molecules with corresponding binding proteins, this approach has the potential to yield unlimited computing power as compared with other aqueous computing methods.     

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计算模型

DNA计算是以DNA分子作为数据的一种新型计算模式.为了减少DNA计算中编码的数量,不降低生化实验操作的可靠性,文中建立了一种基于酶切技术和PCR技术的图顶点着色DNA计算模型,给出了实现该模型的双编码的编码方案.分析表明,利用酶切技术和PCR技术能够有效删除非解并读取真解.该模型的解的检测方法类似于DNA测序技术,使得该模型更容易实现自动化操作.     

求解0-1规划问题的DNA计算模型(英文)

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

DNA fragment assembly using a grid-based genetic algorithm

In this paper we propose a genetic algorithm (GA) for solving the DNA fragment assembly problem in a computational grid. The algorithm, which is named GrEA, is a steady-state GA which uses a panmitic population, and it is based on computing parallel function evaluations in an asynchronous way. We have implemented GrEA on top of the Condor system, and we have used it to solve the DNA assembly problem. This is an NP-hard combinatorial optimization problem which is growing in importance and complexity as more research centers become involved on sequencing new genomes. While previous works on this problem have usually faced 30 K base pairs (bps) long instances, we have tackled here a 77 K bps long one to show how a grid system can move research forward. After analyzing the basic grid algorithm, we have studied the use of an improvement method to still enhance its scalability. Then, by using a grid composed of up to 150 computers, we have achieved time reductions from tens of days down to a few hours, and we have obtained near optimal solutions when solving the 77 K bps long instance (773 fragments). We conclude that our proposal is a promising approach to take advantage of a grid system to solve large DNA fragment assembly problem instances and also to learn more about grid metaheuristics as a new class of algorithms for really challenging problems.     

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

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

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

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

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

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

Performing DNA computation with RecA-mediated triple-stranded DNA structure

A new method of DNA computing using an unusual triple-stranded DNA structure mediated by RecA protein is introduced and a minor 3-variable instance of the satisfiability (SAT) problem is solved. Separations were performed by using biotinylated oligodeoxynucleotide probes coated with RecA protein. During the computation, sequence-specific recognition of double-stranded DNA by homologous oligodeoxynucleotides was fulfilled in the presence of ATPγS. Captured by the magnetic particles coated with streptavidin, the desirable double-stranded DNA strands were retained and extracted. It is suggested that the methods employed here may help decrease the errors in DNA computation and solve some larger size NP- complete problems.     

DNA computation simulator based on abstract bases

 We developed a simulator to aid those who design algorithms and protocols for DNA computing. In this simulator, abstract sequences instead of real DNA sequences are used to represent molecules in order to increase efficiency of simulations. Two approaches for simulation are available: threshold and stochastic. The simulator consists of two main parts, one for finding reactions among existing molecules and generating new ones, and the other for numerically solving differential equations to calculate the concentration of each molecule. The two parts rely on each other. In particular for the threshold approach, the former avoids a combinatorial explosion by setting a threshold on concentrations of molecules that can take part in reactions. In addition, the stochastic approach is also available for simulations which are hard by the threshold approach. Some simulation results by the approaches are also presented: computation of Boolean circuits, whiplash PCR, formation of DNA tiles and polymerase chain reaction (PCR). We also integrate simulating DNA computation and fitting parameters by the genetic algorithm (GA), where simulation results are used as evaluation functions for the genetic algorithm. The integration is applied to find good protocols for PCR amplification. A trial to refine the reaction model for hybridization is also described before the final discussion on the simulator.     

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

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

数制转换的DNA计算模型

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

并行型Ramsey数DNA计算模型

求解Ramsey数的困难在于需要搜索的解空间太大,而传统的电子计算机无法在有效的时间和存储空间上进行求解.由于DNA计算具有巨大的并行性和高密度存储能力等优点,文中研究了Ramsey数的DNA计算模型.针对传统的Ramsey数DNA计算模型存在的DNA序列量过多和序列过长的不足,利用DNA分子的特性以及生物操作将非解尽可能较早地消除,提出了并行型Ramsey数DNA计算模型,并以R(3,10)为例,给出了具体的求解步骤.     

DNA编码问题及其复杂性研究*

高质量的DNA编码可以避免DNA分子间的非特异性杂交,提高DNA计算的有效性和可靠性。首先对DNA编码的约束条件进行归类,分析了各编码约束对编码质量的影响;然后研究了编码质量、编码数量、序列长度与DNA计算可靠性、有效性、可扩充性之间的关系;最后通过类比DNA编码问题和图的独立集问题,说明了求解最大DNA序列集合问题是NP完全的。     

基于汉明距离的DNA编码约束研究

DNA计算是将现实问题进行编码映射到DNA分子上,通过生物实验产生出代表问题的解的DNA分子,最后通过检测技术提取出该DNA分子。高质量的DNA编码可以尽可能避免或减少计算过程中出现的错误,并使检测阶段易于提取出代表问题的解的DNA分子。对DNA编码约束进行了研究,分析了基于汉明距离的编码约束可以有效降低DNA分子间相似程度,减少DNA计算过程中DNA分子间的相互干扰,从而提高DNA计算的有效性和可靠性。还证明了基于汉明距离的编码约束存在等价的序列组合,降低了编码计算的复杂度。     

How ciliates manipulate their own DNA – A splendid example of natural computing

DNA computing is a novel and vivid researcharea which is genuinely interdisciplinary –computer scientists and molecular scientistscollaborate to investigate the use of DNAmolecules for the purpose of computing. DNAcomputing in vivo is the investigation ofcomputations taking place naturally in a livingcell, with the goal of understandingcomputational properties of DNA molecules intheir native environment. Gene assembly inciliates (single cell organisms) is perhaps themost involved process of DNA manipulation yetknown in living organisms. The computationalnature of this process has attracted muchattention in recent years. The resultsobtained so far demonstrate that this processof gene assembly is a splendid example ofcomputing taking place in nature, i.e., NaturalComputing. Indeed, DNA computing in vivomay be far more widespread in nature than wecurrently recognize. This paper is a tutorialon (computational nature of the) gene assemblyin ciliates, which is intended for a broadaudience of researchers interested in NaturalComputing. In particular, no knowledge ofmolecular biology is assumed on the part of themotivated reader.     

A tissue P system and a DNA microfluidic device for solving the shortest common superstring problem

This paper describes a tissue P system for solving the Shortest Common Superstring Problem in linear time. This tissue P system is well suited for parallel and distributed implementation using a microfluidic device working with DNA strands. The approach is not based on the usual brute force generate/test technique applied in DNA computing, but it builds the space solution gradually. The possible solutions/superstrings are build step by step through the parallel distributed combination of strings using the overlapping concatenation operation. Moreover, the DNA microfluidic device solves the problem autonomously, without the need of external control or manipulation.An erratum to this article can be found at