基于三链核酸的DNA计算

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

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

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

Solving the SAT problem using a DNA computing algorithm based on ligase chain reaction

A new DNA computing algorithm based on a ligase chain reaction is demonstrated to solve an SAT problem. The proposed DNA algorithm can solve an n-variable m-clause SAT problem in m steps and the computation time required is O (3m+n). Instead of generating the full-solution DNA library, we start with an empty test tube and then generate solutions that partially satisfy the SAT formula. These partial solutions are then extended step by step by the ligation of new variables using Taq DNA ligase. Correct strands are amplified and false strands are pruned by a ligase chain reaction (LCR) as soon as they fail to satisfy the conditions. If we score and sort the clauses, we can use this algorithm to markedly reduce the number of DNA strands required throughout the computing process. In a computer simulation, the maximum number of DNA strands required was 2(0.48n) when n=50, and the exponent ratio varied inversely with the number of variables n and the clause/variable ratio m/n. This algorithm is highly space-efficient and error-tolerant compared to conventional brute-force searching, and thus can be scaled-up to solve large and hard SAT problems.     

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

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

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).     

A DNA solution of SAT problem by a modified sticker model

Among various DNA computing algorithms, it is very common to create an initial data pool that covers correct and incorrect answers at first place followed by a series of selection process to destroy the incorrect ones. The surviving DNA sequences are read as the solutions to the problem. However, algorithms based on such a brute force search will be limited to the problem size. That is, as the number of parameters in the studied problem grows, eventually the algorithm becomes impossible owing to the tremendous initial data pool size. In this theoretical work, we modify a well-known sticker model to design an algorithm that does not require an initial data pool for SAT problem. We propose to build solution sequences in parts to satisfy one clause in a step, and eventually solve the whole Boolean formula after a number of steps. Accordingly, the size of data pool grows from one sort of molecule to the number of solution assignments. The proposed algorithm is expected to provide a solution to SAT problem and become practical as the problem size scales up.     

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

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

A data-driven model of the generation of human EEG based on a spatially distributed stochastic wave equation

We discuss a model for the dynamics of the primary current density vector field within the grey matter of human brain. The model is based on a linear damped wave equation, driven by a stochastic term. By employing a realistically shaped average brain model and an estimate of the matrix which maps the primary currents distributed over grey matter to the electric potentials at the surface of the head, the model can be put into relation with recordings of the electroencephalogram (EEG). Through this step it becomes possible to employ EEG recordings for the purpose of estimating the primary current density vector field, i.e. finding a solution of the inverse problem of EEG generation. As a technique for inferring the unobserved high-dimensional primary current density field from EEG data of much lower dimension, a linear state space modelling approach is suggested, based on a generalisation of Kalman filtering, in combination with maximum-likelihood parameter estimation. The resulting algorithm for estimating dynamical solutions of the EEG inverse problem is applied to the task of localising the source of an epileptic spike from a clinical EEG data set; for comparison, we apply to the same task also a non-dynamical standard algorithm.     

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

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

Maximum entropy analysis of oversampled data problems

An algorithm for the solution of the Maximum Entropy problem is presented, for use when the data are considerably oversampled, so that the amount of independent information they contain is very much less than the actual number of data points. The application of general purpose entropy maximisation methods is then comparatively inefficient. In this algorithm the independent variables are in the singular space of the transform between map (or image or spectrum) and data. These variables are much fewer in number than either the data or the reconstructed map, resulting in a fast and accurate algorithm. The speed of this algorithm makes feasible the incorporation of recent ideas in maximum entropy theory (Skilling 1989 a; Gull 1989). This algorithm is particularly appropriate for the exponential decay problem, solution scattering, fibre diffraction, and similar applications.     

多维背包问题的DNA计算

提出了一种基于DNA计算的求解多维背包问题的算法,该算法分两个阶段执行,第一个阶段采用试管方法,分别求出满足各个约束方程的可行域;第二个阶段采用表面方法,对第一个阶段求出的多个可行域取交集,即得满足整个约束方程组的可行域,再比较该可行域中各可行解对应的目标函数值,进而得到最优解。并通过实例分析验证了该算法的有效性和正确性,该算法将试管方法和表面方法结合使用,充分利用了两种方法各自的优点。     

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.     

基于模拟退火法由脑磁图推测电流偶极子参数

利用模拟退火（Ｓｉｍｕｌａｔｅｄ Ａｎｎｅａｌｉｎｇ） 算法,由脑磁图（ ＭＥＧ） 数据反演脑内作为磁源的单电流偶极子参数,可以得到理想的结果。在上述工作的基础上,对脑内多电流偶极子参数的反演,则呈现如下状况：即以少于实际源数目的偶极子为源假设反演,目标函数得不到极小优化。反之,目标函数可以得到极小优化, 但出现多余的伪偶极子, 且这些伪偶极子在多次不同条件的反演结果中,处于不稳定状态。若将多次反演结果中处于不稳定状态的偶极子作为伪偶极子的判据而将其排除,则可以得到一种判断磁源偶极子数目的方法     

Is optimal solution of every NP-complete or NP-hard problem determined from its characteristic for DNA-based computing

Cook's Theorem [Cormen, T.H., Leiserson, C.E., Rivest, R.L., 2001. Introduction to Algorithms, second ed., The MIT Press; Garey, M.R., Johnson, D.S., 1979. Computer and Intractability, Freeman, San Fransico, CA] is that if one algorithm for an NP-complete or an NP-hard problem will be developed, then other problems will be solved by means of reduction to that problem. Cook's Theorem has been demonstrated to be correct in a general digital electronic computer. In this paper, we first propose a DNA algorithm for solving the vertex-cover problem. Then, we demonstrate that if the size of a reduced NP-complete or NP-hard problem is equal to or less than that of the vertex-cover problem, then the proposed algorithm can be directly used for solving the reduced NP-complete or NP-hard problem and Cook's Theorem is correct on DNA-based computing. Otherwise, a new DNA algorithm for optimal solution of a reduced NP-complete problem or a reduced NP-hard problem should be developed from the characteristic of NP-complete problems or NP-hard problems.     

0-1整数规划问题的半自动化DNA计算模型

对一般的0—1整数规划问题提出了一种半自动化的DNA计算模型。首先产生所给定的0—1整数规划问题的所有可能解,然后设置对应于0—1整数规划问题的约束不等式的探针,利用这些探针设计半自动化装置对所有可能解进行自动分离,最终找出0—1整数规划问题的解。该模型的最大优点在于具有自动化的特点;同时,从理论上来讲,该模型适合含有任意变量的任意0—1整数规划问题的求解。     

A P system and a constructive membrane-inspired DNA algorithm for solving the Maximum Clique Problem

We present a P system with replicated rewriting to solve the Maximum Clique Problem for a graph. Strings representing cliques are built gradually. This involves the use of inhibitors that control the space of all generated solutions to the problem. Calculating the maximum clique for a graph is a highly relevant issue not only on purely computational grounds, but also because of its relationship to fundamental problems in genomics. We propose to implement the designed P system by means of a DNA algorithm. This algorithm is then compared with two standard papers that addressed the same problem and its DNA implementation in the past. This comparison is carried out on the basis of a series of computational and physical parameters. Our solution features a significantly lower cost in terms of time, the number and size of strands, as well as the simplicity of the biological implementation.     

DNA polymerase programmed with a hairpin DNA incorporates a multiple-instruction architecture into molecular computing

Parallelism is one of the major advantages of molecular computation. A large number of data encoded in DNA molecules can be processed simultaneously by molecular biology techniques, although only a single set of instructions has been implemented in a solution. We have developed a computing machine, called the "whiplash" machine, which is made of DNA polymerase and a hairpin DNA. This machine simulates a finite state machine, executing its own instructions encoded in the DNA moiety, and would thus be applicable to multiple-instruction operation in a solution. In the present study, we explored the feasibility of this novel type of parallelism by applying the whiplash machine in a computation of the directed Hamiltonian path problem. The possible paths in a given graph were represented with different instruction sets, which were then implemented separately by whiplash machines in a test tube. After an autonomous operation of the machines, only the machine that implemented the instruction set corresponding to the Hamiltonian path was recovered from the tube. On the basis of the efficiency of machine operation, which was experimentally determined, 10(10) different instruction sets could be implemented simultaneously in a 1-ml solution.     

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.     

An evolutionary Monte Carlo algorithm for predicting DNA hybridization

Many DNA-based technologies, such as DNA computing, DNA nanoassembly and DNA biochips, rely on DNA hybridization reactions. Previous hybridization models have focused on macroscopic reactions between two DNA strands at the sequence level. Here, we propose a novel population-based Monte Carlo algorithm that simulates a microscopic model of reacting DNA molecules. The algorithm uses two essential thermodynamic quantities of DNA molecules: the binding energy of bound DNA strands and the entropy of unbound strands. Using this evolutionary Monte Carlo method, we obtain a minimum free energy configuration in the equilibrium state. We applied this method to a logical reasoning problem and compared the simulation results with the experimental results of the wet-lab DNA experiments performed subsequently. Our simulation predicted the experimental results quantitatively.     

The evolution of cellular computing: nature's solution to a computational problem

How do cells and nature 'compute'? They read and 'rewrite' DNA all the time, by processes that modify sequences at the DNA or RNA level. In 1994, Adleman's elegant solution to a seven-city directed Hamiltonian path problem using DNA launched the new field of DNA computing, which in a few years has grown to international scope. However, unknown to this field, two ciliated protozoans of the genus Oxytricha had solved a potentially harder problem using DNA several million years earlier. The solution to this problem, which occurs during the process of gene unscrambling, represents one of nature's ingenious solutions to the problem of the creation of genes. RNA editing, which can also be viewed as a computational process, offers a second algorithm for the construction of functional genes from encrypted pieces of the genome.