第三讲 限制图谱与多重图谱

第三讲限制图谱与多重图谱生命是什么？生命是物质的一种运动形态

生命的基本单位是细胞，它是由蛋白质、核酸、氨基酸等生物大分子组成的物质系统生命现象就是复杂系统中物质、能量和信息三个量综合运动与传递的表现2教学要求了解图、区间图、片段大小的度量问题理解多重图谱中双消化问题、双消化问题的多重解掌握从一条路到另一条路、限制图谱及边界块图、限制图谱的盒变换33.1引言当外来DNA引入到一个细菌中，通常不能执行任何遗传功能细菌已进化出一些有效方法，保护自己防止DNA入侵一组称为限制内切核酸酶通过切割DNA执行这种保护，限制入侵DNA的活性4限制位点限制酶可看成是细菌的免疫系统限制酶能在DNA特定短模式上将DNA切开，这些模型称为限制位点大约已发现300种限制酶及他们切割的大约100个不同的限制位点53.2图论与计算生物学图论是计算机科学与离散数学的一个课题，为生物学中限制图谱的若干数据结构和关系提供一自然的数学模型偶图，二分图的概念6

图论的诞生图论起源于1736年Euler的一篇文章，该文章解决了Konigsberg（哥尼斯堡）七桥问题。Konigsberg（哥尼斯堡）七桥问题：能否从某点出发通过每桥恰好回到原地？7

图的定义设V是一个非空集合，E是一个V中元素的无序对构成的多重集，有序对G=（V,E）称为一个图，其中，V称为顶点集，其元素称为顶点或点，E称为边集，其元素称为边。以上定义为无向图类似有向图定义8偶图偶图是一个图，其中顶点集V=V1∪V2,V1∩V2=Ø且边e={u,v}，u∈V1和v∈V2或u∈V2和v∈V19定理：图中任意奇顶点的个数必为偶数10推论：在一次围棋比赛中，下过奇数盘棋的人数是偶数11问题？共有100块糖，从2013年元旦开始吃，每天至少吃一块，共有多少种吃法？123.3区间图区间图的研究源于1959年Benzer（研究细菌结构）的一篇文章基因沿染色体线性排列区间图是分子生物学现代实践的核心13

图谱A和图谱BA假设A图谱假设有4个限制位点

B

假设B图谱有4个限制位点14。…限制图谱A∧B则A∧B上有7个限制位点15区间图区间图是分子生物学的现代实践核心区间图与限制图谱相联系限制图谱指出特定DNA某些位点的位置（位点是特定序列）16A∧B的图谱A图谱有3个限制位点B图谱有4个限制位点A∧B的图谱是A图谱与B图谱区间重叠，可能有7个位点17区间图区间是随意标号的限制酶能把DNA切成许多区间，能识别这些位点的单个区间，却不能直接观测到这些小区间的顺序，而是试图确定A区间是否与B区间重叠由重叠数据构造图谱形式上说：如果两区间有非空的交，则说两区间重叠18限制图谱构造最困难的内容是确定重叠数据19定理下列命题等价（1）偶图G（A,B）是由某限制图谱构成的图（2）G（A,B）是没有孤立点的偶区间图（3）I（A,B）通过行和列的置换变成每行和每列的1都恰好处于这些台阶之一20区间图区间图可被识别并能找到他的表现，所用时间是定点数加边数的线性时间

O(V+E)(V是定点数，E边数)213.4片段大小的度量DNA的长度或大小是通过一个称为凝胶电泳的过程度量的凝胶指固态基质DNA带负电荷分子，当凝胶被放在电场下，DNA向正极移动22片段大小的度量DNA的迁移距离是DNA大小（长度）的函数迁移距离D与DNA大小或距离L的对数成线性关系，即D︽a+blog(L)(b<0)负斜率b意义：长的DNA在凝胶基质中缠结，从而移动不远，而小的DNA穿过基质非常容易23片段大小的度量迁移距离D不是一个点，而是一个污迹，科学家不能精确测量污迹。可用统计学正态分布解释DNA小的片段可被度量的很精确，而大的片段可能有非常大的误差243.5多重图谱用下列方法能能确定重叠区间Ai∩Bj首先，用酶A将DNA打碎，然后对A的每个片段Ai再用酶B将它打碎如果所有A∩B的尺寸是唯一的，则A∩B的每一个片段唯一指定给Ai25多重图谱A∩B片段的唯一性通常有由这些片段长度的唯一性给出按相反次序重复实验，则A∩B的每个片段唯一指定给Bj26通常不是直接从重叠Ai∩Bj的实验数据确定图谱，而是做两个单一消化和一个双消化273.6双消化问题(DDP)线性DNA的双消化在无测量误差的最简单情况，把这个问题叫双消化问题（DoubleDigestingProblem,DDP）限制酶在一些特定模式出现的地方将长为L的DNA分子切成一些片段，并将这些片段长度记录下来28DDP（双消化问题）是NP完全的P类：确定性图灵机多项式时间可计算的问题类（能求出精确解）NP类：确定性图灵机多项式时间可验证的

问题类（可能解多项式时间可验证）NPC类：问题A为NPC类，当且仅当A属于NP类且所有NP类问题均可多项式变换到A29双消化问题(DDP)单独使用某种酶后，有一列片段长度作为数据a=‖A‖={ai:1≤i≤n}来自第一个分解b=‖B‖={bi:1≤i≤m}来自第二个分解30双消化问题(DDP)当两种限制酶同时使用，DNA在两组限制模式的所有出现处被切割，得到一列双消化片段长度c=‖A∧B‖={ci:1≤i≤l}来自第一个分解31双消化问题(DDP)用DDP(a,b,c)来表示求图谱[A,B]的问题，使得‖A‖=a,‖B‖=b及‖C‖=‖A∧B‖=c一般，‖A‖,‖B‖和‖C‖是重集：可能有一些片段长的值出现不止一次32约定：集合‖A‖,‖B‖和‖C‖是有序的，即：若：i≤j,有ai≤aj对于集合‖B‖和‖C‖也一样当然：∑ai=∑bi=∑ci=L333.6.1双消化问题的多重解在许多实例中，双消化问题的解是不唯一的举例P37a=‖A‖={1,3,3,12},n=4b=‖B‖={1,2,3,3,4,6},m=6c=‖C‖={1,1,1,1,2,2,2,3,6}34A和B片段次序决定C=A∧B片段和这些片段次序最简单是组合学给出n!*m!=4!*6!个图谱构形353在A分解中重复2次，3在B分解中也重复了2次在不能区分长度相同片段情况下，上例中：n=4,m=6有（4！*6！）/（2！2!）=4320个图谱构形36Kingman定理概率论中非常有用的工具双消化解的个数随长度指数级增长37概率算法与随机算法的应用区别在概率算法中，我们仅关心组合对象是否存在，若一个事件的发生概率为非零，就足够了在随机算法中，算法性能是非常重要的，我们不能容忍非常小的成功概率。38随机算法在计算生物学中，可利用Lovász局部引理来证明事件发生存在性利用Markov和Chebyshev不等式来证明近似算法的有界性

39假设有n个相互独立的事件，每个事件发生的概率至多是1/2，那么n个事件都不发生的概率至少是2-n

Lovász局部引理将这个问题推广到了每个事件都和另外的一小部分事件非独立的情况。40Kingman定理(次可加遍历)对非负整数s,t,0≤s≤t,设Xs,t是一组随机变量，满足以下条件（1）只要s<t<u,Xs,u≤Xs,t+Xt,u;（2）{Xs,t}的联合分布与{Xs+1,t+1}的联合分布一样（3）期望gt=E[X0,t]存在，并对某个常熟K和所有t>1

满足gt≥Kt,则有：limXs,t/t=m(m>0)(t→∞)以概率为1存在且是一阶矩收敛

41定理1假设对两种酶，这些位点分别以概率pa,pb∈(0,1)独立分布。设Ys,t是第s个和第t个重合切割位点间解的个数，则存在一个有限常数m>0，使

limlog(Y0,t)/t=m(m>0)(t→∞)42定理2假设对两种酶，这些位点分别以概率pa,pb∈(0,1)独立分布。设Zl是从0开始到常为l的一段的解数，则：lim(logZl/l)=mpapb(m>0)(l→∞)则Zl

≈exp(mpapbl)（l为DNA子片段长度）说明：双消化问题的解作为DNA片段长度的函数指数的增长433.7多重解分类对于长的DNA有许多DDP的解，这样的结果困难性什么也不知道不知道指数增长率、确定Kingman定理中常数K也很困难具有多重解的小例子在极长的DNA中也存在。443.7.1多重解的反射性只要a,b是DDP（双消化问题）的解，则a和b的转置a’,b’也是DDP的解，称：（a’,b’）是（a,b）的反射453.7.2重叠等价许多不同的图谱可能有同样的重叠数据，具有同一重叠数据的这些解称为重叠等价46重叠尺寸等价图谱{a1,a2,…an},{b1,b2,…bm}和{c1,c2,…cl}的DDP两个解有同样一组重叠尺寸数据，

则称DDP两个解重叠尺寸等价47边的交错和欧拉路一个路或回路的相继的边的染色不同，称为交错的如果一个路或回路通过图的每条边恰好一次，则称该路是欧拉的483.7.3重叠尺寸等价命题：当图谱{a1,a2,…an}和{b1,b2,…bm}每一个都有互不相同的元素，则重叠等价与重叠尺寸等价相同片段的尺寸一般都是知道的重叠等价推出重叠尺寸等价493.7.4Kotig定理设G是边染色的连通图且顶点的度为偶数，则当且仅当G是平衡图时，G存在一个交错的欧拉回路平衡图：每个