论文部分内容阅读
计算机技术被认为是20世纪三大科学革命之一,电子计算机为社会的发展起到了巨大的促进作用,但是量子物理学已经成功地预测出芯片微处理能力的增长不能长期地保持下去。基于这一原因,科学家们正在寻找其他全新的计算机结构,如人工神经网络计算机、量子计算机、光学计算机以及DNA计算机,其中DNA计算机近十五年来倍受科学界的关注。本文对DNA计算中的DNA编码及其相关理论进行了研究。主要工作如下:DNA编码问题是DNA计算中的第一步也是最重要的一步,是DNA计算中的一个基本问题。DNA编码限制条件是衡量DNA编码优劣的评价准则。本文在DNA编码的一个基本限制条件—Hamming距离基础上,分析了DNA编码的三个参量:码字个数,码字长度与Watson-Crick Hamming距离,并得到它们之间的内在联系;讨论了Watson-Crick Hamming距离与DNA码字重量之间的关系;在此基础上得到了DNA编码的编码策略;提出了适合DNA编码的改进Watson-Crick Hamming距离及DNA编码模块化的定义,实现了对DNA编码的优化。部分字的概念是针对DNA计算过程中出现的错误杂交提出的,部分字的相容性、无关性等性质中就体现了DNA编码的基本限制条件,例如:部分字的相容性包含了Hamming距离。本文引入部分字与其洞的定义,研究了部分字的洞与Watson-CrickHamming距离的内在联系;得到Watson-Crick Hamming距离与DNA编码的关系;通过分析不完全匹配部分字中洞的出现位置,对发生假阳性的DNA码进行了优化,解决了DNA编码中除去洞分散分布在DNA双链中的不完全匹配问题。从子序列的性质出发,给出了相同子序列与最大相同子序列的定义,讨论了它们之间的若干关系。利用Watson-Crick Hamming距离对DNA序列集进行分类,所有类构成的集合即为优码,其规模为O(n2~n)。