【作者】 肖建华；

【导师】 许进；

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

【摘要】 DNA计算是以DNA分子和生物酶等为载体,以生化反应作为“信息处理工具”的一种新的计算模式。近年来,DNA计算得到了广泛的研究和发展。由于DNA计算中的信息需编码成生物序列,有效的编码设计能够提高DNA计算的可靠性。然而DNA编码序列的设计需要同时考虑物理化学属性以及热动力学特性等约束条件,传统的优化方法很难对其进行求解。鉴于DNA编码问题的重要性和复杂性,本文主要围绕DNA计算的编码设计问题,提出了仿生型DNA编码设计算法,并给出了DNA编码在GMR型DNA计算中的应用。本文的主要工作包括:详细讨论了论文的研究背景和意义,系统的介绍了与本文有关的研究概况,以及DNA计算所面临的问题,从而提出了本文所研究的主要问题-编码问题,建立了DNA编码约束的数学模型,并给出了DNA编码问题的适应度函数。膜计算是从生物细胞以及由细胞所组成的组织和器官的功能与结构中抽象出来的计算模型,具有良好的分布式、并行性、非确定性等优点。虽然膜计算已经取得了很多好的成果,但在DNA序列编码优化方面,鲜有膜计算对此的研究成果。基于此,本文构造了DNA序列设计膜系统,提出了字符串优化膜系统DNA序列编码算法。仿真结果表明,该方法对DNA编码序列设计是有效的,可以生成好的DNA编码序列。量子进化算法是将量子计算和进化计算相结合的一种新的优化算法,近年来已经被广泛的研究和应用。本文在这一新颖的算法基础上,提出了改进的量子进化算法DNA编码序列设计方法。在文中,通过引入一种新的量子比特位表示—量子角,并使用粒子群算法自动更新量子角大小。与此同时,为了克服粒子群算法后期易于陷入局部最优解的不足,本文将Tent映射混沌搜索引入到量子进化算法中,提出了一种新的混合量子进化算法,并将其应用于DNA编码序列优化问题。通过融入粒子群算法和Tent映射,该算法不仅能够具有快速的收敛性,而且也能克服算法后期易陷入局部最优解的不足。对DNA序列编码问题进行仿真,结果表明,有效的DNA序列能够获得。针对DNA编码优化是一个多目标优化问题,传统的加权法存在权值选取困难的不足,本文将幂函数载波混沌搜索融入到强度Pareto进化算法中,提出了多目标载波混沌进化算法(MCCEA),并将其应用于求解DNA序列的设计问题。在算法中,每一代交叉变异操作和外部存档更新之后,该算法从外部存档集合中随机选择部分个体,对这些拷贝的个体进行幂函数载波混沌搜索,以产生更多非支配解。同传统的优化算法相比,如:粒子群算法(PSO),遗传算法(GA),权重法等,该算法不但能避免选取权重的困难,而且能够易于逃脱局部最优,增强了算法的搜索能力。仿真结果表明,该算法是有效的,能够生成质量较好的DNA编码序列。最后讨论了DNA编码在可满足性问题中的应用,并提出了基于巨磁电阻检测(GMR)技术芯片的DNA计算模型。与传统的检测技术相比,GMR芯片具有结构简单、无需标记、检测时间短、检测信号易处理等特点。本文在这一新型的DNA芯片和新兴学科DNA计算的基础上,提出了GMR型可满足性问题DNA计算模型,给出了相应的具体算例。与此同时,利用改进的量子进化算法,产生了算例中所需要的DNA编码序列。通过使用Primer Premier 5.0测试,结果表明,该编码能有效的避免非特异性杂交。更多还原

【Abstract】 DNA computing is a novel computation paradigm with DNA molecules and enzymes as“carrier”, and biochemistry trials as“information processing instruments”. In recent years, DNA computing has been extensively researched in recent years. Since information is encoded in DNA sequences, the design of DNA sequences is crucial for successful DNA computation. DNA sequence design need meet simultaneously several physical, chemical and logical constraints, which is difficult to be solved by the traditional optimization methods. Therefore, this thesis focus on DNA sequences design based on various Bio-inspired algorithm to make the molecular computation more reliable. The main research works are as follows:The first part details the background, the aim and the meaning of study, surveys related domestic and foreign researches, proposes the main work of our study, and interprets the DNA encoding problem.A novel algorithm based on membrane computing for DNA sequences design is proposed. Membrane computing, also called P systems, is a branch of natural computing, which is a class of distributed non-deterministic parallel computing devices of a biochemical type. Membrane computing has been used to solve various optimization hard problems, but it hasn’t been employed so far in DNA encoding. In the paper, the new membrane system is constructed, and is firstly used to solve the DNA sequence optimization problem. By using the novel algorithm, a set of good DNA sequences are generated. Furthermore, the simulation results show the efficiency of our method.A novel quantum chaotic swarm evolutionary algorithm (QCSEA) is presented, and is firstly used to solve the DNA sequence optimization problem. Quantum evolutionary algorithm is a novel algorithm based on the quantum computation and evolutionary computation, and has been extensively researched in the recent years. In the paper, a new definition of Q-bit expression called quantum angle is introduced, and the particle swarm optimization is employed to update the quantum angles automatically. By merging the particle swarm optimization and the chaotic search, the hybrid algorithm can not only avoid the disadvantage of easily getting into the local optional solution in the later evolution period, but also keep the rapid convergence performance. And the simulation results demonstrate that the proposed quantum chaotic swarm evolutionary algorithm is valid and outperforms the genetic algorithm and conventional evolutionary algorithm for DNA encoding.DNA sequence design relates to a number of design criteria, which is difficult to select the proper weight values for each vriterion by the weight methods. In this paper, the carrier chaotic searching was merged into multi-objective evolutionary algorithm, and a multi-objective carrier chaotic evolutionary algorithm (MCCEA) for designing DNA sequences was developed. In each generation of MCCEA algorithm, carrier chaotic search is performed on the copy of several individuals chosen randomly from the external archive to obtain new non-dominated solutions. The more non-dominated solutions will be produced by ergodic regularity of chaos. Compared with the traditional algorithm, such as PSO algorithm, GA, weight methods, and so on, our algorithm not only avoids the difficulty of selecting the proper weight values for each criterion, but also escapes from local optimal solution. The simulation results show that the comprehensive performance of multi-objective carrier chaotic evolutionary algorithm is improved by merging chaos in MOEA algorithm.The application of DNA sequecse design is discussed in this paper too. The DNA computation based on Giant Magnetoresistance (GMR) Effect Chip is proposed. Compared with traditional gene assay technology, GMR chip has the simple construction, label-free feature, time-saving detection speed, and conveniently processed information. In the paper, based on the GMR chip and DNA computing theory, a new DNA computing method to solve satisfiability problem is proposed. The DNA sequences of a computational example are generated by quantum chaotic swarm evolutionary algorithm. By using the Primer Premier 5.0, these DNA sequences are tesitified that they are good for avoiding the non-specific hybridization.更多还原