地图着色问题的粘贴DNA算法

提出多级分离的概念,给出一个多级分离装置的模型,并介绍粘贴模型中的多级分离操作、将地图着色问题转化为可满足性问题、基于粘贴模型的巨大并行性及多级分离的优势,提出解决该问题的粘贴DNA算法。通过一个实例给出实验操作步骤,并对生化反应过程进行模拟,得出具体的着色方案,从而证明了该多级分离装置的有效性以及该算法的可行性。     

聚合物混凝土(PC)在机械行业的应用及分析

根据作者对聚合物混凝土的研究，提出改善其性能的一些看法，以求扩大ＰＣ材料在机械行业的应用范围。     

基于粘贴系统求解无向图最短路径问题的DNA计算模型

提出了用粘贴系统求解赋权无向图中固定端点最短路径的DNA算法。该算法首先将无向图中每条边用两条方向相反的有向边代替,将无向图转化为有向图,同时利用粘贴系统的巨大并行性得到两端点间的所有路径,最后通过探针、电泳等分子生物技术手段获得最短路径,并通过实例说明算法的可行性。     

基于批分离实验的最大独立集问题DNA算法

根据解决最大独立集问题的需要,讨论了简化的粘贴模型,该模型只由单链DNA的存储链和分离板组成.以分离实验为基础提出了批分离实验和生化操作过程,该实验可以快速分离存储链.基于批分离实验设计了最大独立集问题的DNA算法,并给出其生化实现过程:先形成所有顶点子集的初始解空间;接着用批分离实验对每个顶点进行检测,筛选全部满足不相邻要求的顶点子集,从而得到全部独立集;然后通过电泳实验得到全部最大独立集;最后通过检测实验输出实验结果.讨论并证明了算法的正确性和复杂性,算法的操作次数是线性的,通过仿真实验说明了算法的有效性和可行性.     

Solve the partitioning problem by sticker model in DNA computing

The aim of this work is to solve the partitioning problem, the most canonical NP-complete problem containing numerical parameters, within the sticker model of DNA computing. We firstly design a parallel program for addition, and then give a program to calculate the subset sums of a set. At last, a program for partitioning is given, which contains the former programs. Furthermore, the correctness of each program is proved in this paper.     

求解最大完全子图的一种DNA算法

最大完全子图是图论中一个重要的问题。粘贴和删除模型是DNA计算的两个基本计算模型。利用改进的粘贴和删除模型给出求解最大完全子图的DNA算法。     

Sticker DNA computer model ——PartⅡ: Application

Sticker model is one of the basic models in the DNA computer models. This model is coded with sin-gle-double stranded DNA molecules. It has the following advantages that the operations require no strands extension and use no enzymes; What抯 more, the materials are reusable. Therefore, it arouses attention and interest of scientists in many fields. In this paper, we extend and improve the sticker model, which will be definitely beneficial to the construction of DNA computer. This paper is the second part of our series paper, which mainly focuses on the application of sticker model. It mainly consists of the following three sections: the matrix representation of sticker model is first presented; then a brief review of the past research on graph and com-binatorial optimization, such as the minimal set covering problem, the vertex covering problem, Hamiltonian path or cycle problem, the maximal clique problem, the maximal independent problem and the Steiner spanning tree problem, is described; Finally a DNA algorithm for the graph iso-morphic problem based on the sticker model is given.     

Sticker DNA computer model ——Part Ⅰ: Theory

Sticker model is one of the basic models in the DNA computer models. This model is coded with single-double stranded DNA molecules. It has the following advantages that the operations require no strands extension and use no enzymes; What‘s more, the materials are reusable.Therefore it arouses attention and interest of scientists in many fields. In this paper, we will systematically analyze the theories and applications of the model, summarize other scientists‘ contributions in this field, and propose our research results. This paper is the theoretical portion of the sticker model on DNA computer, which includes the introduction of the basic model of sticker computing. Firstly, we systematically introduce the basic theories of classic models about sticker computing; Secondly, we discuss the sticker system which is an abstract computing model based on the sticker model and formal languages; Finally, extend and perfect the model, and present two types of models that are more extensive in the applications and more perfect in the theory than the past models: one is the so-called k-bit sticker model, the other is full-message sticker DNA computing model.     

基于粘贴系统求解TSP问题

旅行商问题，简称为TSP问题，是困难的NP完全问题，在工程实践中具有广泛的应用。利用常规的计算方法求解这个问题，计算所需的时间是随着问题规模的增大以指数形式增加的，因而无法有效的解决此类问题。DNA计算是一种新兴的计算方式，粘贴系统模型是其中基于粘贴运算的一种DNA计算的抽象模型。通过将旅行商问题转化为求赋权图中权值最小的Hamilton圈，利用粘贴系统模型的巨大并行性，可以有效的求解旅行商问题。     

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

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