DNA自组装计算模型的研究及其在匹配问题中的应用

摘要

DNA自组装计算凭借其海量存储能力、高度并行性和超低能耗这三个强大的优势，使其在各种不同的算法中脱颖而出，成为解决NP难问题和组合优化问题的一种潜在方案。相比于传统的计算方法，DNA自组装计算能够以空间换时间的方法在计算时间上弥补传统计算的不足。论文正是利用了DNA自组装计算的这些特点，解决了一般图最大匹配问题和最优工作安排问题。论文主要工作如下：
　　首先，基于DNA自组装计算的数学模型给出了一种简单的求解一般图最大匹配问题的算法思想，然后根据该算法思想编码设计了种子系统、匹配系统、检测系统和输出系统四个子系统所需的不同类型的DNA Tile，接着以一个包含6个顶点12条边的图来详细说明算法自组装的过程以及对最终解的处理方法，并分析了该计算模型的算法复杂度。通过实例表明该系统所用到的Tile种类为常数，且在线性时间内解决一般图最大匹配问题。
　　其次，针对求解最优工作安排问题这种应用性较强的实际问题，将工作人员信息和任务信息映射到DNA Tile的结合域中，把该问题的求解转换成求解二部图的最大匹配。通过一个简单的实例提出了二部图最大匹配的DNA自组装算法，对该算法的步骤进行了详细的说明，并给出了算法复杂度的分析。
　　最后，对全文进行了总结与展望。对于本文所提出的方法中不足之处进行分析和讨论，确定今后的研究方向。

目录

声明

第1章 绪 论

1.1 选题背景及意义

1.2 国内外研究现状

1.2.1 DNA计算的研究现状

1.2.2 DNA自组装技术的研究现状

1.2.3 匹配问题的研究现状

1.3 本文主要工作及创新点

1.4 论文的结构

第2章 DNA自组装计算模型的研究

2.1 基础知识

2.1.1 DNA分子结构

2.1.2 DNA计算的生物操作

2.2 DNA自组装计算的原理

2.3 DNA自组装计算的数学模型

2.4 本章小结

第3章 基于DNA自组装的一般图最大匹配问题计算模型

3.1 图的最大匹配问题

3.2 求解一般图最大匹配问题的DNA自组装计算模型

3.2.1 种子系统

3.2.2 匹配系统

3.2.3 检测系统

3.2.4 输出系统

3.2.5 算法的求解步骤

3.2.6 算法分析

3.3 本章小结

第4章 基于DNA自组装的最优工作安排问题计算模型

4.1 最优工作安排问题

4.2 求解最优工作安排问题的DNA自组装计算模型

4.2.1 DNA Tile编码设计

4.2.2算法步骤

4.2.3 算法分析

4.3 本章小结

第5章 总结与展望

参考文献

致谢

附 录：攻读硕士学位期间发表的学术论文