学位论文 > 优秀研究生学位论文题录展示
DNA计算中若干理论的研究
作 者: 薛圣伟
导 师: 王淑栋
学 校: 山东科技大学
专 业: 应用数学
关键词: DNA计算 NP完全问题 粘贴模型 布尔矩阵 图最大独立集 图顶点着色 约束变量
分类号: TP301.6
类 型: 硕士论文
年 份: 2008年
下 载: 11次
引 用: 0次
阅 读: 论文下载
内容摘要
1994年,Adleman首次提出利用DNA分子解决有向哈密尔顿路问题。随后,关于DNA计算无论在理论还是实验方式研究上都取得了很大的进展。本文主要建立了布尔矩阵乘法以及图论中两类NP完全问题的DNA计算模型,运用统计学中的主成分分析法对DNA序列约束变量的优化进行了探讨。主要工作如下:布尔矩阵及其幂可以作为表达和解决多种问题的数学模型,如:自动机状态,开关问题等,基于布尔矩阵乘法可以用有向图来表示。本文给出了一种新的布尔矩阵乘法的DNA算法。本算法所用到的寡聚核苷酸片段等于有向图的规模,不需要聚合酶链式反应(PCR)扩增。粘贴模型是基于Waston-Crick碱基互补配对原则的DNA计算模型,该模型的优点是:理论上不需要扩展DNA链,反应时不需要生物酶的参与,DNA链可以重复利用等。2005年,Chia-Ning Yang给出了一种改进的DNA粘贴模型,该模型在解决SAT问题时所需的寡聚核苷酸片段数量有显著降低。本文对上述粘贴模型作了进一步的改进,建立了求解图最大独立集的DNA计算模型。首先将图的独立集问题转化为可满足性问题,然后利用改进的粘贴模型给出了图的最大独立集的DNA算法。最后通过一个实例给出算法实现并求出了图的最大独立集。图顶点着色问题是图论中一个著名的NP完全问题,它在现实生活中有着非常重要的应用,如:排序问题,时间表问题,交通状态,车队保养,电路安排,任务的分配等问题都与图顶点着色问题密切相关。本文利用上述改进的粘贴模型,给出了求解图顶点着色问题一种新的DNA粘贴算法。生化反应中只需生成一种DNA单链模板分子,并且这些DNA单链可以在极短时间内生成表示图所有可能顶点着色方案的DNA存储复合物,然后再运用所设计的分离操作来检测图是否可以正常着色。最后通过6个顶点8条边的图对所建模型进行了验证。本算法所用的寡聚核苷酸片段数等于图的规模。DNA计算中,序列约束变量不但具有相关性,而且带有重复的信息,这给序列的分析带来了不便。本文运用统计学中的主成分分析来减少DNA序列约束变量,得到新的约束变量(主成分)。主成分不仅彼此不相关而且能比较全面地反映原来那些约束变量包含的信息。最后对10条DNA序列的5个约束变量对应值进行了主成分分析。
|
全文目录
摘要 5-7 ABSTRACT 7-11 1 绪论 11-16 1.1 DNA计算产生的背景 11-12 1.2 DNA计算的研究现状 12-14 1.3 本文内容 14-15 1.4 本文创新之处 15-16 2 DNA计算的基本生物操作 16-20 2.1 DNA分子结构 16-17 2.2 DNA分子的基本生物操作 17-20 3 布尔矩阵乘法的一种DNA算法 20-23 3.1 基本概念 20 3.2 布尔矩阵乘法的DNA算法设计 20-22 3.3 算法分析 22-23 4 图最大独立集问题的一种改进的DNA粘贴算法 23-30 4.1 基本知识 23 4.2 图最大独立集问题一种改进的DNA粘贴算法的设计 23-27 4.3 算法分析 27-30 5 图顶点着色问题的一种新DNA粘贴算法 30-37 5.1 基本概念 30 5.2 图顶点着色问题一种新的DNA粘贴模型的设计 30-33 5.3 实例分析 33-34 5.4 算法分析 34-37 6 DNA序列约束变量的一种优化方法 37-43 6.1 引言 37 6.2 DNA序列约束变量 37-39 6.3 DNA序列约束变量相应值的主成分分析 39-41 6.4 实例分析 41-43 7 结束语 43-44 致谢 44-45 参考文献 45-48
|
相似论文
- DNA自组装模型在组合优化问题中的应用研究,TP399-C8
- 认知无线电中联合功率控制的动态频谱分配算法研究,TN925
- 基于遗传算法的学分制下多校区排课系统的研究与实现,TP18
- DNA计算机中数据结构的设计与研究,TP311.12
- DNA计算中若干问题的研究,TP301
- 完备Brouwer格上Fuzzy关系方程的求解及传递关系的个数问题,O159
- 基于0-1规划的DNA计算模型的设计与实现,TP3
- 遗传算法在DNA计算中的研究与应用,TP18
- DNA计算在信息安全上的应用,TP309
- DNA计算的编码序列理论及算法的研究,O157.4
- DNA自组装计算模型的应用研究,O242.1
- DNA计算在图论中的应用,O157.5
- DNA计算及其在组合优化问题中的应用,O224
- 基于依存语法的统计机器翻译研究,TP391.2
- 基于DNA计算的布尔逻辑门的设计,TN79
- 关联规则挖掘算法的改进与应用,TP311.13
- 基于DNA技术的加密方法研究,TN918.4
- 关联规则Eclat算法改进研究,TP311.13
- DNA计算中的编码设计优化算法,TP301.6
- DNA计算基本操作研究,TP38
中图分类: > 工业技术 > 自动化技术、计算机技术 > 计算技术、计算机技术 > 一般性问题 > 理论、方法 > 算法理论
© 2012 www.xueweilunwen.com
|