DNA芯片组技术及其在解决NP问题中的应用-中国管理科学.PDF

第35卷第5期 北京工业大学学报 Vd．35No．5 OF UNIVERSITYOFTECHNOLOGY 2009 2009年5月 JOURNALBEIJING May DNA芯片组技术及其在解决NP问题中的应用 孟大志1，仲国强1，王丽娜2 (1．北京工业大学应用数理学院，北京100124；2．青岛理工大学琴岛学院，青岛266106) 擒要：为了用DNA并行算法解决实际应用中的一个NP问题——图的四着色问题，基于先进的DNA计算理 论、DNA芯片技术、数据库技术。提出了DNA芯片组技术的概念；通过解决一个极大平面图(包括外边界的中 国地图)的四着色问题，阐述了DNA芯片组技术的具体操作步骤；对生化实验进行计算机模拟并对数据库进行 分析与处理，得到了所有的可行着色方案，从而验证了DNA芯片组技术在解决NP问题中的巨大应用能力． 关键词：DNA计算；DNA芯片；极大平面图；NP问题；四着色问题 中图分类号：TP301 文献标识码：A 文章编号：0254—0037(2009)05—0685一05 士”问题等多个NP类难题的DNA模型和算法．这些模型和算法充分展示了DNA计算所具有的高度的 信息存储与处理能力、巨大的计算并行性等特点，但同时也暴露出了它的一些不足之处，如核苷酸分子数 随着变量数量的增加而呈指数增长，生化实验自动化程度不高，正确解不易获得等．DNA芯片是由 原理是通过处理DNA芯片上的杂交检测图像，对芯片上的DNA信息进行分析和处理[8】．伴随着DNA 芯片技术的发展，对DNA链的荧光标记技术已由一种荧光标记发展到多种荧光标记，而且这种多种荧光 0J． 标记技术已经在许多研究领域得到了应用【94 考虑到实际应用中的NP问题规模一般较大，而DNA芯片技术有很强的处理DNA序列信息的能力， 本文提出了DNA芯片组技术的概念，并设计了DNA芯片组技术的具体操作方法，以弥补以往DNA计算 模型在解决大规模NP问题中的不足． 地图四着色问题的图论模型 地图四着色问题是一个著名的NP完全问题，它以极大平面图(既包括陆地又包括海洋的球面地图) 为主要的研究对象[It]．解决地图四着色问题首先要将极大平面图转换成一个无向图，方法如下：将地图 中的每个区域(包括外边界)表示为图的一个顶点，若2个区域相邻，则用一条无向的边将它们相连，此处 表示外边界的点要与每个表示边界区域的点都相连．极大平面图的四着色问题相对平面上图的四着色问 题约束条件更多，求解的难度更大． 假设由给定地图所导出的无向图中共有靠个点，表示为zl，z2，……，z。，它们就是给定问题的以个 zi—zi≠o表示它们之间的关系，即Xi与Xi不能着相同的颜色，所有的这种不等式关系就是给定问题的 “约束条件”． 解决图的四着色问题的一个一般算法包含以下步骤：1)生成给定问题的变量取值的所有可能组合； 2)利用每一个约束条件排除不满足要求的组合；3)保留剩余的组合；4)重复步骤2)、3)，并保留满足所 有约束条件的组合，它们就是全部的可行着色方案． 收稿日期：2007．09—04． 作者简介：孟大志(1947一)。男。北京人．教授 万方数据 北京工业大学学报 2009焦 2 DNA芯片组技术及地图四着色问题的DNA芯片组模型 精确求解地图四着色问题需要从所有可能的着色方案中筛选出满足所有约束条件的可行解，而随着 变量数量的增加解空间的规模是呈指数级增长的，所以对于规模较大的问题，算法是无法实现的．考虑到 在DNA芯片上操作DNA分子，实现并行计算和信息检测的特点，本文提出了DNA芯片组技术的概念， 并构建了地图四着色问题的DNA芯片组模型． 2．1 DNA芯片组技术 DNA芯片组技术是一项由多种先进技术结合而成的生化实验技术，它包含以下几个步骤：1)按照给 定问题变量之间的关系，将变量进行分组，每组变量对应于一块DNA芯片，建立变量组与芯片组之间的 题的步骤和要求，利用多种荧光标记技术、核苷酸分子杂交技术