DNA计算机

脱氧核糖核酸（简称DNA）是生物体内的一种具有双螺旋结构的遗传物质,用DNA可以进行运算,即构成的DNA计算机能很快地求解复杂的问题;以DNA编码为信息的载体,DNA计算机中的输入和输出设备都是DNA的,链用一系列二进制的数代表所求问题中的变量,用DNA中特有的寡核苷酸序列表示这些二进制的数,再将DNA利用分子生物和化学组装技术组装到芯片上,利用DNA杂交化学方法,排除各种代表不正确解的寡核苷酸序列,最后通过聚合酶链式反应（PCR）和各种检测技术读出保留在芯片上的DNA序列,读出的DNA序列所代表的二进制数即为所求问题的解,本文将从DNA运算过程入手,介绍DNA计算机的原理和DNA计算机的若干最新研究进展。     

利用发夹结构分子实现栈式结构的DNA计算模型

为使DNA计算机能像电子计算机一样解决数据的组织与存储问题, 提出了一种利用发夹结构分子实现栈式数据结构的DNA计算模型,描述了数据的存储和组织方式以及元素入栈、 出栈等操作的生物操作过程。经验证, DNA计算模型求解数据的组织问题是可行的, 有助于DNA计算机走向实际应用。     

分子计算机的诞生与现状

介绍了计算机领域的一项最新成果———分子计算机 .分子计算机利用脱氧核糖核酸 (DNA)来进行计算 .腺嘌呤、鸟嘌呤、胞密啶、胸腺密啶 (核苷酸 )在计算中起了重要的作用 .使用限制内切酶、接合酶、转移酶、外切核酸酶、修饰酶来实现计算所需要的各种操作 .介绍了分子计算机完成的第 1个计算———解哈密顿通路问题的方法 ,用这种方法使NP完全问题在很短的时间内就得到解决     

Multi-objective carrier chaotic evolutionary algorithm for DNA sequences design

DNA computing is a new vista of computation, which is of biochemical type. Since each piece of information is encoded in biological sequences, their design is crucial for successful DNA computation. DNA sequence design is involved with a number of design criteria, which is difficult to be solved by the traditional optimization methods. In this paper, the multi-objective carrier chaotic evolution algorithm (MCCEA) is introduced to solve the DNA sequence design problem. By merging the chaotic search base on power function carrier, a set of good DNA sequences are generated. Furthermore, the simulation results show the efficiency of our method.     

Multi-objective carrier chaotic evolutionary algorithm for DNA sequences design

DNA computing is a new vista of computation, which is of biochemical type. Since each piece of information is encoded in biological sequences, their design is crucial for successful DNA computation. DNA sequence design is involved with a number of design criteria, which is difficult to be solved by the traditional optimization methods. In this paper, the multi-objective carrier chaotic evolution algorithm (MCCEA) is introduced to solve the DNA sequence design problem. By merging the chaotic search base on power function carrier, a set of good DNA sequences are generated. Furthermore, the simulation results show the efficiency of our method.     

A novel DNA computing model based on RecA-mediated triple-stranded DNA structure

The field of DNA computing emerged in 1994 after Adleman’s paper was published. Henceforth,a few scholars solved some noted NP-complete problems in this way. And all these methods of DNA computing are based on conventional Watson-Crick hydrogen bond of doublehelical DNA molecule. In this paper, we show that the triple-stranded DNA structure mediated by RecA protein can be used for solving computational problems. Sequence-specific recognition of double-stranded DNA by oligonucleotide-directed triple helix (triplex) formation is used to carry out the algorithm. We present procedure for the 3-vertex-colorability problems. In our proposed procedure, it is suggested that it is possible to solve more complicated problems with more variables by this model.     

利用数组和字符串实现长整数的精确计算

文章阐述了用计算机进行长整数的乘法运算时所遇到的问题以及如何利用数组和字符串来解决这些问题。通过对人工计算过程进行模拟和分析,最终找到一个适合在计算机中实现的算法,即用高级语言来实现长整数的精确计算。     

一种广义分子计算模型在集合覆盖中的应用

在分子计算原理和传统计算机模型基础上,提出了一种新的基于图灵机的广义分子计算模型,又称广义图灵模型,该模型的具体实现不依赖于特定生物技术. 模型继承分子计算大存储高并行的特点,通过时空复杂度转换,在求解NP完全问题上具有通用性. 模型由一台基本图灵机、一个只写带和一条工作带及读写网络这3部分组成,其中只写带和工作带之间存在一种特殊拓扑映射. 通过数据规模为4的集合覆盖问题,证明该算法能在多项式时间内求解集合覆盖问题,验证了算法和模型的有效性.     

DNA计算原理与发展

DNA计算是一种摸拟生物分子DNA的结构并借助分子生物技术进行计算的新方法,为NP完全问题的解决提供了一种全新的途径,具有广阔的应用前景。本文首先介绍了DNA计算的基本思想;然后综述了DNA算例及其模型;指出了DNA计算的应用及目前存在的问题;最后对DNA计算的发展前景进行展望。     

基于J2ME的字符串自动换行算法在手机游戏开发中的实现

随着J2ME在开发移动设备上应用的增多,游戏开发已成为当前的主要应用领域之一.然而,针对在游戏开发中经常需要绘制长字符串的问题,J2ME并没有提供相应的解决方法.对此,通过设计一种切割字符串的算法来解决该问题.实验结果表明此算法是有效的.     

Solid phase based DNA solution of the coloring problem

DNA computing has the potential to tackle computationally difficult problems that have real-world implications.The parallel search capabilities of DNA make it a valuable tool for approaching intractable computational problems,for which conventional computers have limited potentials.Up to now,many accomplishments have been achieved to improve its performance and increase its reliability.In this paper,the coloring problem has been solved by means of molecular biology techniques.The coloring problem is a well-known NP-complete problem.This work represents further evidence for the ability of DNA computing to solve NP-complete problems.     

Genetic algorithm in DNA computing： A solution to the maximal clique problem

Genetic algorithm is one of the possible ways tobreak the limit of brute-force method in DNA computing.Using the idea of Darwinian evolution, we introduce a geneticDNA computing algorithm to solve the maximal clique prob-lem. All the operations in the algorithm are accessible withtoday‘s molecular biotechnoiogy. Our computer simulationsshow that with this new computing algorithm, it is possible toget a solution from a very small initial data pool, avoidingenumerating all candidate solutions. For randomly generatedproblems, genetic algorithm can give correct solution withina few cycles at high probability. Although the current speedof a DNA computer is slow compared with silicon computers,our simulation indicates that the number of cycles needed inthis genetic algorithm is approximately a linear function ofthe number of vertices in the network. This may make DNAcomputers more powerfully attacking some hard computa-tional problems.     

A membrane evolutionary algorithm for DNA sequence design in DNA computing

DNA sequence design has a crucial role in successful DNA computation,which has been proved to be an NP-hard(non-deterministic polynomial-time hard) problem.In this paper,a membrane evolutionary algorithm is proposed for the DNA sequence design problem.The results of computer experiments are reported,in which the new algorithm is validated and out-performs certain known evolutionary algorithms for the DNA sequence design problem.     

DNA computing model based on lab-on-a-chip and its application on solving the timetabling problem

The essential characteristic of DNA computation is its massive parallelism in obtaining and managing information. With the development of molecular biology technique, the field of DNA computation has made a great progress. By using an advance technique of biochip, laboratory-on-a-chip, in this paper a new DNA computing model was presented to solve a simple timetabling problem, which is a special version of the optimization problems and plays an important role in education. With a simulated biological experiment, the result suggested that DNA computation with lab-on-a-chip has the potential to solve a real complex timetabling problem.     

基于k-臂分子求解最短路径的DNA计算模型

为有效求解最短路径问题, 避免传统算法计算量大、 求解时间长的问题, 充分发挥DNA(Deoxyribo Nuclec Acid)计算的并行性在求解复杂计算问题的优势, 提出一种基于k-臂分子和粘贴计算求解最短路径问题的DNA计算模型, 阐述了顶点、边及权值的编码方案, 描述了求解最短路径的DNA算法, 经验证, 该模型对求解最短路径问题是有效的。     

A new approach based on PSO algorithm to find good computational encoding sequences

Computational encoding DNA sequence design is one of the most important steps in molecular computation. A lot of research work has been done to design reliable sequence library. A revised method based on the support system developed by Tanaka et al. is proposed here with different criteria to construct fitness function. Then we adapt particle swarm optimization (PSO) algorithm to our encoding problem. By using the new algorithm, a set of sequences with good quality is generated. The result also shows that our PSO-based approach could rapidly converge at the minimum level for an output of the simulation model. The celerity of the algorithm fits our requirements.     

A new DNA algorithm to solve graph coloring problem

Using a small quantity of DNA molecules and little experimental time to solve complex problems successfully is a goal of DNA computing. Some NP-hard problems have been solved by DNA computing with lower time complexity than conventional computing. However, this advantage often brings higher space complexity and needs a large number of DNA encoding molecules. One example is graph coloring problem. Current DNA algorithms need exponentially increasing DNA encoding strands with the growing of problem size. Here we propose a new DNA algorithm of graph coloring problem based on the proof of four-color theorem. This algorithm has good properties of needing a relatively small number of operations in polynomial time and needing a small number of DNA encoding molecules (we need only 6R DNA encoding molecules if the number of regions in a graph is R).     

A new DNA algorithm to solve graph coloring problem

Using a small quantity of DNA molecules and little experimental time to solve complex problems successfully is a goal of DNA computing. Some NP-hard problems have been solved by DNA computing with lower time complexity than conventional computing. However, this advantage often brings higher space complexity and needs a large number of DNA encoding molecules. One example is graph coloring problem. Current DNA algorithms need exponentially increasing DNA encoding strands with the growing of problem size. Here we propose a new DNA algorithm of graph coloring problem based on the proof of four-color theorem. This algorithm has good properties of needing a relatively small number of operations in polynomial time and needing a small number of DNA encoding molecules (we need only 6R DNA encoding molecules if the number of regions in a graph is R).     

A new approach based on PSO algorithm to find good computational encoding sequences

Computational encoding DNA sequence design is one of the most important steps in molecular computation. A lot of research work has been done to design reliable sequence library. A revised method based on the support system developed by Tanaka et al. is proposed here with different criteria to construct fitness function. Then we adapt particle swarm optimization (PSO) algorithm to our encoding problem. By using the new algorithm, a set of sequences with good quality is generated. The result also shows that our PSO-based approach could rapidly converge at the minimum level for an output of the simulation model. The celerity of the algorithm fits our requirements.     

DNA芯片在最短公共超串问题中的应用

DNA芯片技术是近年来生命科学与信息科学的新兴研究领域，其突出特点在于它的高度并行性、多样化、微型化以及自动化，最短公共超串问题是计算机科学中的NP-完全问题．笔者在DNA计算和DNA芯片基础上，提出了基于DNA芯片解决最短公共超串问题的DNA计算新模型．该模型可对信息高度并行获取，并且具有操作易自动化的优点．