资源描述：
《一种图顶点着色DNA计算机模型》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第51卷第4期2006年2月论文一种图顶点着色DNA计算机模型①②①①①许进强小利方刚周康(①华中科技大学分子生物计算机研究所,武汉430074;②大连大学生物工程学院,大连116622.E-mail:jxu@mail.hust.edu.cn)摘要设计了一种专门用于求解图顶点着色的DNA计算机.该计算机的主体是由一个可变温度的聚丙烯酰胺凝胶电泳构成.可变温度的电泳由3部分组成,分别为“解链区”、“非解区”和“解区”.它们对应的可控温度分别为Tm1,Tm2和Tm3.本文介绍了该计算机的基本结构与基本原理,给出了存储库的构建方法,特别讨论
2、了编码问题,并成功地对5个顶点的图给出了系统的生物操作与生化实验.关键词DNA计算机图顶点着色编码[1]自从Adleman开拓了DNA计算模型以来,无本研究设计了一种用于求解图的顶点着色问题论在理论上还是生物操作技术上,DNA计算与DNA的专用型DNA计算机模型.该计算机的主体由一个计算机的研究工作均取得了惊人的发展.目前不仅可变温度的聚丙烯酰胺凝胶电泳构成.另外,本研究基于DNA分子,而且基于生物酶、生物操作等,已还给出了计算机中存储库的具体构造方法.这里的经提出了不少的DNA计算模型.在已有的DNA计算存储库主要由两个部分构成:一
3、个是构成所有可能[2]模型中,有些是理论上的模型,如Lipton建立的求着色的所谓的图的着色方案的DNA序列链,简称为库[3]解可满足性问题的DNA计算模型及Roweis等人链;另一个是给出图结构信息的所谓的探针库链.在本提出的粘贴DNA计算模型等.有些则通过巧妙地利研究中,我们特别指出了编码的方法步骤,并对20个用生物操作技术建立的DNA计算模型,如Adleman顶点的一个图给出了具体的编码.最后,成功地对5个[4]研究组在2002年建立的求具有20个变量的3-SAT顶点的图给出了系统地生物操作与生化实验验证.问题的DNA计算模型,
4、就是充分利用凝胶电泳和温本研究中的图用G表示,均指简单无向图.用控方法建立起来的,是目前利用非电子工具解决的V(G)及E(G)表示图G的顶点集和边集.图G的一个规模最大的一个NP-完全问题.在那些基于生物实验k-正常顶点着色,简称为图的k-顶点着色,是指用k[5]的模型中,备受关注的有Sakamoto等人巧妙地利种颜色对图G的每个顶点的一种分配,使得相邻的用DNA发夹构形给出的求解SAT问题的模型;顶点分配(或称为“着”)到不同的颜色.由于本研究仅[6]Ouyang等人利用POA技术合成DNA分子来设计考虑图的3-着色问题,故我们总是
5、假定颜色集为{r,b,DNA计算中所需要的所有数据库,给出的求解图的y},其中r表示红色,b表示蓝色,y表示黄色.所以,[7]最大团问题的DNA计算模型;Liu等人给出的表面求解图的3-着色问题可以认为是寻找从图的顶点集DNA计算的SAT问题的模型以及Weizman研究小V(G)到颜色集{r,b,y}的一种映射:[8,9]组给出的利用DNA计算进行疾病诊断与治疗相结f:V(G)→{r,b,y},合的DNA计算机模型和逻辑分析DNA计算模型等.使得对于∀uv∈E(G),f(u)≠f(v).图的3-着色问众所周知,图的着色问题是一个困难的
6、组合优[23]题是一个NP-完全问题.化问题,具有良好的应用背景,如工序问题、排课表容易推理,本研究结果同样适用于k≥4的情况.[10~12]问题以及存储问题等均有直接的应用.然而,图1基本结构与基本原理着色问题是一个困难的NP-完全问题.目前,已经有不少的算法用于研究图的着色问题,如常规的算(ⅰ)基本结构.设计的“图顶点着色DNA计算法[13~15]、人工神经网络算法[16,17]、遗传算法[18]以及机模型”的基本结构由硬件和软件两个部分构成，其模拟退火算法[19]等.近年来,我们已经提出了几个基中的硬件主体是聚丙烯酰胺凝胶电泳,
7、该凝胶电泳于DNA计算的图的着色问题的理论计算模型[20~22].由3个区构成:本文所提出的这个新的图顶点着色DNA计算机模型,(1)变性区.将来自于存储库中的双链DNA分也正是在上述研究工作所积累上提出来的.子经过变性后变成单链,其中的一条单链被固定,而480www.scichina.com论文第51卷第4期2006年2月另一条单链没有固定,可随电泳进行移动.固定n,且图总是简单无向有限图.本研究假定对图的顶DNA分子的方法可采用磁珠技术,或者所谓的点着色是3-着色.当然,对于k-着色问题,k≥4,其TMTMAcrydite方法等,
8、有关Acrydite方法的理论以及原理是相同的.1)较为详细的讨论参见文献.把存储库中代表顶点着色方案的所有双链DNA序列置于一个板上,称为A板.(2)非解粘贴区,或简称为“非解区”.存放一个B板,称为探针板.探针板上均
