第三讲-限制图谱与多重图谱课件

第三讲第三讲 限制图谱与多重图谱限制图谱与多重图谱生命是什么？生命是什么？n生命是物质的一种生命是物质的一种运动形态运动形态 n生命的基本单位是细胞，它是由蛋白质、生命的基本单位是细胞，它是由蛋白质、核酸、氨基酸等生物大分子组成的物质核酸、氨基酸等生物大分子组成的物质系统系统 n生命现象就是复杂系统中生命现象就是复杂系统中物质物质、能量能量和和信息信息三个量综合运动与传递的表现三个量综合运动与传递的表现 2教学要求教学要求n了解图、区间图、片段大小的度量问题了解图、区间图、片段大小的度量问题n理解理解多重图谱中双消化问题、双消化问多重图谱中双消化问题、双消化问题的多重解题的多重解n掌握掌握从一条路到另一条路、限制图谱及从一条路到另一条路、限制图谱及边界块图、限制图谱的盒变换边界块图、限制图谱的盒变换 33.1 3.1 引言引言n当外来当外来DNADNA引入到一个细菌中，通常不能引入到一个细菌中，通常不能执行任何遗传功能执行任何遗传功能n细菌已进化出一些有效方法，保护自己细菌已进化出一些有效方法，保护自己防止防止DNADNA入侵入侵n一组称为一组称为限制内切限制内切核酸酶核酸酶通过切割通过切割DNADNA执执行这种保护，限制入侵行这种保护，限制入侵DNADNA的活性的活性4限制位点限制位点n限制酶可看成是细菌的免疫系统限制酶可看成是细菌的免疫系统n限制酶能在限制酶能在DNADNA特定短模式上将特定短模式上将DNADNA切开，切开，这些模型称为这些模型称为限制位点限制位点n大约已发现大约已发现300300种限制酶种限制酶及他们切割的大及他们切割的大约约100100个个不同的不同的限制位点限制位点53.2 3.2 图论与计算生物学图论与计算生物学n图论是计算机科学与离散数学的一个课图论是计算机科学与离散数学的一个课题，为生物学中限制图谱的若干数据结题，为生物学中限制图谱的若干数据结构和关系提供一自然的数学模型构和关系提供一自然的数学模型n偶图，二分图的概念偶图，二分图的概念6 图论的诞生图论的诞生n图论起源于图论起源于17361736年年EulerEuler的一篇文章，该的一篇文章，该文章解决了文章解决了KonigsbergKonigsberg（哥尼斯堡）七（哥尼斯堡）七桥问题。桥问题。nKonigsbergKonigsberg（哥尼斯堡）七桥问题：能（哥尼斯堡）七桥问题：能否从某点出发通过每桥恰好回到原地？否从某点出发通过每桥恰好回到原地？7 图的定义图的定义n设设V V是一个非空集合，是一个非空集合，E E是一个是一个V V中元素的无序中元素的无序对构成的多重集，有序对对构成的多重集，有序对G=G=（V,EV,E）称为一个）称为一个图，其中，图，其中，V V称为顶点集，其元素称为顶点或称为顶点集，其元素称为顶点或点，点，E E称为边集，其元素称为边。称为边集，其元素称为边。n以上定义为以上定义为无向图无向图n类似有向图定义类似有向图定义8偶图偶图n偶图是一个图，其中顶点集偶图是一个图，其中顶点集V=VV=V1 1VV2 2,V V1 1VV2 2=且边且边e=u,ve=u,v，uVuV1 1和和v Vv V2 2或或uVuV2 2和和v Vv V1 19n定理：图中任意奇顶点定理：图中任意奇顶点的个数必为偶数的个数必为偶数10n推论：在一次围棋比赛中，推论：在一次围棋比赛中，下过奇数盘棋的人数是偶下过奇数盘棋的人数是偶数数11问题？问题？n共有共有100100块糖，从糖，从20132013年元旦开始吃，每天年元旦开始吃，每天至少吃一至少吃一块，共有多少种吃法？，共有多少种吃法？123.3 3.3 区间图区间图n区间图的研究源于区间图的研究源于19591959年年BenzerBenzer（研究（研究细菌结构）的一篇文章细菌结构）的一篇文章n基因沿基因沿染色体线性排列染色体线性排列n区间图区间图是分子生物学现代实践的核心是分子生物学现代实践的核心13 图谱图谱A A和图谱和图谱B BnA n假设假设A A图谱假设有图谱假设有4 4个限制位点个限制位点 nBn 假设假设B B图谱有图谱有4 4个限制位点个限制位点14。限制图谱限制图谱A BA Bn则则A BA B上有上有7 7个限制位点个限制位点15区间图区间图n区间图是分子生物学的现代实践核心区间图是分子生物学的现代实践核心n区间图区间图与与限制图谱限制图谱相联系相联系n限制图谱指出特定限制图谱指出特定DNADNA某些位点的位置某些位点的位置（位点是特定序列位点是特定序列）16A B的图谱的图谱nA A图谱有图谱有3 3个限制位点个限制位点nB B图谱有图谱有4 4个限制位点个限制位点nA AB B的图谱的图谱是是A A图谱与图谱与B B图谱区间重叠，图谱区间重叠，可能有可能有7 7个位点个位点17区间图区间图n区间是随意标号的区间是随意标号的n限制酶能把限制酶能把DNA切成许多区间，能识别这些位点的单切成许多区间，能识别这些位点的单个区间，却不能直接观测到这些小区间的顺序，而是个区间，却不能直接观测到这些小区间的顺序，而是试图确定试图确定A区间是否与区间是否与B区间重叠区间重叠n由重叠数据构造图谱由重叠数据构造图谱n形式上说：如果两区间有非空的交，则说两区间重叠形式上说：如果两区间有非空的交，则说两区间重叠18n限制图谱构造最困难的内容是限制图谱构造最困难的内容是确定重叠确定重叠数据数据19定理定理下列命题等价下列命题等价（1 1）偶图偶图G G（A,BA,B）是由某是由某限制图谱限制图谱构成构成 的图的图（2 2）G G（A,BA,B）是没有是没有孤立点孤立点的的偶区间图偶区间图（3 3）I I（A,BA,B）通过行和列的通过行和列的置换置换变成每变成每行和每列的行和每列的1 1都恰好处于这些台阶之一都恰好处于这些台阶之一20区间图区间图n区间图可被识别并能找到他的表现，所区间图可被识别并能找到他的表现，所用时间是用时间是定点数加边数定点数加边数的的线性时间线性时间 O(V+E)(V是定点数，是定点数，E边数边数)213.4 3.4 片段大小的度量片段大小的度量nDNADNA的长度或大小是通过一个称为的长度或大小是通过一个称为凝胶电凝胶电泳泳的的过程度量过程度量的的n凝胶指凝胶指固态基质固态基质nDNADNA带带负电荷分子负电荷分子，当凝胶被放在电场下，当凝胶被放在电场下，DNADNA向正极移动向正极移动22片段大小的度量片段大小的度量nDNADNA的迁移距离是的迁移距离是DNADNA大小（长度）的函大小（长度）的函数数n迁移距离迁移距离D D与与DNADNA大小或距离大小或距离L L的对数成线的对数成线性关系，即性关系，即D Da+blog(L)(b0)a+blog(L)(b0)n负斜率负斜率b b意义：长的意义：长的DNADNA在凝胶基质中缠在凝胶基质中缠结，从而移动不远，而小的结，从而移动不远，而小的DNADNA穿过基质穿过基质非常容易非常容易23片段大小的度量片段大小的度量n迁移距离迁移距离D D不是一个点，而是一个污迹，不是一个点，而是一个污迹，科学家不能精确测量污迹。科学家不能精确测量污迹。n可用可用统计学正态分布统计学正态分布解释解释nDNADNA小的片段可被度量的很精确，而大的小的片段可被度量的很精确，而大的片段可能有非常大的误差片段可能有非常大的误差243.5 3.5 多重图谱多重图谱n用下列方法能能确定重叠区间用下列方法能能确定重叠区间A Ai iBBj jn首先，用酶首先，用酶A A将将DNADNA打碎，然后对打碎，然后对A A的每个的每个片段片段A Ai i再用酶再用酶B B将它打碎将它打碎n如果所有如果所有ABAB的尺寸是唯一的，则的尺寸是唯一的，则ABAB的每一个片段唯一指定给的每一个片段唯一指定给A Ai i25多重图谱多重图谱nABAB片段的唯一性通常有由这些片段长片段的唯一性通常有由这些片段长度的唯一性给出度的唯一性给出n按相反次序重复实验，则按相反次序重复实验，则 ABAB的每个片的每个片段唯一指定给段唯一指定给B Bj j26n通通常常不不是是直直接接从从重重叠叠A Ai iBBj j的的实实验验数数据据确确定定图图谱谱，而而是是做做两两个个单单一一消消化化和和一一个个双双消化消化273.6 双消化问题双消化问题(DDP)n线性线性DNADNA的的双消化在无测量误差双消化在无测量误差的最简单的最简单情况，把这个问题叫双消化问题情况，把这个问题叫双消化问题（Double Digesting Problem,Double Digesting Problem,DDPDDP）n限制酶在一些特定模式出现的地方将长限制酶在一些特定模式出现的地方将长为为L L的的DNADNA分子切成一些片段，分子切成一些片段，并将这些并将这些片段长度记录下来片段长度记录下来28DDPDDP（双消化问题）是（双消化问题）是NPNP完全的完全的nP P类：类：确定性图灵机多项式时间可计算的确定性图灵机多项式时间可计算的 问题类（能求出精确解）问题类（能求出精确解）nNPNP类：确定性图灵机多项式时间可验证的类：确定性图灵机多项式时间可验证的 问题类（可能解多项式时间可验证）问题类（可能解多项式时间可验证）nNPCNPC类：问题类：问题A A为为NPCNPC类，当且仅当类，当且仅当A A属于属于NP NP 类且所有类且所有NPNP类问题均可多项式变换到类问题均可多项式变换到A A29双消化问题双消化问题(DDP)n单独使用某种酶后，有一列片段长度作为数据na=A=ai:1i n来自第一个分解nb=B=bi:1i m来自第二个分解30双消化问题双消化问题(DDP)当两种限制酶同时使用，当两种限制酶同时使用，DNADNA在两组限制模在两组限制模式的所有出现处被切割，得到一列双消式的所有出现处被切割，得到一列双消化片段长度化片段长度nc=A B=ci:1i l来自第一个分来自第一个分解解31双消化问题双消化问题(DDP)n用DDP(a,b,c)来表示求图谱A,B的问题，使得A=a,B=b及C=A B=c一般，一般，A,B和和C是重集：可能有一是重集：可能有一些片段长的值出现不止一次些片段长的值出现不止一次32n约定：集合约定：集合A,BA,B和和C C是有序是有序的，即：若：的，即：若：ij,ij,有有a ai iaaj jn对于集合对于集合BB和和C C也一样也一样n当然：当然：a ai i=bi i=c=ci i=L=L333.6.1 3.6.1 双消化问题的多重解双消化问题的多重解n在许多实例中，双消化问题的解是不唯在许多实例中，双消化问题的解是不唯一的一的n举例举例P37P37na=A=1,3,3,12,n=4a=A=1,3,3,12,n=4nb=B=1,2,3,3,4,6,m=6b=B=1,2,3,3,4,6,m=6nc=C=1,1,1,1,2,2,2,3,6c=C=1,1,1,1,2,2,2,3,634nA A和和B B片段次序决定片段次序决定C=AC=AB B片段和这些片片段和这些片段次序段次序n最简单是组合学给出最简单是组合学给出n!*m!=4!*6!n!*m!=4!*6!个图谱个图谱构形构形35n3 3在在A A分解中重复分解中重复2 2次，次，3 3在在B B分解中也重分解中也重复了复了2 2次次n在不能区分长度相同片段情况下，上例在不能区分长度相同片段情况下，上例中：中：n=4,m=6n=4,m=6有（有（4 4！*6 6！）！）/（2 2！2!2!）=4320=4320个图谱构形个图谱构形36KingmanKingman定理定理n概率论中非常有用的工具概率论中非常有用的工具n双消化解的个数随长度指数级增长双消化解的个数随长度指数级增长37概率算法与随机算法的应用概率算法与随机算法的应用区别区别在概率算法概率算法中，我们仅关心组合对象是否存在，若一个事件的发生概率为非零，就足够了在随机算法随机算法中，算法性能是非常重要的，我们不能容忍非常小的成功概率不能容忍非常小的成功概率。38n随机算法在计算生物学中，可利用随机算法在计算生物学中，可利用nLovsz局部引理局部引理来证明事件发生存在性来证明事件发生存在性n利用Markov和Chebyshev不等式来证明近似算法的有界性的有界性 39n假设有假设有n n个相互独立的事件，每个事件发个相互独立的事件，每个事件发生的概率至多是生的概率至多是1/21/2，那么，那么n n个事件都不个事件都不发生的概率至少是发生的概率至少是2 2-n-nn LovLov szsz局部引理将这个问题推广到了每局部引理将这个问题推广到了每个事件都和另外的一小部分事件非独立个事件都和另外的一小部分事件非独立的情况。的情况。40KingmanKingman定理定理(次可加遍历次可加遍历)n对非负整数对非负整数s,t,0st,s,t,0st,设设 X Xs,ts,t是一组随机变量，是一组随机变量，满足以下条件满足以下条件（1 1）只要）只要stu,Xst1 t1 满足满足g gt tKt,Kt,则有：则有：limXlimXs,ts,t/t=m(m0)(t/t=m(m0)(t)以以 概率为概率为 1 1存在且是一阶矩收敛存在且是一阶矩收敛 41定理定理1 1n假设对两种酶，这些位点分别以概率假设对两种酶，这些位点分别以概率p pa a,p,pb b(0,1)(0,1)独立分布。设独立分布。设Y Ys,ts,t是第是第s s个个和第和第t t个重合切割位点间解的个数，则存个重合切割位点间解的个数，则存在一个有限常数在一个有限常数m0m0，使，使 limlog(Ylimlog(Y0,t0,t)/t=m(m0)(t)/t=m(m0)(t)42定理定理2 2n假设对两种酶，这些位点分别以概率假设对两种酶，这些位点分别以概率p pa a,p,pb b(0,1)(0,1)独立分布。设独立分布。设Z Zl l是从是从0 0开始开始到常为到常为l l的一段的解数，则：的一段的解数，则：lim(log lim(log Z Zl l/l)=m /l)=m p pa ap pb b(m0)(l(m0)(l)n则则Z Zl l exp(exp(m m p pa ap pb bl)l)（l l为为DNADNA子片段长子片段长度）说明：双消化问题的解作为度）说明：双消化问题的解作为DNADNA片段片段长度的函数指数的增长长度的函数指数的增长433.7 3.7 多重解分类多重解分类n对于长的对于长的DNADNA有许多有许多DDPDDP的解，这样的结的解，这样的结果困难性什么也不知道果困难性什么也不知道n不知道指数增长率、确定不知道指数增长率、确定KingmanKingman定理中定理中常数常数K K也很困难也很困难n具有多重解的小例子在极长的具有多重解的小例子在极长的DNADNA中也存中也存在。在。443.7.13.7.1多重解的反射性多重解的反射性n只要只要a,ba,b是是DDPDDP（双消化问题）的解，（双消化问题）的解，则则a a和和b b的转置的转置a a,b,b也是也是DDPDDP的解，称：的解，称：（a a,b,b）是（）是（a,ba,b）的）的反射反射453.7.23.7.2重叠等价重叠等价n许多不同的图谱可能有同样的重叠数据，许多不同的图谱可能有同样的重叠数据，具有同一重叠数据的这些解称为具有同一重叠数据的这些解称为重叠等重叠等价价46重叠尺寸等价重叠尺寸等价n图谱图谱aa1 1,a,a2 2,a an n,b,b1 1,b,b2 2,b bm m 和和 c c1 1,c,c2 2,c cl l 的的DD PDD P两个解有同样一组两个解有同样一组重叠尺寸数据，重叠尺寸数据，则称则称DD PDD P两个解两个解重叠尺寸等价重叠尺寸等价47边的交错和欧拉路边的交错和欧拉路n一个路或回路的相继的边的染色不同，一个路或回路的相继的边的染色不同，称为称为交错的交错的n如果一个路或回路通过图的每条边恰好如果一个路或回路通过图的每条边恰好一次，则称该路一次，则称该路是欧拉的是欧拉的483.7.3 3.7.3 重叠尺寸等价重叠尺寸等价n命题：命题：当图谱当图谱aa1 1,a,a2 2,a an n 和和bb1 1,b,b2 2,b bm m 每一个都有互不相同的元素，每一个都有互不相同的元素，则则重叠等价重叠等价与与重叠尺寸等价重叠尺寸等价相同相同n片段的尺寸一般都是知道的片段的尺寸一般都是知道的n重叠等价推出重叠重叠等价推出重叠尺寸尺寸等价等价493.7.4 Kotig 3.7.4 Kotig 定理定理n设设G G是边染色的是边染色的连通图连通图且顶点的度为偶数，且顶点的度为偶数，则当且仅当则当且仅当G G是是平衡图平衡图时，时，G G存在一个交存在一个交错的错的欧拉回路欧拉回路n平衡图：每个顶点都是平衡的图平衡图：每个顶点都是平衡的图nMaxdMaxdc c(v,E)(v,E)d(v,E)/2 d(v,E)/2 则称顶点则称顶点v v是是平平衡的衡的(d dc c(v,E)(v,E)是与是与v v关联的关联的E E的的c c色边的边色边的边数数)50n二阶与三阶行列式的二阶与三阶行列式的计算计算51作业作业1、DNA片段大小是如何度量的？片段大小是如何度量的？2 2、若、若a=A=1,3,3,12,n=4a=A=1,3,3,12,n=4 b=B=1,2,3,3,4,6,m=6 b=B=1,2,3,3,4,6,m=6 则则c=c=A B可能有多少种图谱可能有多少种图谱？3 3、如何理解双消化问题的解作为、如何理解双消化问题的解作为DNADNA片段片段长度的函数指数的增长长度的函数指数的增长52