| 【中文题名】 | DNA计算编码研究及其算法实现 |
| 【英文题名】 | Research on the DNA Words and Its Arithmetic Actualize |
| 【学科专业】 | 控制工程 |
| 【论文级别】 | 硕士论文 |
| 【投稿时间】 | 2006-4-5 |
| 【中关键词】 | DNA计算,编码问题,线性码,计数问题,约束强度,顶点覆盖问题 |
| 【英关键词】 | DNA Computing,Encoding Problem,linear codes,words count problem,constraint strength,vertex cover problem, |
| 【分类导航】 | 工业技术>自动化技术、计算机技术>自动化基础理论>人工智能理论>> |
| 【论文摘要】 | 随着生物技术的发展,DNA计算随之产生。由于DNA计算机所具有的巨大并行性、海量存储以及低能耗等优点,因此将有望在某些领域弥补现有电子计算机的不足。本文的研究主要包括二方面的内容:DNA计算中的编码问题和DNA计算实例模型研究。
编码问题是DNA计算的关键问题,也是DNA计算中的重点和难点,目前还没有一种通用的方法可以系统地解决编码问题。本文主要工作是在Braich等提出的DNA编码约束条件的基础上做进一步研究,提出了一种新的构造性编码方法——基于线性码的DNA计算编码算法,突破了以往的搜索式算法,该算法能快速、高效地产生所需的编码,结果编码的数量和质量均有保障,从而解决了三字母表的DNA计算编码问题。
为了在已知编码数量情况下,寻找到性能最优地编码参数,如码长l、最大相同子序列的长度s、最小海明距离d_h和GC含量等,需要对编码的计数问题进行研究。目前对编码的计数研究仅局限于单个约束条件下的编码计数,对于同时满足多个约束条件的编码计数问题国内外均未见报道。本文提出了一个新的概念——约束强度,解决了多约束的编码计数问题,能有效地估算出多约束条件下的编码数量。 |
| 【论文题纲】 |
|
摘要 |
3-5 |
|
ABSTRACT |
5-7 |
|
符号说明 |
7-11 |
|
第一章 绪论 |
11-19 |
|
1．1 DNA计算简介 |
11-12 |
|
1．2 DNA计算的研究现状 |
12-16 |
|
1．3 DNA计算待解决的问题 |
16-17 |
|
1．4 本文主要研究内容 |
17-18 |
|
1．5 本文的创新之处 |
18-19 |
|
第二章 DNA计算的生物基础 |
19-33 |
|
2．1 引言 |
19 |
|
2．2 DNA分子结构和性质 |
19-23 |
|
2．3 肽核酸 |
23 |
|
2．4 生物操作 |
23-33 |
|
第三章 DNA计算中的编码问题 |
33-41 |
|
3．1 引言 |
33 |
|
3．2 编码问题及其影响因素 |
33-36 |
|
3．3 编码的计数问题 |
36-37 |
|
3．4 模板—映射编码方法 |
37-38 |
|
3．5 最小长度子串方法 |
38-39 |
|
3．6 遗传算法 |
39 |
|
3．7 编码的热力学性质 |
39-41 |
|
第四章 约束条件与编码计数问题 |
41-50 |
|
4．1 问题的提出 |
41 |
|
4．2 数学模型 |
41-42 |
|
4．3 生物学特性 |
42-43 |
|
4．4 独立约束编码的计数 |
43-46 |
|
4．5 约束强度 |
46-48 |
|
4．6 多约束编码数量的估算 |
48-50 |
|
第五章 构造线性码 |
50-59 |
|
5．1 问题的提出 |
50 |
|
5．2 线性码 |
50-54 |
|
5．3 搜索监督矩阵的优化设计 |
54-56 |
|
5．4 监督矩阵的搜索算法 |
56-57 |
|
5．5 监督矩阵与编码的性能 |
57-59 |
|
第六章 DNA计算编码算法及其结果分析 |
59-65 |
|
6．1 问题的提出 |
59 |
|
6．2 算法设计 |
59 |
|
6．3 算法步骤 |
59-60 |
|
6．4 运行结果 |
60-61 |
|
6．5 运行时间分析 |
61 |
|
6．6 编码数量分析 |
61 |
|
6．7 编码序列的热力学性质 |
61-62 |
|
6．8 随机算法步骤 |
62 |
|
6．9 DNA编码的应用 |
62-65 |
|
第七章 编码在DNA计算模型中的应用 |
65-70 |
|
7．1 问题的提出和描述 |
65-66 |
|
7．2 算法 |
66 |
|
7．3 编码设计 |
66-67 |
|
7．4 生物实现 |
67-68 |
|
7．5 算法分析 |
68-69 |
|
7．6 结束语 |
69-70 |
|
第八章 总结与展望 |
70-72 |
|
8．1 总结 |
70-71 |
|
8．2 展望 |
71-72 |
|
参考文献 |
72-76 |
|
致谢 |
76-77 |
|
攻读硕士学位期间完成论文情况 |
77-78 |
|
| 【DOI】 | LunWen.ID:2.2008.387677 |
