DNA计算编码研究及其算法实现

《DNA计算编码研究及其算法实现》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、DNA计算编码研究及其算法实现摘要随着生物技术的发展，DNA计算随之产生。由于DNA计算机所具有的巨大并行性、海量存储以及低能耗等优点，因此将有望在某些领域弥补现有电子计算机的不足。本文的研究主要包括二方面的内容：DNA计算中的编码问题和DNA计算实例模型研究。编码问题是DNA计算的关键问题，也是DNA计算中的重点和难点，目前还没有一种通用的方法可以系统地解决编码问题。本文主要工作是在Braich等提出的DNA编码约束条件的基础上做进一步研究，提出了一种新的构造性编码方法——基于线性码的DNA计算编码算法，突破了以往的搜索式算法，

2、该算法能快速、高效地产生所需的编码，结果编码的数量和质量均有保障，从而解决了三字母表的DNA计算编码问题。为了在已知编码数量情况下，寻找到性能最优地编码参数，如码长，、最大相同子序列的长度J、最小海明距离巩和GC含量等，需要对编码的计数问题进行研究。目前对编码的计数研究仅局限于单个约束条件下的编码计数，对于同时满足多个约束条件的编码计数问题国内外均未见报道。本文提出了一个新的概念——约束强度，解决了多约束的编码计数问题，能有效地估算出多约束条件下的编码数量。浙江工业大学工程硕士学位论文在研究过程中还发现，搜索空间的优化是寻找监督矩

3、阵的关键，而且满足条件的监督矩阵在搜索空间中的分布基本上是相对均匀的，监督矩阵决定码重分布。研究结果表明，三字母表的编码参数一般为1=10．14、s=4．6、以=5．6、GC含量约为1／3，可满足编码数量小于180的各种情况。最后设计了一个编码的应用模型，用于DNA计算来解决最小顶点覆盖问题，该模型的特点是直接在可满足解空间搜索问题的解，简化了DNA计算过程，同时也提高了溶液解浓度，有效地扩大了解决问题的规模。关键词：DNA计算，编码问题，线性码，计数问题，约束强度，顶点覆盖问题DNA计算编码研究及其算法实现RESEARCHONT

4、HEDNAWORDSANDITSARITH卫腰TICACTUALIZEABSTRACTWiththerapiddevelopmentofbiologicaltechniques，anewdisciplinenamedDNAcomputinghascomeintobeing．Owingtomassiveparallelism，high．densitystorageandlowenergycostDNAcomputerovercomethedisadvantagesofelectroniccomputer．Thispapermainl

5、yfocusesonthefollowingtwosubjects：theencodingproblemandDNAcomputingalgorithmfortheminimumvertexcoverproblem．EncodingproblemisthekeytoDNAcomputing，SOalsothemostdifficultproblembecauseithasnotageneralsolution．Inthisthesis，weproposeanefficientalgorithmofconstructivitybas

6、edonlinearcodes．OurworkiSbasedontheworkofBraichetal．，inwhichtheyproposedaconstraintconditionmodeltoproduceDNAsequencesthroughtertiarystrands．Ourproposedalgorithmsurpasssthesearchalgorithm．ThealgorithmCanfastandeffiecientlyproducewordswithenoughamountandhighquality．So，

7、ithadsolvedtheencodingproblemwithtemaryalphabet．Giventhewordamount，wesearchtheoptimizationencodingparameterssuchaswordslengthlandmaximumsubstringlengthsandminimumhammingdistance以So，inthissitutationweneedonlyresearchingthewordscount．Nowtherearereportsonthewordscountpro

8、blemundersingleconstraint，butuptonowthereisnoreportonthisproblemundermultiplecontraints．Ourmethodhadsolvedamultipleconstrain