【作者】 王延峰；

【导师】 许进；

【作者基本信息】 华中科技大学 ， 系统分析与集成， 2007， 博士

【摘要】 DNA计算是以DNA分子为载体,利用DNA杂交反应的巨大并行性特点而进行计算的一种自然计算模式。编码问题是DNA计算机研制中的核心问题之一。从分子生物学角度来看,DNA序列自身的物理化学属性决定了DNA编码序列的存在形式;而DNA编码序列的热力学属性则是杂交反应的动力源泉。基于此,本文主要围绕DNA序列的物理化学属性以及热动力学特性进行DNA计算中的编码理论的研究与设计,主要研究内容如下:详细地讨论了DNA计算中的编码问题;详细地介绍了DNA分子的物理化学性质、杂交反应的热力学基础以及相关热力学参数的计算方法。提出了一种针对DNA计算的编码序列优化设计方案。该方案在综合考虑DNA计算中编码序列的约束条件的基础上,根据约束条件之间的相互制约关系,采用整体优化的思想,首先将各约束条件进行归类;然后依据各约束条件的计算时间复杂度和约束强弱程度进行优化组合排序,采用随机产生-实时过滤算法产生计算所需数目的DNA编码序列。比较结果表明,该优化设计方案的各项评价指标均优于以往文献提供的方法。在综合考虑计算编码序列生物约束条件之间的制约关系的基础上,提出了一种基于统计学原理的、无需实验就可确定各评价指标的权重系数的方法:组合权重方法,并据此建立了一套DNA编码序列系统评价模型,仿真结果表明该评价模型可以对编码序列集合进行合理、客观的评价。另外,该系统评价模型对采用演化策略进行DNA编码序列的设计研究时构造适应度函数具有重要的指导意义。由于在一个随机产生的DNA序列集合中寻找满足相关物理化学和热力学约束条件的最大编码数问题可以映射为求解图的最大团问题,即是一NP困难问题,于是,采用启发式算法来解决该问题也就成了必然选择。基于此,尝试采用一种基于改进的Hopfield神经网络算法的DNA编码序列设计方法。仿真结果显示,该方法可用于对随机产生的DNA序列集合进行评估和预过滤,对最终得到好的DNA编码序列具有指导和参考作用。提出了一种基于模拟退火遗传算法的计算编码序列设计方法。该算法既有遗传算法的全局搜索能力,又兼有模拟退火算法的局部快速收敛性。仿真结果显示,该方法对DNA编码序列设计是有效的,可生成质量较好的DNA编码序列。讨论了粒子群优化算法在DNA计算中的编码问题上的应用。提出了一种离散问题连续化策略,使得只能求解连续优化问题的标准粒子群优化算法可用于解决属于离散问题的DNA于编码序列设计问题;还提出了一种用于DNA编码序列设计的四进制离散粒子群优化算法。仿真结果表明,这两种算法对于较小规模的编码问题具有很好的效果,能快速有效地进行DNA编码序列设计。更多还原

【Abstract】 DNA computing is a new computational paradigm that uses DNA molecules as information storage materials and hybridization reactions as information processing operators due to massive parallelism and huge memory capacity. Computational codeword design is one of the crucial problems in DNA computing. From the perspective of molecular biology, the existence of codeword is attributed by the physicochemical properties of DNA sequence; Thermodynamic properties of DNA sequences govern the kinetics of hybridization and ligation. Therefore, this thesis focus on designing computational codeword based on physicochemical properties, as well as the thermodynamic properties of DNA sequences to make the molecular computation more reliable. The main research works are as follows:Besides the encoding problem of DNA computing, both the physicochemical properties of DNA molecule and the thermodynamics of hybridization are discussed in detail. Additionally, some usual calculation methods for the correlative thermodynamic parameters are also introduced.An optimized approach for generating a set of computational codeword is presented. In this method, after studying more systematically the thermodynamic and physicochemical constrains of DNA encoding sequences and exploring the inherent connection among these constrains, the criterions are classified into two classes, and the order of criterions is organized by computational time complexity and constraint intensity. Then the desired number of computational codeword is generated by using random generate and real-time filter algorithm. The comparison results show the performance of this approach outperforms the existing DNA sequence design systems, especially in preventing sequence self-complementary from forming secondary structure and keeping the uniform melting temperature among sequences.After investigating relationship among the universal constraints for the design of computational codeword, we present a new combined weight method to determine the objective index weight in the synthetic evaluation system for computational codeword based on statistics without experiment. The simulation results show that this system evaluation model can not only provide objective and stability evaluation to a set of computational codeword, but guide us to design fitness function when evolutionary algorithms are used to the design of codeword for DNA computing.Because the problem of finding the maximum number of computational codeword in a generated randomly set of DNA sequences can be mapped onto solution to a graph maximum clique problem and is NP-hard. Thus, utilizing meta-heuristic algorithm to find an optimal or near optimal solution and predestinating whether the computational codeword in an arbitrary generated randomly set are enough for the following controllable computation or not is required. So we present an improved Hopfield neural network algorithm to solve this problem. The simulation results show that the proposed method is useful for user to select an appropriate set of candidate DNA sequences to filter and obtain the good computational codeword finally.Aim at satisfying the maximum unique of the codeword and the minimum rate of crossover, we present a new computational codeword design method based on Hybridized Simulated Annealing Algorithm and Genetic Algorithms. This method possesses both the global searching ability of GAs and the local rapid convergence of SA algorithm, and the efficiency improved. The simulation results show that the proposed method is effective to generate high quality computational codeword.The design of computational codeword based on particle swarm optimization is discussed. We propose strategy for converting the discrete problem into the continuous optimization problems so as to the standard particle swarm optimization algorithm could be used to address in the design of computational codeword, which belongs to discrete problem. Besides, a new methodology based on Quarter-Discrete Particle Swarm Optimization is also developed to optimize DNA encoding. Simulation results show that our two PSO-based approaches are effective for the small scale encoding problem, and could rapidly converge at at the minimum level for an output of the simulation model.更多还原