dna计算核酸编码优化与算法设计

《dna计算核酸编码优化与算法设计》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、ADissertationSubmittedinPartialFulfillmentoftheRequirementsfortheDegreeofDoctorofPhilosophyinEngineeringDNAEncodingOptimizationandNucleicAcidSequencesDesignAlgorithmforDNAComputingPh.D.Candidate:ZhangKaiMajor:SystemsAnalysisandIntegrationSupervisor:Prof.XuJinHuazhongUniversityo

2、fScience&TechnologyWuhan430074,P.R.ChinaJune,2008独创性声明本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除文中已经标明引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。学位论文作者签名：日期：年月日学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有权保留并向国家有关部门或机构送交论文的复印件和电子版，允

3、许论文被查阅和借阅。本人授权华中科技大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。保密□，在年解密后适用本授权书。本论文属于不保密□。（请在以上方框内打“√”）学位论文作者签名：指导教师签名：日期：年月日日期：年月日华中科技大学博士学位论文摘要DNA计算是一种以DNA分子作为计算介质，以生物化学反应作为计算工具的一种新型计算方法。凭借着极大的存储密度和高度并行性，这种基于生物分子的计算模式，在求解复杂的组合优化NP完全问题时显示出了极大潜力。DNA计算首先是对核酸序列进行编码，将现

4、实问题映射到核酸分子上，然后通过生物试验获得代表问题解的核酸分子。核酸编码质量的优劣决定了DNA计算的效率，核酸编码数量的多少决定了DNA计算可求解问题的规模，因此核酸编码是DNA计算研究中的重要课题。本文研究了DNA计算中核酸编码理论及其算法的设计，主要研究工作如下：(1)DNA计算中编码质量、编码数量、序列长度与DNA计算的可靠性、有效性、可扩充性密切相关，选取适当的DNA编码约束及约束强度是提高DNA计算设计效率的关键，DNA编码问题是一个极具挑战性的多目标组合优化问题。本文首先分析了各编码约束对编码质量的影响，进而对DNA编码的约束条件进行归

5、类。通过将DNA编码问题和图的最大独立集问题进行类比，对DNA编码问题的复杂性进行了分析。对基于汉明距离和基于最小自由能这两类DNA编码方法进行了类比和研究，分析了两类方法限制核酸非特异性杂交的完备性及计算量，为DNA计算编码方法的选择及其参数的确定提供了理论支持。(2)DNA分子杂交二级结构的多样性，使得计算其最小自由能的时间复杂度非常高，当编码约束条件较严格时，很难在有效的时间内设计出满意数量的DNA序列。提高DNA分子二级结构的预测精度和自由能的计算效率是热力学DNA编码算法设计的难点和关键。本文研究了DNA分子杂交自由能变化与双链DNA分子二

6、级结构稳定性的关系，提出了一种基于热力学的启发式随机搜索DNA序列设计算法，该算法采用Nearest-Neighbors热力学模型，通过对DNA分子杂交的二级结构进行预测，选择满足用户设定的最小自由能约束的DNA序列，从而有效避免了DNA计算中DNA分子的非特异性杂交。同其它随机搜索DNA序列设计算法相比，该算法首先排除不满足解链温度的候选DNA序列，然后用贪婪算法计算DNA序列的自由能，并逐步将不满足自由能约束的候选序列转化为可行解，提高了DNA序列的设计效率。通过和其它算法提供的DNA序列进行比较和分析，证实了算法可产生热力学性质更稳定的DNAI

7、华中科技大学博士学位论文序列，验证了算法的有效性。(3)当前各种DNA序列设计算法适用的编码约束有限，对不同的DNA计算模型不具备通用性；并且难以高效的设计出满足约束的最大DNA序列集合，无法求解大规模的DNA计算问题实例。本文针对DNA编码设计的这些难点，提出了隐枚举核酸序列设计算法，以提高DNA计算的可扩充性，求解更大规模的计算问题。通过将编码约束转换为整型线性规划的条件不等式对DNA序列进行约束，灵活适用于各种编码约束，可满足各种DNAn计算模型对DNA编码的不同要求。算法使用剪枝策略高效的搜索4解空间，找出满足约束条件的最大的DNA序列集合。

8、最后通过和遗传算法、多目标进化算法、模板映射、模拟退火和动态规划等算法进行比较和分析，证明了本文提出的隐枚举