基于改进pcr计算模型求解最大团问题的方法
基于改进pcr计算模型求解最大团问题的方法
【技术领域】
[0001] 本发明涉及PCR计算领域，具体讲的是通过改进阿德尔曼-利普顿模型，并进而建 立PCR计算的抽象理论模型，然后利用PCR计算求解最大团问题。
【背景技术】
[0002] DNA计算是一种新兴的交叉学科，利用DNA分子生物技术解决计算机科学、数学难 题。随着研究的不断深入，PCR在DNA计算领域已取得多项进展。Franco等人利用交叉配对 PCR(Cross Pairing PCR-XPCR)技术，提出了一种新的方法产生一个初始池，它是通过特 殊上下文规则应用第四纪复合字符串拼接，来提取DNA解空间中具有某种特定信息特征的 DNA链，实现解的检测与分离。Manca等人采用PCR技术，设计了一个基于混合/分离策略的 DNA计算模型，模型中利用DNA双链分子对问题进行编码，用PCR技术实现全部解空间的生 成，并结合电泳技术实现DNA分子的分离操作。与DNA计算中用其它手段实现信息处理操作 相比，PCR操作简洁高效，且计算过程中的分离操作仅与DNA分子的长度相关，精度较高，但 在Manca等人的模型中由于采用的是混合/分离计算模型，如不运用改进的算法仍需面对指 数爆炸问题，并且在进行DNA编码时如果不进行谨慎设计，将会引起XPCR反应过程中错误编 码的错误扩增。Komiya等人将DNA发卡结构与DNA聚合酶的聚合作用相结合，构造了 DNA计算 的Whiplash PCR模型，并通过连续的热循环实现计算过程中的状态转移。而Franco将XPCR 技术应用进行进一步扩展，通过几个DNA算法利用XPCR技术尝试解决如多发性级联、变异、 DNA提取等。Saaid，建议利用实时PCR技术标记"是"和"否"后，并将其应用于解决汉密尔顿 路径和DNAmachine，并利用算例证明了这种方法的可行性。
[0003] 最大团问题(Maximum Clique Problem,MCP)是图论中一个经典的组合优化问题， 更是现实中真实存在的问题。在很多领域有着广泛用途，如计算机视觉、信号分析与处理。 很多学者致力于寻找解决MCP的最优算法，目前有很多文献对其论述，并提出多种不同解决 方法。杨静等人基于环状DNA分子，借助于链霉亲和素包被的磁珠及环化酶，构建了新型的 计算模型。在此计算模型中需要将DNA分子结构由线性转化成为单链环形，单链环形分子可 以极大地减少了计算所需的时间和空间。算法的空间及时间复杂度为〇(n+m)。对于解决一 个含有η个节点的最大团问题，这种算法与枚举型算法相比，在搜索过程中所需试管数较 少，只需η+1个试管，而利用枚举型算法则至少需要2η个试管。文中所利用环状DNA分子与双 链DNA不同，需在计算前人工合成单链DNA分子，虽然可以根据计算要求对DNA单链进行编 码，但DNA单链分子稳定性较弱，实际试验操作中较易出现错误解。Daniel Manrique通过改 进优先搜索DNA算法(改进DNA链长度和体积，生物酶的数量和浓度），提高了解决最大团问 题的效率。Gang Yang等人尝试利用改进的竞争Hopfield网络算法（ICHN)激发了竞争动态， 有效增加了最优解出现的概率，适于求解大规模MCP问题。QinghuaWu利用主搜索分类策略 及最相关图关键因素算法[17]解决了最大团问题。但是随着问题规模急剧增长后，传统确 定性算法时间复杂度较大，并且不能进行并行计算，在问题解决方面日益显得无能无力。
[0004]本文以PCR运算模型作为主要操作手段，用于解决最大团问题(Maximum Clique Problem，MCP)。首先利用双链DNA分子进行编码，避免了单链DNA分子的不稳定性，利用PCR 技术对DNA双链上特定片段进行复制，并利用XPCR技术得到全部解空间，最后通过引物筛选 出特定解，从而得到最终解。此种算法无需使用催化酶，可以有效避免复制粘贴模型所引 起的误差。又因使用双链DNA分子相较于环形分子长度受限不能解决较大规模的最大团问 题更有优势。双链DNA分子更稳定，实验过程无需使用催化酶，故适于用在准确度要较高的 数学NP完全问题中。PCR计算所运用的实验步骤均能在实验室条件下实现，是更为成熟的求 解算法。
【发明内容】
[0005] 鉴于已有方法存在的缺陷，本发明提供基于改进PCR计算模型求解最大团问题的 方法，本发明首先对试管中的DNA链进行编码，编码如下
使编码后的DNA链能准确表示给定无向图的顶点子集。从所有可能解中筛选出所需的特定 解，并进一步对所得接求补，即可得到最终解。在筛选特定解时，对阿德尔曼-利普顿模型进 行改进:加入了 PCR、XPCR操作，对特定解进行指数扩增，能够实现特定解的筛选。
[0006] 本发明使得求解过程稳定准确，易于在实际操作中实现，又因使用双链DNA分子实 验过程无需使用催化酶求解过程更稳定，结果更准确，更适合于解决大规模的最大团问题。
[0007] 为实现上述目的，本发明所采用的技术方案是：
[0008] 基于改进的PCR计算模型的求解最大团问题方法，其基本思想是利用PCR模型中的 混合，清空，筛选，PCR，及改进的XPCR操作，实现最大团问题的解空间生成，特定解筛选，并 筛选出最终解。本专利中所有操作均是对试管中的DNA链进行操作。
[0009] 基于改进PCR计算模型求解最大团问题的方法，如下步骤：
[0010] 步骤1:建立无向图的补图；
[0011] 步骤2:用DNA链表示补图的顶点子集，并对DNA链进行编码，利用PCR技术对DNA链 上的特定片段进行复制并利用XPCR技术生成解空间；
[0012] 步骤3:给定一条补图边，每条补图边对应两个顶点，筛选出含有这两个顶点的一 个或两个的DNA链，放入试管；
[0013] 步骤4:对试管中的DNA链重复步骤3，直到所有的补图边均被筛选过；
[0014] 步骤5:从步骤4所得结果中，利用PCR技术筛选出试管中最短的DNA链作为含有最 少顶点数的子集；
[0015] 步骤6:对步骤5中所得子集求补，得到最终结果。
[0016] 所述DNA链为DNA双链。
[0017] 基于改进PCR计算模型求解最大团问题的方法，所述步骤2中生成解空间的具体方 法如下：利用PCR技术，对初始DNA双链分子按照顶点编号，逐位循环进行XPCR交叉连接， XPCR进行的过程中会伴随DNA双链分子的指数扩增，对于η个顶点的简单无向图，循环η次得 到图所有的顶点子集，则试管中生成的DNA双链分子表示所有的顶点子集，得到解空间。
[0018] 基于改进PCR计算模型求解最大团问题的方法，所述步骤3中筛选的方法为通过 XPCR操作对含有特定DNA分子序列的DNA分子后面添加指定序列β，以DNA分子片段ω和β的 后缀分别作为PCR操作的前端与后端引物，对添加了特定序列邱勺DNA分子进行指数扩增，扩 增后以DNA分子的长度作为DNA序列分离的特征条件，通过凝胶电泳对DNA序列进行分离，筛 选出含有特定顶点的顶点子集。
[0019] 基于改进了的P C R计算模型求解最大团问题的方法，对于给定的无向图G = (V，E)， 其中V={vi, . . .，vn}，E= {ei, . . .，em}，求解具体步骤如下：
[0020] 1)建立无向图G的补图G Q
[0021] 2)用DNA序列对补图否中的每个顶点进行DNA序列编码，采用二进制编码顶点子 集，编码格式^
其中UA代表第i个顶点在顶点子集中的状 态。并生成无向图G的所有可能顶点子集，即为解空间。
[0022] 3)对补图G中的所有的边玄=洱，...,?}进行编号，每条边均由两个顶点唯一确定 弓= :(H)。
[0023] 4)给定一条补图吞中的边忑=(^)，利用PCR技术筛选含有Vi或vi的DNA链，并放 入特定试管T中。
[0024] 5)对试管T中DNA链重复步骤4,直到所有的补图边均被筛选过。
[0025] 6)利用PCR技术筛选出试管T中，含有最少的顶点的子集。并对这些子集求补，即为 最终结果。
[0026] 本发明与现有技术相比具有以下优点：
[0027] 1，将PCR计算引入最大团问题求解过程中，通过对特定解指数扩增，能稳定且准确 的筛选出特定解。< br>[0028] 2,在筛选特定解过程中，对阿德尔曼-利普顿模型改进，引入PCR、XPCR技术到最大 团问题研究，采用DNA双链分子，且在实验过程中不使用限制性内切酶，降低了限制性内切 酶对生化实验的干扰，降低了 DNA编码的难度，有利于实现大规模的DNA计算。
[0029] 3,对DNA双链进行编码，然后通过PCR技术对有特定编码片段的DNA双链进行复制， 以DNA双链的长度作为唯一的筛选标准，这一标准可以用电泳的方式来实现，且实现过程简 单可靠。
[0030] 4,解决最大团问题算法操作过程中对阿德尔曼-利普顿模型进行改进，增加了对 并行PCR及XPCR操作的形式化数学定义，将对应的DNA分子生化反应操作抽象为数学运算算 子，进而形成PCR计算模型的形式定义，最终建立PCR计算的抽象理论模型。
【附图说明】
[0031 ]图1 DNA链编码的定义；
[0032]图2实施例中给定的无向图；
[0033]图3给定无向图对应的完全图；
[0034]图4给定无向图对应的补图；
[0035]图5程序流程图；
[0036]图6筛选含有特定序列(特定顶点）的DNA链过程；
[0037]图7实施例每一步骤结果。
【具体实施方式】
[0038]下面结合附图对本发明作进一步说明：
[0039] 实施例1
[0040]本发明的实施例是在以本发明技术方案为前提下进行实施的，给出了详细的实施 方式和具体的操作过程，但本发明的保护范围不限于下述实施例。因为有无数种无向图，我 们以一个顶点数为5的无向图为例，具体见图2,其完全图见图3,补图见图4。
[0041] 步骤1:首先对DNA分子链编码。可以对顶点子集V={V1，…，vn}进行编码，编码方案 见图1。单链ω与δ分别为DNA链前缀与后缀。1与0表示顶点在顶点子集中的状态，若为1则表 示顶点在该顶点子集中，若为〇则表示顶点子集中无该点，且11 I =2 | 0 |。如对图2中的无向 图，其某个顶点子集Κ = {V1，V3，ν5}可以对应编码为双链DNA序歹[
[0042] 步骤2:在试管T中包含4种初始DNA双链分子：
利用 PCR技术，对初始DNA双链分子按照顶点编号，逐位循环进行XPCR交叉连接，XPCR进行的过程 中会伴随DNA双链分子的指数扩增，对于η个顶点的简单无向图，循环η次就得到图所有的顶 点子集(2η个顶点子集）。对于图2的简单图，仅需要5次循环，则试管中生成的DNA双链分子 可以表示图2所有的顶点子集。
[0043] 步骤3:在获得的所有DNA双链分子中，通过指定PCR过程中的5'端-引物与3'端-弓| 物，利用PCR操作实现特定DNA双链分子片段的截取;基于前述DNA双链分子的编码方案，利 用DNA双链分子3 端后缀与5 端前缀相同的特点，通过XPCR操作实现特定DNA双链分子的 连接。具体为通过XPCR操作对含有编码第i个顶点的特定DNA分子序列UiD的DNA分子后面添 加 DNA分子序列β(序列β的长度大于ΙΒΗΒΗ - Βη?ζφ | -一序列两端的竖线表示求取对应 DNA分子序列的长度），以DNA分子片段ω和邱勺后缀分别作为PCR操作的前端与后端引物，对 添加了特定序列β的DNA分子进行指数扩增。扩增后，由于序列邮]长度大于?ΒΗΒη-ΙΙζφ ，以DNA分子的长度做为DNA序列分离的特征条件，通过凝胶电泳对DNA序列进行分离，通过 这种方法可以筛选出含有特定顶点的顶点子集，其详细过程如图6。用此方法，首先复制两 份解空间，一份筛选出试管中含有v2的顶点子集。另一份筛选出含有V4顶点子集的DNA链。将 两份结果混合，即为所有含有^或^顶点子集的DNA链。结果如图7。
[0044] 步骤4:在步骤3的基础上筛选出含有V2或V5顶点子集的DNA链。结果如图7。
[0045]步骤5:利用电泳技术，筛选出步骤3，4所得结果中最短的DNA链。结果为V2。
[0046] 步骤6:对上一步结果求反，即为最终结果。结果为V1V3V4V5。
[0047] 综上所述，我们通过改进的PCR计算模型求解最大团问题，可以避免使用限制性核 酸内切酶，在DNA编码中不需要考虑限制性核酸内切酶的识别位点约束，简化DNA编码，同时 由于DNA序列的分离仅仅依赖于DNA分子的长度，可以大大提高实验过程的稳定性和计算结 果的精度。应用PCR技术可以准确的从所有可能解中筛选特定解，也因为PCR技术需要使用 稳定性更好的双链DNA分子而适合于求解大规模最大团问题。由此说明我们的方法是有效 可行的。
[0048]以上所述，仅为本发明较佳的【具体实施方式】，但本发明的保护范围并不局限于此， 任何熟悉本技术领域的技术人员在本发明披露的技术范围内，根据本发明的技术方案及其 发明构思加以等同替换或改变，都应涵盖在本发明的保护范围内。
【主权项】
1. 基于改进PCR计算模型求解最大团问题的方法，其特征在于，如下步骤： 步骤1:建立无向图的补图； 步骤2:用DNA链表示补图的顶点子集，并对DNA链进行编码，利用PCR技术对DNA链上的 特定片段进行复制并利用XPCR技术生成解空间； 步骤3:给定一条补图边，每条补图边对应两个顶点，筛选出含有这两个顶点的一个或 两个的DNA链，放入试管； 步骤4:对试管中的DNA链重复步骤3，直到所有的补图边均被筛选过； 步骤5:从步骤4所得结果中，利用PCR技术筛选出试管中最短的DNA链作为含有最少顶 点数的子集； 步骤6:对步骤5中所得子集求补，得到最终结果。2. 根据权利要求1所述的基于改进了的PCR计算模型求解最大团问题的方法，其特征在 于:对于给定的无向图G = (V，E)，其中V= {vi, . . .，vn} ,E = {ei, . . .，em}，求解具体步骤如 下： 1) 建立无向图G的补图否， 2) 用DNA序列对补图石中的每个顶点进行DNA序列编码，采用二进制编码顶点子集，编 码格式为其中U1X代表第i个顶点在顶点子集中的状态;并 生成无向图G的所有可能顶点子集，即为解空间； 3) 对补图G中的所有的边互=间，...，乙}进行编号，每条边均由两个顶点唯一确定 4) 给定一条补图G中的边巧，利用PCR技术筛选含有Vi或"的0嫩链，并放入特 定试管T中； 5) 对试管T中DNA链重复步骤4,直到所有的补图边均被筛选过； 6) 利用PCR技术筛选出试管T中，含有最少的顶点的子集，并对这些子集求补，即为最终 结果。3. 根据权利要求1或2所述的基于改进了的PCR计算模型求解最大团问题的方法，其特 征在于:所述DNA链为DNA双链。4. 根据权利要求1所述的基于改进PCR计算模型求解最大团问题的方法，其特征在于， 所述步骤2中生成解空间的具体方法如下：利用PCR技术，对初始DNA双链分子按照顶点编 号，逐位循环进行XPCR交叉连接，XPCR进行的过程中会伴随DNA双链分子的指数扩增，对于η 个顶点的简单无向图，循环η次得到图所有的顶点子集，则试管中生成的DNA双链分子表示 所有的顶点子集，得到解空间。5. 根据权利要求1所述的基于改进PCR计算模型求解最大团问题的方法，其特征在于： 所述步骤3中筛选的方法为通过XPCR操作对含有特定DNA分子序列的DNA分子后面添加指定 序列β，以DNA分子片段ω和β的后缀分别作为PCR操作的前端与后端引物，对添加了特定序 列β的DNA分子进行指数扩增，扩增后以DNA分子的长度作为DNA序列分离的特征条件，通过 凝胶电泳对DNA序列进行分离，筛选出含有特定顶点的顶点子集。
【专利摘要】本发明涉及最大团问题领域，设计了一种基于改进了的PCR计算模型解决最大团问题的方法。该方法对PCR计算模型进行改进,并用于解决最大团问题。此种方法在实验室环境下较易实现，且误差较小，亦可以有效降低计算中各种酶切反应不完全而引起的“噪声”，且DNA编码链为双链DNA分子，比单链编码更为稳定。
【IPC分类】G06N3/12
【公开号】CN105488569
【申请号】CN201510860554
【发明人】张强, 翟伟华, 郑学东
【申请人】大连大学
【公开日】2016年4月13日
【申请日】2015年12月1日
【技术领域】
[0001] 本发明涉及PCR计算领域，具体讲的是通过改进阿德尔曼-利普顿模型，并进而建 立PCR计算的抽象理论模型，然后利用PCR计算求解最大团问题。
【背景技术】
[0002] DNA计算是一种新兴的交叉学科，利用DNA分子生物技术解决计算机科学、数学难 题。随着研究的不断深入，PCR在DNA计算领域已取得多项进展。Franco等人利用交叉配对 PCR(Cross Pairing PCR-XPCR)技术，提出了一种新的方法产生一个初始池，它是通过特 殊上下文规则应用第四纪复合字符串拼接，来提取DNA解空间中具有某种特定信息特征的 DNA链，实现解的检测与分离。Manca等人采用PCR技术，设计了一个基于混合/分离策略的 DNA计算模型，模型中利用DNA双链分子对问题进行编码，用PCR技术实现全部解空间的生 成，并结合电泳技术实现DNA分子的分离操作。与DNA计算中用其它手段实现信息处理操作 相比，PCR操作简洁高效，且计算过程中的分离操作仅与DNA分子的长度相关，精度较高，但 在Manca等人的模型中由于采用的是混合/分离计算模型，如不运用改进的算法仍需面对指 数爆炸问题，并且在进行DNA编码时如果不进行谨慎设计，将会引起XPCR反应过程中错误编 码的错误扩增。Komiya等人将DNA发卡结构与DNA聚合酶的聚合作用相结合，构造了 DNA计算 的Whiplash PCR模型，并通过连续的热循环实现计算过程中的状态转移。而Franco将XPCR 技术应用进行进一步扩展，通过几个DNA算法利用XPCR技术尝试解决如多发性级联、变异、 DNA提取等。Saaid，建议利用实时PCR技术标记"是"和"否"后，并将其应用于解决汉密尔顿 路径和DNAmachine，并利用算例证明了这种方法的可行性。
[0003] 最大团问题(Maximum Clique Problem,MCP)是图论中一个经典的组合优化问题， 更是现实中真实存在的问题。在很多领域有着广泛用途，如计算机视觉、信号分析与处理。 很多学者致力于寻找解决MCP的最优算法，目前有很多文献对其论述，并提出多种不同解决 方法。杨静等人基于环状DNA分子，借助于链霉亲和素包被的磁珠及环化酶，构建了新型的 计算模型。在此计算模型中需要将DNA分子结构由线性转化成为单链环形，单链环形分子可 以极大地减少了计算所需的时间和空间。算法的空间及时间复杂度为〇(n+m)。对于解决一 个含有η个节点的最大团问题，这种算法与枚举型算法相比，在搜索过程中所需试管数较 少，只需η+1个试管，而利用枚举型算法则至少需要2η个试管。文中所利用环状DNA分子与双 链DNA不同，需在计算前人工合成单链DNA分子，虽然可以根据计算要求对DNA单链进行编 码，但DNA单链分子稳定性较弱，实际试验操作中较易出现错误解。Daniel Manrique通过改 进优先搜索DNA算法(改进DNA链长度和体积，生物酶的数量和浓度），提高了解决最大团问 题的效率。Gang Yang等人尝试利用改进的竞争Hopfield网络算法（ICHN)激发了竞争动态， 有效增加了最优解出现的概率，适于求解大规模MCP问题。QinghuaWu利用主搜索分类策略 及最相关图关键因素算法[17]解决了最大团问题。但是随着问题规模急剧增长后，传统确 定性算法时间复杂度较大，并且不能进行并行计算，在问题解决方面日益显得无能无力。
[0004]本文以PCR运算模型作为主要操作手段，用于解决最大团问题(Maximum Clique Problem，MCP)。首先利用双链DNA分子进行编码，避免了单链DNA分子的不稳定性，利用PCR 技术对DNA双链上特定片段进行复制，并利用XPCR技术得到全部解空间，最后通过引物筛选 出特定解，从而得到最终解。此种算法无需使用催化酶，可以有效避免复制粘贴模型所引 起的误差。又因使用双链DNA分子相较于环形分子长度受限不能解决较大规模的最大团问 题更有优势。双链DNA分子更稳定，实验过程无需使用催化酶，故适于用在准确度要较高的 数学NP完全问题中。PCR计算所运用的实验步骤均能在实验室条件下实现，是更为成熟的求 解算法。
【发明内容】
[0005] 鉴于已有方法存在的缺陷，本发明提供基于改进PCR计算模型求解最大团问题的 方法，本发明首先对试管中的DNA链进行编码，编码如下
使编码后的DNA链能准确表示给定无向图的顶点子集。从所有可能解中筛选出所需的特定 解，并进一步对所得接求补，即可得到最终解。在筛选特定解时，对阿德尔曼-利普顿模型进 行改进:加入了 PCR、XPCR操作，对特定解进行指数扩增，能够实现特定解的筛选。
[0006] 本发明使得求解过程稳定准确，易于在实际操作中实现，又因使用双链DNA分子实 验过程无需使用催化酶求解过程更稳定，结果更准确，更适合于解决大规模的最大团问题。
[0007] 为实现上述目的，本发明所采用的技术方案是：
[0008] 基于改进的PCR计算模型的求解最大团问题方法，其基本思想是利用PCR模型中的 混合，清空，筛选，PCR，及改进的XPCR操作，实现最大团问题的解空间生成，特定解筛选，并 筛选出最终解。本专利中所有操作均是对试管中的DNA链进行操作。
[0009] 基于改进PCR计算模型求解最大团问题的方法，如下步骤：
[0010] 步骤1:建立无向图的补图；
[0011] 步骤2:用DNA链表示补图的顶点子集，并对DNA链进行编码，利用PCR技术对DNA链 上的特定片段进行复制并利用XPCR技术生成解空间；
[0012] 步骤3:给定一条补图边，每条补图边对应两个顶点，筛选出含有这两个顶点的一 个或两个的DNA链，放入试管；
[0013] 步骤4:对试管中的DNA链重复步骤3，直到所有的补图边均被筛选过；
[0014] 步骤5:从步骤4所得结果中，利用PCR技术筛选出试管中最短的DNA链作为含有最 少顶点数的子集；
[0015] 步骤6:对步骤5中所得子集求补，得到最终结果。
[0016] 所述DNA链为DNA双链。
[0017] 基于改进PCR计算模型求解最大团问题的方法，所述步骤2中生成解空间的具体方 法如下：利用PCR技术，对初始DNA双链分子按照顶点编号，逐位循环进行XPCR交叉连接， XPCR进行的过程中会伴随DNA双链分子的指数扩增，对于η个顶点的简单无向图，循环η次得 到图所有的顶点子集，则试管中生成的DNA双链分子表示所有的顶点子集，得到解空间。
[0018] 基于改进PCR计算模型求解最大团问题的方法，所述步骤3中筛选的方法为通过 XPCR操作对含有特定DNA分子序列的DNA分子后面添加指定序列β，以DNA分子片段ω和β的 后缀分别作为PCR操作的前端与后端引物，对添加了特定序列邱勺DNA分子进行指数扩增，扩 增后以DNA分子的长度作为DNA序列分离的特征条件，通过凝胶电泳对DNA序列进行分离，筛 选出含有特定顶点的顶点子集。
[0019] 基于改进了的P C R计算模型求解最大团问题的方法，对于给定的无向图G = (V，E)， 其中V={vi, . . .，vn}，E= {ei, . . .，em}，求解具体步骤如下：
[0020] 1)建立无向图G的补图G Q
[0021] 2)用DNA序列对补图否中的每个顶点进行DNA序列编码，采用二进制编码顶点子 集，编码格式^
其中UA代表第i个顶点在顶点子集中的状 态。并生成无向图G的所有可能顶点子集，即为解空间。
[0022] 3)对补图G中的所有的边玄=洱，...,?}进行编号，每条边均由两个顶点唯一确定 弓= :(H)。
[0023] 4)给定一条补图吞中的边忑=(^)，利用PCR技术筛选含有Vi或vi的DNA链，并放 入特定试管T中。
[0024] 5)对试管T中DNA链重复步骤4,直到所有的补图边均被筛选过。
[0025] 6)利用PCR技术筛选出试管T中，含有最少的顶点的子集。并对这些子集求补，即为 最终结果。
[0026] 本发明与现有技术相比具有以下优点：
[0027] 1，将PCR计算引入最大团问题求解过程中，通过对特定解指数扩增，能稳定且准确 的筛选出特定解。< br>[0028] 2,在筛选特定解过程中，对阿德尔曼-利普顿模型改进，引入PCR、XPCR技术到最大 团问题研究，采用DNA双链分子，且在实验过程中不使用限制性内切酶，降低了限制性内切 酶对生化实验的干扰，降低了 DNA编码的难度，有利于实现大规模的DNA计算。
[0029] 3,对DNA双链进行编码，然后通过PCR技术对有特定编码片段的DNA双链进行复制， 以DNA双链的长度作为唯一的筛选标准，这一标准可以用电泳的方式来实现，且实现过程简 单可靠。
[0030] 4,解决最大团问题算法操作过程中对阿德尔曼-利普顿模型进行改进，增加了对 并行PCR及XPCR操作的形式化数学定义，将对应的DNA分子生化反应操作抽象为数学运算算 子，进而形成PCR计算模型的形式定义，最终建立PCR计算的抽象理论模型。
【附图说明】
[0031 ]图1 DNA链编码的定义；
[0032]图2实施例中给定的无向图；
[0033]图3给定无向图对应的完全图；
[0034]图4给定无向图对应的补图；
[0035]图5程序流程图；
[0036]图6筛选含有特定序列(特定顶点）的DNA链过程；
[0037]图7实施例每一步骤结果。
【具体实施方式】
[0038]下面结合附图对本发明作进一步说明：
[0039] 实施例1
[0040]本发明的实施例是在以本发明技术方案为前提下进行实施的，给出了详细的实施 方式和具体的操作过程，但本发明的保护范围不限于下述实施例。因为有无数种无向图，我 们以一个顶点数为5的无向图为例，具体见图2,其完全图见图3,补图见图4。
[0041] 步骤1:首先对DNA分子链编码。可以对顶点子集V={V1，…，vn}进行编码，编码方案 见图1。单链ω与δ分别为DNA链前缀与后缀。1与0表示顶点在顶点子集中的状态，若为1则表 示顶点在该顶点子集中，若为〇则表示顶点子集中无该点，且11 I =2 | 0 |。如对图2中的无向 图，其某个顶点子集Κ = {V1，V3，ν5}可以对应编码为双链DNA序歹[
[0042] 步骤2:在试管T中包含4种初始DNA双链分子：
利用 PCR技术，对初始DNA双链分子按照顶点编号，逐位循环进行XPCR交叉连接，XPCR进行的过程 中会伴随DNA双链分子的指数扩增，对于η个顶点的简单无向图，循环η次就得到图所有的顶 点子集(2η个顶点子集）。对于图2的简单图，仅需要5次循环，则试管中生成的DNA双链分子 可以表示图2所有的顶点子集。
[0043] 步骤3:在获得的所有DNA双链分子中，通过指定PCR过程中的5'端-引物与3'端-弓| 物，利用PCR操作实现特定DNA双链分子片段的截取;基于前述DNA双链分子的编码方案，利 用DNA双链分子3 端后缀与5 端前缀相同的特点，通过XPCR操作实现特定DNA双链分子的 连接。具体为通过XPCR操作对含有编码第i个顶点的特定DNA分子序列UiD的DNA分子后面添 加 DNA分子序列β(序列β的长度大于ΙΒΗΒΗ - Βη?ζφ | -一序列两端的竖线表示求取对应 DNA分子序列的长度），以DNA分子片段ω和邱勺后缀分别作为PCR操作的前端与后端引物，对 添加了特定序列β的DNA分子进行指数扩增。扩增后，由于序列邮]长度大于?ΒΗΒη-ΙΙζφ ，以DNA分子的长度做为DNA序列分离的特征条件，通过凝胶电泳对DNA序列进行分离，通过 这种方法可以筛选出含有特定顶点的顶点子集，其详细过程如图6。用此方法，首先复制两 份解空间，一份筛选出试管中含有v2的顶点子集。另一份筛选出含有V4顶点子集的DNA链。将 两份结果混合，即为所有含有^或^顶点子集的DNA链。结果如图7。
[0044] 步骤4:在步骤3的基础上筛选出含有V2或V5顶点子集的DNA链。结果如图7。
[0045]步骤5:利用电泳技术，筛选出步骤3，4所得结果中最短的DNA链。结果为V2。
[0046] 步骤6:对上一步结果求反，即为最终结果。结果为V1V3V4V5。
[0047] 综上所述，我们通过改进的PCR计算模型求解最大团问题，可以避免使用限制性核 酸内切酶，在DNA编码中不需要考虑限制性核酸内切酶的识别位点约束，简化DNA编码，同时 由于DNA序列的分离仅仅依赖于DNA分子的长度，可以大大提高实验过程的稳定性和计算结 果的精度。应用PCR技术可以准确的从所有可能解中筛选特定解，也因为PCR技术需要使用 稳定性更好的双链DNA分子而适合于求解大规模最大团问题。由此说明我们的方法是有效 可行的。
[0048]以上所述，仅为本发明较佳的【具体实施方式】，但本发明的保护范围并不局限于此， 任何熟悉本技术领域的技术人员在本发明披露的技术范围内，根据本发明的技术方案及其 发明构思加以等同替换或改变，都应涵盖在本发明的保护范围内。
【主权项】
1. 基于改进PCR计算模型求解最大团问题的方法，其特征在于，如下步骤： 步骤1:建立无向图的补图； 步骤2:用DNA链表示补图的顶点子集，并对DNA链进行编码，利用PCR技术对DNA链上的 特定片段进行复制并利用XPCR技术生成解空间； 步骤3:给定一条补图边，每条补图边对应两个顶点，筛选出含有这两个顶点的一个或 两个的DNA链，放入试管； 步骤4:对试管中的DNA链重复步骤3，直到所有的补图边均被筛选过； 步骤5:从步骤4所得结果中，利用PCR技术筛选出试管中最短的DNA链作为含有最少顶 点数的子集； 步骤6:对步骤5中所得子集求补，得到最终结果。2. 根据权利要求1所述的基于改进了的PCR计算模型求解最大团问题的方法，其特征在 于:对于给定的无向图G = (V，E)，其中V= {vi, . . .，vn} ,E = {ei, . . .，em}，求解具体步骤如 下： 1) 建立无向图G的补图否， 2) 用DNA序列对补图石中的每个顶点进行DNA序列编码，采用二进制编码顶点子集，编 码格式为其中U1X代表第i个顶点在顶点子集中的状态;并 生成无向图G的所有可能顶点子集，即为解空间； 3) 对补图G中的所有的边互=间，...，乙}进行编号，每条边均由两个顶点唯一确定 4) 给定一条补图G中的边巧，利用PCR技术筛选含有Vi或"的0嫩链，并放入特 定试管T中； 5) 对试管T中DNA链重复步骤4,直到所有的补图边均被筛选过； 6) 利用PCR技术筛选出试管T中，含有最少的顶点的子集，并对这些子集求补，即为最终 结果。3. 根据权利要求1或2所述的基于改进了的PCR计算模型求解最大团问题的方法，其特 征在于:所述DNA链为DNA双链。4. 根据权利要求1所述的基于改进PCR计算模型求解最大团问题的方法，其特征在于， 所述步骤2中生成解空间的具体方法如下：利用PCR技术，对初始DNA双链分子按照顶点编 号，逐位循环进行XPCR交叉连接，XPCR进行的过程中会伴随DNA双链分子的指数扩增，对于η 个顶点的简单无向图，循环η次得到图所有的顶点子集，则试管中生成的DNA双链分子表示 所有的顶点子集，得到解空间。5. 根据权利要求1所述的基于改进PCR计算模型求解最大团问题的方法，其特征在于： 所述步骤3中筛选的方法为通过XPCR操作对含有特定DNA分子序列的DNA分子后面添加指定 序列β，以DNA分子片段ω和β的后缀分别作为PCR操作的前端与后端引物，对添加了特定序 列β的DNA分子进行指数扩增，扩增后以DNA分子的长度作为DNA序列分离的特征条件，通过 凝胶电泳对DNA序列进行分离，筛选出含有特定顶点的顶点子集。
【专利摘要】本发明涉及最大团问题领域，设计了一种基于改进了的PCR计算模型解决最大团问题的方法。该方法对PCR计算模型进行改进,并用于解决最大团问题。此种方法在实验室环境下较易实现，且误差较小，亦可以有效降低计算中各种酶切反应不完全而引起的“噪声”，且DNA编码链为双链DNA分子，比单链编码更为稳定。
【IPC分类】G06N3/12
【公开号】CN105488569
【申请号】CN201510860554
【发明人】张强, 翟伟华, 郑学东
【申请人】大连大学
【公开日】2016年4月13日
【申请日】2015年12月1日
最新回复(0)