DNA芯片在0-1规划问题中的应用

生物芯片技术和DNA计算分别是近年来生命科学与信息科学的新兴研究领域,对信息高度并行的获取与处理是二者的本质特性.而0-1规划问题作为运筹学中一个重要的问题,到目前为止还没有好的算法.在DNA计算和DNA芯片基础上,提出了基于DNA芯片解决0-1规划问题的DNA计算新模型,与以往DNA计算模型相比,该模型具有高信息量和操作易自动化的优点.同时指出DNA芯片技术有望作为新型生物计算的芯片.     

基于分子信标的DNA计算

DNA计算是解决一类难以计算问题的一种新方法,这种计算随着问题的增大可以呈指数增长．迄今为止,许多研究成果已经成功地提高了它的性能和增加了它的可行性,本文在基于表面的DNA计算中采用了分子信标编码策略,并对分子信标在与对应的补链杂交形成双链时的受力进行分析,给出3-SAT问题的另一种解法．这种方法比现有的方法更有效,更具发展前景．因为它具有编码简单;耗材底;操作时间短;技术先进等优点．本文尝试了分子生物学,光学和力学的结合．这一工作为DNA计算能解决NP一完全问题提供了更有力的依据．     

Molecular solutions to the binary integer programming problem based on DNA computation

Binary optimization is a widely investigated topic in integer linear programming. This study proposes a DNA-based computing algorithm for solving the significantly large binary integer programming (BIP) problem. The proposed approach is based upon Adleman and Lipton's DNA operations to solve the BIP problem. The potential of DNA computation for the BIP problem is promising given the operational time complexity of O(nxk).     

An improved surface-based method for DNA computation

DNA computing is a novel method for solving a class of intractable computational problems, in which the computing time can grow exponentially with problem size. Up to now, many accomplishments have been achieved to improve its performance and increase its reliability, among which a surface-based method is an efficient candidate. In this paper, the surface-based approach proposed by Liu, Q., Wang, L., Frutos, A.G., Condon, A.E., Corn, R.M., and Smith, L.M., 2000, DNA computing on surfaces. Nature 403, 175-179 is analyzed and an improved surface-based method for DNA computation (i.e. the hybrid DNA/optical computing method) is proposed. Compared with Liu et al.'s approach, our method has some significant advantages such as low cost, short operating time, reusable surface and simple experimental steps. Moreover, the concept of combining easily patterned DNA computing steps with equally parallel, but generally uniform and not easily patterned optical computing steps is an important new direction.     

分子信标芯片计算在0-1整数规划问题中的应用

生物芯片技术和DNA计算分别是近年来生命科学与信息科学的新兴研究领域,对信息高度并行的获取与处理是二者的本质特性．而0-1整数规划问题作为运筹学中一个重要的问题,到目前为止还没有好的算法．在DNA计算和DNA芯片基础上,提出了基于分子信标芯片解决0-1整数规划问题的DNA计算新模型．与以往DNA计算模型相比,该模型具有高信息量和操作易自动化的优点,同时指出分子信标芯片技术有望作为新型生物计算的芯片．     

Optically programming DNA computing in microflow reactors

The programmability and the integration of biochemical processing protocols are addressed for DNA computing using photochemical and microsystem techniques. A magnetically switchable selective transfer module (STM) is presented which implements the basic sequence-specific DNA filtering operation under constant flow. Secondly, a single steady flow system of STMs is presented which solves an arbitrary instance of the maximal clique problem of given maximum size N. Values of N up to about 100 should be achievable with current lithographic techniques. The specific problem is encoded in an initial labeling pattern of each module with one of 2N DNA oligonucleotides, identical for all instances of maximal clique. Thirdly, a method for optically programming the DNA labeling process via photochemical lithography is proposed, allowing different problem instances to be specified. No hydrodynamic switching of flows is required during operation -- the STMs are synchronously clocked by an external magnet. An experimental implementation of this architecture is under construction and will be reported elsewhere.     

Solving traveling salesman problems with DNA molecules encoding numerical values

We introduce a DNA encoding method to represent numerical values and a biased molecular algorithm based on the thermodynamic properties of DNA. DNA strands are designed to encode real values by variation of their melting temperatures. The thermodynamic properties of DNA are used for effective local search of optimal solutions using biochemical techniques, such as denaturation temperature gradient polymerase chain reaction and temperature gradient gel electrophoresis. The proposed method was successfully applied to the traveling salesman problem, an instance of optimization problems on weighted graphs. This work extends the capability of DNA computing to solving numerical optimization problems, which is contrasted with other DNA computing methods focusing on logical problem solving.     

Computing with DNA by operating on plasmids

A new method of computing using DNA plasmids is introduced and the potential advantages are listed. The new method is illustrated by reporting a laboratory computation of an instance of the NP-complete algorithmic problem of computing the cardinal number of a maximal independent subset of the vertex set of a graph. A circular DNA plasmid, specifically designed for this method of molecular computing, was constructed. This computational plasmid contains a specially inserted series of DNA sequence segments, each of which is bordered by a characteristic pair of restriction enzyme sites. For the computation reported here, the DNA sequence segments of this series were used to represent the vertices of the graph being investigated. By applying a scheme of enzymatic treatments to the computational plasmids, modified plasmids were generated from which the solution of the computational problem was selected. This new method of computing is applicable to a wide variety of algorithmic problems. Further computations in this style are in progress.     

全错位排列问题的基于表面的DNA计算模型

生物表面技术是DNA计算的一种实现方式,是近年来生命科学的新兴研究领域．而全错位排列问题作为组合数学中一个重要的问题,到目前为止还没有好的算法．在DNA表面技术的基础上,首次提出了全错位排列问题的基于表面的DNA计算模型,并对模型进行了简单的分析．     

Solving satisfiability problems using a novel microarray-based DNA computer

An algorithm based on a modified sticker model accompanied with an advanced MEMS-based microarray technology is demonstrated to solve SAT problem, which has long served as a benchmark in DNA computing. Unlike conventional DNA computing algorithms needing an initial data pool to cover correct and incorrect answers and further executing a series of separation procedures to destroy the unwanted ones, we built solutions in parts to satisfy one clause in one step, and eventually solve the entire Boolean formula through steps. No time-consuming sample preparation procedures and delicate sample applying equipment were required for the computing process. Moreover, experimental results show the bound DNA sequences can sustain the chemical solutions during computing processes such that the proposed method shall be useful in dealing with large-scale problems.     

A CLIQUE algorithm using DNA computing techniques based on closed-circle DNA sequences

DNA computing has been applied in broad fields such as graph theory, finite state problems, and combinatorial problem. DNA computing approaches are more suitable used to solve many combinatorial problems because of the vast parallelism and high-density storage. The CLIQUE algorithm is one of the gird-based clustering techniques for spatial data. It is the combinatorial problem of the density cells. Therefore we utilize DNA computing using the closed-circle DNA sequences to execute the CLIQUE algorithm for the two-dimensional data. In our study, the process of clustering becomes a parallel bio-chemical reaction and the DNA sequences representing the marked cells can be combined to form a closed-circle DNA sequences. This strategy is a new application of DNA computing. Although the strategy is only for the two-dimensional data, it provides a new idea to consider the grids to be vertexes in a graph and transform the search problem into a combinatorial problem.     

Construction of a DNA nano-object directly demonstrates computation

We demonstrate a computing method in which a DNA nano-object representing the solution of a problem emerges as a result of self-assembly. We report an experiment in which three-vertex colorability for a six-vertex graph with nine edges is solved by constructing a DNA molecule representing the colored graph itself. Our findings show that computation based on “shape processing” is a viable alternative to symbol processing when computing by molecular self-assembly.     

基于质粒DNA匹配问题的分子算法

给定无向图,图的最小极大匹配问题是寻找每条边都不相邻的最大集中的最小者,这个问题是著名的NP-完全问题.1994年Adleman博士首次提出用DNA计算解决NP-完全问题,以编码的DNA序列为运算对象,通过分子生物学的运算操作解决复杂的数学难题,使得NP-完全问题的求解可能得到解决.提出了基于质粒DNA的无向图的最大匹配问题的DNA分子生物算法,通过限制性内切酶的酶切和凝胶电泳完成解的产生和最终接的分离,依据分子生物学的实验手段,算法是有效并且可行的.     

DNA computation model to solve 0-1 programming problem

0-1 programming problem is an important problem in opsearch with very widespread applications. In this paper, a new DNA computation model utilizing solution-based and surface-based methods is presented to solve the 0-1 programming problem. This model contains the major benefits of both solution-based and surface-based methods; including vast parallelism, extraordinary information density and ease of operation. The result, verified by biological experimentation, revealed the potential of DNA computation in solving complex programming problem.     

基于三链核酸的DNA计算

一种研究DNA计算的新模型——三链DNA计算模型在本文中提出。此模型是在近年三链核酸的研究成果的基础上建立的。并应用于求解可满足性问题（SAT）,这是一个困难的NP-完全问题。不同于以住的DNA计算方法,基于三链核酸的分子算法通过寡聚脱氧核苷酸（ODN）在RecA蛋白的介导下与同源的双链DNA匹配成三链DNA进行基本的运算,这样可以有效减少计算中的错误。依据分子生物学的实验方法,该算法切实可行并且有效。     

DNA library design for molecular computation.

A novel approach to designing a DNA library for molecular computation is presented. The method is employed for encoding binary information in DNA molecules. It aims to achieve a practical discrimination between perfectly matched DNA oligomers and those with mismatches in a large pool of different molecules. The approach takes into account the ability of DNA strands to hybridize in complex structures like hairpins, internal loops, or bulge loops and computes the stability of the hybrids formed based on thermodynamic data. A dynamic programming algorithm is applied to calculate the partition function for the ensemble of structures, which play a role in the hybridization reaction. The applicability of the method is demonstrated by the design of a twelve-bit DNA library. The library is constructed and experimentally tested using molecular biology tools. The results show a high level of specific hybridization achieved for all library words under identical conditions. The method is also applicable for the design of primers for PCR, DNA sequences for isothermal amplification reactions, and capture probes in DNA-chip arrays. The library could be applied for integrated DNA computing of twelve-bit instances of NP-complete combinatorial problems by multi-step DNA selection in microflow reactors.     

Approaching mathematical model of the immune network based DNA Strand Displacement system

One biggest obstacle in molecular programming is that there is still no direct method to compile any existed mathematical model into biochemical reaction in order to solve a computational problem. In this paper, the implementation of DNA Strand Displacement system based on nature-inspired computation is observed. By using the Immune Network Theory and Chemical Reaction Network, the compilation of DNA-based operation is defined and the formulation of its mathematical model is derived. Furthermore, the implementation on this system is compared with the conventional implementation by using silicon-based programming. From the obtained results, we can see a positive correlation between both. One possible application from this DNA-based model is for a decision making scheme of intelligent computer or molecular robot.     

A new solution for maximal clique problem based sticker model

In this paper, we use stickers to construct a solution space of DNA for the maximal clique problem (MCP). Simultaneously, we also apply the DNA operation in the sticker-based model to develop a DNA algorithm. The results of the proposed algorithm show that the MCP is resolved with biological operations in the sticker-based model for the solution space of the sticker. Moreover, this work presents clear evidence of the ability of DNA computing to solve the NP-complete problem. The potential of DNA computing for the MCP is promising given the operational time complexity of O(nxk).     

DNA计算机的分子生物学研究进展

DNA(脱氧核糖核酸)计算机研究是一个新领域。从字面上看,它既包含DNA研究也包含计算机的研究,因而也包含DNA技术与计算机技术如何交融的研究。1994年,Adleman在Science上报道了首例DNA计算的研究结果;2001年,Benenson等在Nature报道了一种由DNA分子和相应的酶分子构成的、有图灵机功能的可程序试管型DNA计算机,标志着DNA计算机研究的重大进展。DNA计算机最大的特点是超大规模的并行运算能力和潜在的巨大的数据储存能力。目前DNA计算机研究已涉及许多领域,包括生物学、数学、物理、化学、计算机科学和自动化工程等具体应用,是计算概念上的一次革命。DNA计算机的研究大大促进了DNA分子操作技术尤其是在纳米尺度下操作DNA分子的研究速度。从DNA计算机的基本原理、应用形式、与基因组学研究的重要关系等方面总结和评述了相关研究进展。