本文主要从粘贴模型和粘贴系统两个方面出发,对图与组合优化中的若干问题进行了研究和讨论,具体内容如下: 粘贴系统是一种基于粘贴运算的语言生成器,也是一种遵循 Watson-Crick互补性质进行退火操作的 DNA 计算抽象模型。本文利用粘贴系统的巨大并行性,给出了旅行商问题的 DNA 计算模型,并通过实例对所建模型进行了验证。 最小顶点覆盖问题是一个 NP 完全问题,它在分子生物学、调度问题、错误诊断和恢复集装线平衡、油轮行程安排及开关理论中有着广泛的应用。本文利用粘贴系统理论对最小顶点覆盖问题的计算模型进行了研究和探索。对系统的限制条件进行了修改,在设计不完整分子 LRρ(V)时,将双链部分定义为单链,左、右的粘性末端连接形式相同,或者同时为上连接,或者同时为下连接。本文认为,如果将LRρ(V)式中的双链部分定义为非空的任意形式,则可表达的 DNA 序列状态增加到 10 种。 检测问题是 DNA 计算中的一个关键问题。本文通过建立最小顶点覆盖问题DNA 计算的表面粘贴模型对检测问题进行了探讨。在建立模型时,对图的顶点和边用一定长度的寡聚核苷酸片断表示;在设计 DNA 序列时采用了双色荧光标记策略,通过在模板链上加入荧光剂和荧光猝灭分子,使得粘贴串与模板链发生杂交反应后产生的荧光猝灭效果,来检测最后的结果。 DNA 计算是通过若干步生化实验完成的,实验步骤的多少直接会影响计算的精度和计算时间。粘贴模型主要是利用 DNA 分子的互补原理,通过控制 DNA序列的变性与复性,对目标位点进行操作而达到计算目的。在这样的计算中,每一步变性与复性都涉及到整个序列的 DNA 分子,因而操作步骤的次数对该模型的计算效果显得尤为明显。本文通过将一种新的生物分子-PNA 引入到粘贴模型中,尝试减少计算过程中的分子操作次数。PNA 分子是一种人工合成的生物 I<WP=5>分子,它与 DNA 之间的连接具有连接牢固、解链温度高,和分子不带电荷、几乎不受离子浓度影响的特性。根据 PNA 分子的这种特性,本文利用 DNA 分子设计存储链和分离探针,PNA 分子设计粘贴串,给出了一个基于粘贴模型求解完美匹配问题的 DNA 计算模型。该模型的难点在于控制变性温度。