最小连通图问题dna表面计算

《最小连通图问题dna表面计算》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、最小连通图问题DNA表面计算　　摘要：现在探讨一种基于芯片的DNA表面计算与电子计算机杂合计算的方法，用于完全问题的计算.该芯片模型通过相应数据库的设计来排布数据，依据不同的问题进行算法设计，在通用的计算芯片表面进行计算反应，计算所得芯片图像，通过专门设计的图像处理计算软件利用计算机进行进一步计算，可以直接得到相应问题的完全解.与以往的DNA计算方法相比，DNA表面计算芯片方法可以将问题的指数运算转化成单项式运算，具有操作简单，不依靠酶反应过程，假阳性率低等优点，并可通过软件与电子计算机相结合，充分发挥DNA计算的并行计算优势和电子计算机的快速数据

2、处理能力的优势，实现良好的杂合.关键词：最小连通问题Adleman-Lipton模型DNA表面计算中图分类号：Q811.211文献标识码：A文章编号：1007-9416（2013）01-0216-028目前，DNA计算机相对于电子计算机有两点不足：（1）DNA计算需要以指数级增长的DNA分子数。但事实上如此之大的DNA链数日难以被满足；（2）DNA计算中的平均错误率的存在。比如不正确的杂交、可能发生的寡核苷酸的内部二次结构等都会降低最后结果的可靠性。这两个缺点限制了DNA计算解决大型复杂问题的能力。而DNA表面计算是克服这上述缺点的一种有效办法。它

3、具有方便样本处理、减少了样本处理中的丢失、减少了寡核苷酸间的干扰、方便了实验中每一步中的DNA分子的纯化。通过化学反应用不同的活化试剂在载体表面键合上各种各样的活性基团，以便与配基共价结合，形成具有不同生物特异性的亲和载体，用来固定不同的活性生物分子，如蛋自质、核酸等。通过这种方法固定在载体表面上的DNA分子，具有能够承受在表面上进行的各种加热、清洗及其它生化反应操作的能力。DNA表面计算方法具体描述如下：（1）分析完全问题，其完全数据池中的数据转化可用0和1按序表达的方式。（2）将完全问题的完全数据池转化为序列数据库。个变量的完全问题，其完全数据

4、池包含个数据，每个数据由个变量的0或1两种状态按序组成。将这样的完全数据池制作成阵列数据库，将数据库中的每个阵列由个分单元构成，每个分单元代表完全数据池中的一个数据，即分单元与数据之间可寻址，每个分单元由4个点组成，则整个阵列包含64个取值为0或1的点，则排布为点阵。6个变量的完全问题的阵列由64个分单元构成，每个分单元由6个点组成，则整个阵列包含384个取值为0或1的点，可排布为点阵。8（3）将阵列数据库中的阵列转化为DNA计算芯片。将完全问题阵列中的数据映射为寡核苷酸序列并排布在芯片上，映射关系如下：1）个变量，每个变量有0和1两种状态，则共有

5、中状态，分别一一对应为种不同的寡核苷酸序列。例如三个变量，则，，，，，六种状态分别一一对应为6种不同的寡核苷酸序列。2）阵列中每个分单元由个0或1按序构成，则按序索引中规定的对应关系，从而将每个分单元对应于依序排列的个寡核苷酸序列，每个序列成为芯片上的一个点；（4）根据完全问题的类型，设计相应的DNA芯片计算算法，编写专用的图像处理和后续计算软件。（5）对给定的芯片算法，将预定合成的有标记的寡核苷酸链混合，与DNA计算芯片发生杂交反应，得到杂交图像。标记物可以是荧光，同位素，化学反应的底物等等，输出的杂交图像可以是荧光图像，同位素图像，化学发光图像

6、等等，也可以是电学信号。（6）采用针对一类问题算法设计的专用软件处理得到的杂交图像，进行计算，寻址，得到该类问题的全解。8如果一个图中任意两个顶点都可以用一条道路把这两个点连接，则这样的图称为连通图。用电子计算机判断一个图是不是连通的并且把能连接所有顶点并且包含最少边的最小连通图迅速找出来，在顶点和边数比较多的情况下，并不是件容易的事情；这就是一个典型的问题。而现在我们就可以用新的表面计算快速地来解决这个问题。而若是一个图是连通的，必须能满足三点：（1）对于交于同一点的几条边来说，应保证其中至少一条在连通图中存在，才能使这点在连通图中存在。（2）对

7、于最小的连通图，不能有环出现，因此要把存在环的情况剔除。（3）对于个点的图来说，其连通图连接的边数应为条边。因此要选出边为的链。满足以上三点的情况即是无权值的最小连通图问题的解。例如：求下图的最小连通图：城市间可以修建，，，，，，，八条管道，每条管道的总成本一样，问有多少种修建方法使这些城市都连接起来，且管道数目最少（如图1）：用DNA表面计算芯片计算此问题的模型和步骤如下：（1）此问题包括8条边，即八个变量。首先定义一种完全数据池的映射策略：1）边分别用，，，，，，，表示。2）定义任一条边有两种赋值，当该条边在图中的边的子集时，则取值为1，否则取

8、值为0。3）将边的子集映射为由1和0组成的数据，顺序依次为。例如：边的集合映射为二进制数101100000。（2）在以上的