若干DNA计算粘贴模型的研究

《若干DNA计算粘贴模型的研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、华中科技大学博士学位论文若干DNA计算粘贴模型的研究姓名：董亚非申请学位级别：博士专业：系统工程指导教师：许进20040112华中科技大学博士学位论文摘要本文主要从粘贴模型和粘贴系统两个方面出发，对图与组合优化中的若干问题进行了研究和讨论，具体内容如下:粘贴系统是一种基于粘贴运算的语言生成器，也是一种遵循Watson-Crick互补性质进行退火操作的DNA计算抽象模型。本文利用粘贴系统的巨大并行性，给出了旅行商问题的DNA计算模型，并通过实例对所建模型进行了验证。最小顶点覆盖问题是一个NP完全问题，它在分子生物学、调度问题、错误诊断和恢复

2、集装线平衡、油轮行程安排及开关理论中有着广泛的应用。本文利用粘贴系统理论对最小顶点覆盖问题的计算模型进行了研究和探索。对系统的限制条件进行了修改，在设计不完整分子LR,')时，将双链部分定义为单链，左、右的粘性末端连接形式相同，或者同时为上连接，或者同时为下连接。本文认为，如果将LRO少)式中的双链部分定义为非空的任意形式，则可表达的。NA序列状态增加到10种。检测问题是DNA计算中的一个关键问题。本文通过建立最小顶点覆盖问题DNA计算的表面粘贴模型对检测问题进行了探讨。在建立模型时，对图的顶点和边用一定长度的寡聚核昔酸片断表示;在设计

3、DNA序列时采用了双色荧光标记策略，通过在模板链上加入荧光剂和荧光碎灭分子，使得粘贴串与模板链发生杂交反应后产生的荧光碎灭效果，来检测最后的结果。DNA计算是通过若干步生化实验完成的，实验步骤的多少直接会影响计算的精度和计算时间。粘贴模型主要是利用DNA分子的互补原理，通过控制DNA序列的变性与复性，对目标位点进行操作而达到计算目的。在这样的计算中，每一步变性与复性都涉及到整个序列的DNA分子，因而操作步骤的次数对该模型的计算效果显得尤为明显。本文通过将一种新的生物分子一PNA引入到粘贴模竺吐全沐减少计算过程中的分子操作次数。PNA分子是

4、一种人工合成的生物华中科技大学博士学位论文分子，它与DNA之间的连接具有连接牢固、解链温度高，和分子不带电荷、几乎不受离子浓度影响的特性。根据PNA分子的这种特性，本文利用DNA分子设计存储链和分离探针，PNA分子设计粘贴串，给出了一个基于粘贴模型求解完美匹配问题的DNA计算模型。该模型的难点在于控制变性温度。关键词:DNA计算，下SP问题，最小顶点覆盖问题，完美匹配问题，粘贴模型，粘贴系统，PNA分子华中科技大学博士学位论文Abstract切thedissertation,severalproblemsingraphandcombina

5、torialoptimizationarestudiedanddiscussedmainlyfromthepointofstickermodelsandstickersystems.Thedetailedcontentsareasfollows:ThestickersystemisalanguagegenerativemechanismbasedonstickingoperationsandaDNAcomputationabstractmodelthatfollowsWatson-Crickcomplementarityrelationt

6、oanneal.Inthisdissertation,DNAcomputingmodelsoftraveling-salesmanproblemsaregivenoutusingthemassiveparallelismofstickersystem.Afterall,thebuiltmodelsareverifiedbyanactualexample.Theminimalvertex-coveringproblemisaNP-completeproblem,andmayapplywidelytomolecularbiology,sche

7、duleproblem,errordiagnosis,thebalanceofresumeandcollection,thejourneyplanofoiltankerandswitchtheory.Inthedissertation,DNAcomputingmodelsoftheminimalvertex-coveringproblemsarestudiedandexploredusingthetheoriesofstickersystems.Therestrictionconditionsofsystemsaremodified,an

8、dthedoublesegmentsaredefinedassinglestrandswhentheincompletemoleculesLRp(V)beingdesigned.Thejoin