文档介绍：华中科技大学
博士学位论文
仿生型DNA计算编码算法研究
姓名:肖建华
申请学位级别:博士
专业:系统分析与集成
指导教师:许进
20080604
华中科技大学博士学位论文
摘要
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 序列的设计问题。在算法中,每一
I
华中科技大学博士学位论文
代交叉变异操作和外部存档更新之后,该算法从外部存档集合中随机选择部分个体,
对这些拷贝的个体进行幂函数载波混沌搜索, 以产生更多非支配解。同传统的优化算
法相比,如:粒子群算法(PSO),遗传算法(GA),权重法等,该算法不但能避免选取
权重的困难,而且能够易于逃脱局部最优,增强了算法的搜索能力。仿真结果表明,
该算法是有效的,能够生成质量较好的 DNA 编码序列。
最后讨论了 DNA 编码在可满足性问题中的应用,并提出了基于巨磁电阻检测
(GMR)技术芯片的 DNA 计算模型。与传统的检测技术相比,GMR 芯片具有结构
简单、无需标记、检测时间短、检测信号易处理等特点。本文在这一新型的 DNA 芯
片和新兴学科 DNA 计算的基础上,提出了 GMR 型可满足性问题 DNA 计算模型,给
出了相应的具体算例。与此同时,利用改进的量子进化算法,产生了算例中所需要的
DNA 编码序列。通过使用 Primer Premier 测试,结果表明,该编码能有效的避免
非特异性杂交。
关键词:膜计算;DNA 编码;多目标进化算法;量子进化算法;混沌优化;
GMR 技术
II
华中科技大学博士学位论文
Abstract
puting is a putation paradigm with DNA molecules and enzymes
as “carrier”, and biochemistry trials as “information processing instruments”. In recent
years, puting has been extensively researched in recent years. Since information
is encoded in DNA sequen