DNA计算中的编码设计与分析课件

1、DNA计算中的编码设计与分析DNA计算DNA计算是借助于分子生物技术进行计算的新方法，凭借极大的存储密度和高度并行性，DNA计算为求解NP完全问题提供了一种全新的途径，开创了广阔的应用全景，DNA编码质量的优劣确定了DNA计算的效率，DNA编码数量的多少确定了DNA计算可求解问题的规模，因此核苷酸编码是DNA计算研究中的重要课题。DNA计算机 研究DNA计算领域的专家普遍认为，一旦DNA计算机研制成功，其运算量是目前的传统计算机望尘莫及的，DNA计算机是一个极具开发价值的研究领域。与传统的计算机相比，DNA 计算机具有三个突出的有点：高度的并行性，海量的存储能力，极低的耗能。 1994年，Le

2、onard M.Adleman发表了其著名的DNA计算的研究文章-Molecular Computation of Solutions To Combinatorial Problems。在该篇文章中Adleman通过DNA序列的方法来解决著名的NP完全性问题Hamilton Graph。开创了DNA计算这门学科的先河。DNA计算标志性成果(1) 有向图的每一个顶点都编码为唯一的DNA分子(2) 在一定的反应条件下，代表顶点和代表边的DNA分子相互杂交，相互连接形成长的DNA分子，产生有向 图的路径(3) 最后检测出代表Hamilton路的DNA分子。解的分离解的检测DNA编码问题及其复杂性研

3、究 DNA 计算的编码质量、编码数量、序列长度与 DNA 计算的可靠性、有效性、可扩充性紧密相关。 编码约束条件太强，则难以设计出足够数量的 DNA 序列，限制了DNA 计算的规模；选取的编码约束条件太弱，会导致 DNA 计算出现错误。 选取适当的 DNA 编码约束及约束强度是提高 DNA 计算的设计效率的关键。在 DNA 计算的过程中，单链 DNA 分子在溶液中任意扩散，溶液中会同时存在单链 DNA 分子，及其三种相关的 DNA 分子： DNA 反链、 DNA 补链、 DNA 反补链，它们都可能参与 DNA 计算的杂交反应。本文用 X 表示单链 DNA 序列， XC表示 X 的Watson-

4、Crick 补序列， XR 表示 X 的反向序列， XRC 表示 X 的反补序列。杂交反应是 DNA 计算中最主要、最核心的反应。杂交反应具有方向性，通常是53的单链 DNA 分子和 35的单链 DNA 分子在氢键的作用下相互绑定形成双螺旋结构。杂交分为特异性杂交和非特异性杂交，特异性杂交即为单链 DNA 分子 X 和其补链 XC 的碱基对完全互补的杂交反应，除此之外的其它杂交反应均为非特异性杂交。 DNA 编码问题可以表示为：设 X=5x1x2xn3为一个长度为 n 的单链 DNA序列，其中 xi 代表碱基， xi A,C,G,T。设 S 是长度为 n 的 DNA 序列集合，显然集合 S 的

5、大小为|S|=4n。求 S 的一个子集 ，使得 C 中的任意两条序列 X， Y 满足给定的 DNA 编码约束准则，如汉明距离、相似度、 H-measure、解链温度、最小自由能等。这些编码准则可以分成 4 类： 1) 碱基距离约束； 2) DNA 二级结构约束； 3) DNA化学特性约束； 4) 限定的 DNA 子序列约束。DNA 计算的基本问题是提高 DNA 计算的可靠性、有效性和可扩充性。可靠性和有效性与 DNA 编码的质量息息相关，它要求任意两非同源 DNA 序列不发生非特异性杂交。可扩充性是指在保证可靠性的前提下，提高解决问题的规模。这就是说，编码质量越高， DNA 计算的可靠性越高；

6、编码数量越多，解决问题的应用规模也就越大。但事实上，编码质量和数量之间存在相互制约的关系：编码质量越高则满足条件的编码数量就越少DNA 编码受到碱基距离约束、化学热力学约束、 DNA 二级结构约束、 DNA 分子组成约束等多种编码规则的组合约束，在计算量上是 NP 完全问题， 即随着问题规模的增大，对于求解最优 DNA 序列集合的计算量呈指数增长。如果设计链长为 n 的一组 DNA 序列，由于每位的碱基有A,T,G,C四种可能，其解空间为 4n。如果要求 DNA序列集合最大，仅考虑 DNA 序列之间非特异性杂交的限制，对于长度为 n 的 DNA 序列，就等价于求解 4n 个顶点的图的最大独立集

7、问题。DNA 序列杂交关系网络：给定一个单链 DNA 杂交网络 N(S, H)， S 为长度为 n 的DNA 序列集合， H 为 S 中任两条 DNA 杂交关系的集合，如图 3.3 所示。 si代表单链DNA 序列，h(si, sj) H 表示 DNA 序列 si和 sj可以非特异性杂交。设 S是 S 的子集 S S，如果对任意两个 DNA 序列 si， sj S， h(si, sj) H，则 S中任意两个序列都不能非特异性杂交，则 S为 DNA 计算可用编码集合，即为 DNA 编码问题的解。黑色的点代表相互不能非特异性杂交的 DNA 分子。DNA 序列杂交关系网络图的独立集问题：给定一个图

8、G=(V, E)， V 是顶点 vi 的集合， E 是边 e(vi, vj)的集合，如下图 所示。 V是 V 的子集 V V，如果对任意两个顶点 vi, vj V， e(vi, vj) E，则称 V为 G 的一个独立集。黑色的点表示图的一个独立集图的独立集问题DNA 序列设计问题等价于图的独立集问题。为了提高 DNA 计算模型的可扩充性，以解决更大规模的计算问题， DNA 编码问题需找到尽可能多的满足约束的DNA 序列，即求解满足约束的最大的 DNA 集合。而求解图的最大独立集为 NP 完全问题。因此， DNA 编码问题的计算量也是为 NP 完全的。DNA 编码约束及分析 常见的 DNA 编码

9、约束可以分成 4 类：1)基于汉明距离的编码约束； 2)DNA 二级结构约束； 3)DNA 化学特性约束；4)DNA 子序列碱基组成约束。汉明距离约束两个 DNA 序列的汉明距离是所有对应位置字符不同的总数。设 DNA 序列 X 和 Y分别为 X=5x1x2xn3和 Y=5y1y2yn3，其汉明距离记为 H(X,Y)，计算公式如下图所示：在 DNA 编码设计中，汉明距离用来描述两个 DNA 序列的不相似程度。汉明距离越大，说明两个 DNA 序列 X 和 Y 之间不同的碱基个数就越多，因此它们相同的碱基个数就少，从而序列 X 和 Y 的补序列 YC之间互补的碱基个数就少，因此 X 和 YC 之间

10、发生特异性杂交的可能性就越小例如：长度为 13bp 的 DNA 序列 X 和 Y，其汉明距离仅为 4，因此 X 和 YC容易发生错配杂交H(*,*)表示汉明距离，当 k 0 时， k 表示右移；当 k 0 时， k表示左移， 表示移动的位数。如果 X 和 Y 经过距离为 k 的移动后汉明距离减小，那么 Similarity的值也随之减小。 Similarity 值较小时序列 X 和 Y 就非常相似，序列 X 和 YC 之间互补的碱基就多，容易出现非特异性杂交；当 Similarity 值较大时序列 X 和 Y 相同的碱基则很少， X 和 YC 之间互补碱基就很少，从而 X 和 YC 之间不会出

11、现非特异性杂交DNA 二级结构约束 单链 DNA 分子产生二级结构通常由自身反向折叠而形成，发卡结构为典型的自身折叠结构，如下图所示。许多以特异性杂交反应为基础的 DNA 计算模型，都要求避免单链 DNA 形成二级结构，这样单链 DNA 分子才能和自身的补链充分有效的发生特异性杂交。DNA 化学特性约束DNA 实验要求参加反应的 DNA 序列具有相似的化学特性。例如， PCR 通常需要统一的扩增效果。 DNA 化学特性约束通常包含自由能约束、解链温度约束、 GC 含量约束。GC 含量约束(DNA 序列的 GC 含量影响该序列的化学性质，例如解链温度可以由 GC 含量计算得到。 GC 含量即为

12、DNA 序列中碱基 G 和碱基 C 的个数或者百分比。同理，与其相对应的另外两个碱基的数量为 AT 含量，即 DNA 序列中碱基 A 和碱基 T 的个数或百分比解链温度(Tm)是双链 DNA 分子在加温变性过程中，有 50%的 DNA 分子打开双链变成单链时的温度。解链温度它是评价 DNA 分子化学热力学稳定性的一个重要参数。DNA 计算要求 DNA 分子具有一致的解链温度。影响解链温度 Tm 的因素为： DNA分子组成、 DNA 分子浓度、溶液 PH 值等。解链温度约束 任意两个 DNA 分子 X 和 Y 的杂交反应可用如下的化学方程式表示： X+Y YX X+Y |G| YX 单链 DNA

13、 分子 X、 Y 释放能量，形成一条双链 X+Y YX+|G| 双链 DNA 分子 YX 吸收能量，分成两条单链化学自由能约束其中 YX 代表杂交后的双链。由化学热力学可知，杂交反应的方向为自由能减小的方向。自由能是参加化学反应的单链 DNA 分子从高能量状态自发的向低能量状态的双链分子变迁所释放的能量。自由能(G)是两单链 DNA 分子杂交形成双链 DNA 的能量变化。由于 DNA 杂交通常放出热量，因此自由能的变化通常为负值，即 G0。 G 是 DNA 双链稳定性的度量，其绝对值越高， DNA 双链越稳定。两单链 DNA 分子发生非特异性杂交，是由于它们形成双链时 G 较大，形成的双链较稳定。为防止 DNA 序列间的非特异性杂交，则要求 DNA 解集 C 中的序列都满足最小自由能约束。给定最小自由能变化阈值Gmin，使 DNA 解集 C 中任意两个 DNA 分子发生非特异性杂交的 G 都大于该阈Gmin，从而不能形成稳定的双链结构，阻止非特异性杂交的发生。自由能(G)DNA 计算编码理论研究进展Feldkamp等人利用有向树编码 DNA。通过限制定长的子序列仅允许出现一次，使设计的 DNA 序列尽可能唯一，这种编码方法可以