第三講 限制圖譜與多重圖譜

第三講限制圖譜與多重圖譜生命是什么？生命是物質(zhì)的一種運(yùn)動(dòng)形態(tài)

生命的基本單位是細(xì)胞，它是由蛋白質(zhì)、核酸、氨基酸等生物大分子組成的物質(zhì)系統(tǒng)生命現(xiàn)象就是復(fù)雜系統(tǒng)中物質(zhì)、能量和信息三個(gè)量綜合運(yùn)動(dòng)與傳遞的表現(xiàn)2教學(xué)要求了解圖、區(qū)間圖、片段大小的度量問(wèn)題理解多重圖譜中雙消化問(wèn)題、雙消化問(wèn)題的多重解掌握從一條路到另一條路、限制圖譜及邊界塊圖、限制圖譜的盒變換33.1引言當(dāng)外來(lái)DNA引入到一個(gè)細(xì)菌中，通常不能執(zhí)行任何遺傳功能細(xì)菌已進(jìn)化出一些有效方法，保護(hù)自己防止DNA入侵一組稱為限制內(nèi)切核酸酶通過(guò)切割DNA執(zhí)行這種保護(hù)，限制入侵DNA的活性4限制位點(diǎn)限制酶可看成是細(xì)菌的免疫系統(tǒng)限制酶能在DNA特定短模式上將DNA切開(kāi)，這些模型稱為限制位點(diǎn)大約已發(fā)現(xiàn)300種限制酶及他們切割的大約100個(gè)不同的限制位點(diǎn)53.2圖論與計(jì)算生物學(xué)圖論是計(jì)算機(jī)科學(xué)與離散數(shù)學(xué)的一個(gè)課題，為生物學(xué)中限制圖譜的若干數(shù)據(jù)結(jié)構(gòu)和關(guān)系提供一自然的數(shù)學(xué)模型偶圖，二分圖的概念6

圖論的誕生圖論起源于1736年Euler的一篇文章，該文章解決了Konigsberg（哥尼斯堡）七橋問(wèn)題。Konigsberg（哥尼斯堡）七橋問(wèn)題：能否從某點(diǎn)出發(fā)通過(guò)每橋恰好回到原地？7

圖的定義設(shè)V是一個(gè)非空集合，E是一個(gè)V中元素的無(wú)序?qū)?gòu)成的多重集，有序?qū)=（V,E）稱為一個(gè)圖，其中，V稱為頂點(diǎn)集，其元素稱為頂點(diǎn)或點(diǎn)，E稱為邊集，其元素稱為邊。以上定義為無(wú)向圖類似有向圖定義8偶圖偶圖是一個(gè)圖，其中頂點(diǎn)集V=V1∪V2,V1∩V2=?且邊e={u,v}，u∈V1和v∈V2或u∈V2和v∈V19定理：圖中任意奇頂點(diǎn)的個(gè)數(shù)必為偶數(shù)10推論：在一次圍棋比賽中，下過(guò)奇數(shù)盤棋的人數(shù)是偶數(shù)11問(wèn)題？共有100塊糖，從2013年元旦開(kāi)始吃，每天至少吃一塊，共有多少種吃法？123.3區(qū)間圖區(qū)間圖的研究源于1959年Benzer（研究細(xì)菌結(jié)構(gòu)）的一篇文章基因沿染色體線性排列區(qū)間圖是分子生物學(xué)現(xiàn)代實(shí)踐的核心13

圖譜A和圖譜BA假設(shè)A圖譜假設(shè)有4個(gè)限制位點(diǎn)

B

假設(shè)B圖譜有4個(gè)限制位點(diǎn)14。…限制圖譜A∧B則A∧B上有7個(gè)限制位點(diǎn)15區(qū)間圖區(qū)間圖是分子生物學(xué)的現(xiàn)代實(shí)踐核心區(qū)間圖與限制圖譜相聯(lián)系限制圖譜指出特定DNA某些位點(diǎn)的位置（位點(diǎn)是特定序列）16A∧B的圖譜A圖譜有3個(gè)限制位點(diǎn)B圖譜有4個(gè)限制位點(diǎn)A∧B的圖譜是A圖譜與B圖譜區(qū)間重疊，可能有7個(gè)位點(diǎn)17區(qū)間圖區(qū)間是隨意標(biāo)號(hào)的限制酶能把DNA切成許多區(qū)間，能識(shí)別這些位點(diǎn)的單個(gè)區(qū)間，卻不能直接觀測(cè)到這些小區(qū)間的順序，而是試圖確定A區(qū)間是否與B區(qū)間重疊由重疊數(shù)據(jù)構(gòu)造圖譜形式上說(shuō)：如果兩區(qū)間有非空的交，則說(shuō)兩區(qū)間重疊18限制圖譜構(gòu)造最困難的內(nèi)容是確定重疊數(shù)據(jù)19定理下列命題等價(jià)（1）偶圖G（A,B）是由某限制圖譜構(gòu)成的圖（2）G（A,B）是沒(méi)有孤立點(diǎn)的偶區(qū)間圖（3）I（A,B）通過(guò)行和列的置換變成每行和每列的1都恰好處于這些臺(tái)階之一20區(qū)間圖區(qū)間圖可被識(shí)別并能找到他的表現(xiàn)，所用時(shí)間是定點(diǎn)數(shù)加邊數(shù)的線性時(shí)間

O(V+E)(V是定點(diǎn)數(shù)，E邊數(shù))213.4片段大小的度量DNA的長(zhǎng)度或大小是通過(guò)一個(gè)稱為凝膠電泳的過(guò)程度量的凝膠指固態(tài)基質(zhì)DNA帶負(fù)電荷分子，當(dāng)凝膠被放在電場(chǎng)下，DNA向正極移動(dòng)22片段大小的度量DNA的遷移距離是DNA大?。ㄩL(zhǎng)度）的函數(shù)遷移距離D與DNA大小或距離L的對(duì)數(shù)成線性關(guān)系，即D︽a+blog(L)(b<0)負(fù)斜率b意義：長(zhǎng)的DNA在凝膠基質(zhì)中纏結(jié)，從而移動(dòng)不遠(yuǎn)，而小的DNA穿過(guò)基質(zhì)非常容易23片段大小的度量遷移距離D不是一個(gè)點(diǎn)，而是一個(gè)污跡，科學(xué)家不能精確測(cè)量污跡?？捎媒y(tǒng)計(jì)學(xué)正態(tài)分布解釋DNA小的片段可被度量的很精確，而大的片段可能有非常大的誤差243.5多重圖譜用下列方法能能確定重疊區(qū)間Ai∩Bj首先，用酶A將DNA打碎，然后對(duì)A的每個(gè)片段Ai再用酶B將它打碎如果所有A∩B的尺寸是唯一的，則A∩B的每一個(gè)片段唯一指定給Ai25多重圖譜A∩B片段的唯一性通常有由這些片段長(zhǎng)度的唯一性給出按相反次序重復(fù)實(shí)驗(yàn)，則A∩B的每個(gè)片段唯一指定給Bj26通常不是直接從重疊Ai∩Bj的實(shí)驗(yàn)數(shù)據(jù)確定圖譜，而是做兩個(gè)單一消化和一個(gè)雙消化273.6雙消化問(wèn)題(DDP)線性DNA的雙消化在無(wú)測(cè)量誤差的最簡(jiǎn)單情況，把這個(gè)問(wèn)題叫雙消化問(wèn)題（DoubleDigestingProblem,DDP）限制酶在一些特定模式出現(xiàn)的地方將長(zhǎng)為L(zhǎng)的DNA分子切成一些片段，并將這些片段長(zhǎng)度記錄下來(lái)28DDP（雙消化問(wèn)題）是NP完全的P類：確定性圖靈機(jī)多項(xiàng)式時(shí)間可計(jì)算的問(wèn)題類（能求出精確解）NP類：確定性圖靈機(jī)多項(xiàng)式時(shí)間可驗(yàn)證的

問(wèn)題類（可能解多項(xiàng)式時(shí)間可驗(yàn)證）NPC類：?jiǎn)栴}A為NPC類，當(dāng)且僅當(dāng)A屬于NP類且所有NP類問(wèn)題均可多項(xiàng)式變換到A29雙消化問(wèn)題(DDP)單獨(dú)使用某種酶后，有一列片段長(zhǎng)度作為數(shù)據(jù)a=‖A‖={ai:1≤i≤n}來(lái)自第一個(gè)分解b=‖B‖={bi:1≤i≤m}來(lái)自第二個(gè)分解30雙消化問(wèn)題(DDP)當(dāng)兩種限制酶同時(shí)使用，DNA在兩組限制模式的所有出現(xiàn)處被切割，得到一列雙消化片段長(zhǎng)度c=‖A∧B‖={ci:1≤i≤l}來(lái)自第一個(gè)分解31雙消化問(wèn)題(DDP)用DDP(a,b,c)來(lái)表示求圖譜[A,B]的問(wèn)題，使得‖A‖=a,‖B‖=b及‖C‖=‖A∧B‖=c一般，‖A‖,‖B‖和‖C‖是重集：可能有一些片段長(zhǎng)的值出現(xiàn)不止一次32約定：集合‖A‖,‖B‖和‖C‖是有序的，即：若：i≤j,有ai≤aj對(duì)于集合‖B‖和‖C‖也一樣當(dāng)然：∑ai=∑bi=∑ci=L333.6.1雙消化問(wèn)題的多重解在許多實(shí)例中，雙消化問(wèn)題的解是不唯一的舉例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片段和這些片段次序最簡(jiǎn)單是組合學(xué)給出n!*m!=4!*6!個(gè)圖譜構(gòu)形353在A分解中重復(fù)2次，3在B分解中也重復(fù)了2次在不能區(qū)分長(zhǎng)度相同片段情況下，上例中：n=4,m=6有（4！*6！）/（2！2!）=4320個(gè)圖譜構(gòu)形36Kingman定理概率論中非常有用的工具雙消化解的個(gè)數(shù)隨長(zhǎng)度指數(shù)級(jí)增長(zhǎng)37概率算法與隨機(jī)算法的應(yīng)用區(qū)別在概率算法中，我們僅關(guān)心組合對(duì)象是否存在，若一個(gè)事件的發(fā)生概率為非零，就足夠了在隨機(jī)算法中，算法性能是非常重要的，我們不能容忍非常小的成功概率。38隨機(jī)算法在計(jì)算生物學(xué)中，可利用Lovász局部引理來(lái)證明事件發(fā)生存在性利用Markov和Chebyshev不等式來(lái)證明近似算法的有界性

39假設(shè)有n個(gè)相互獨(dú)立的事件，每個(gè)事件發(fā)生的概率至多是1/2，那么n個(gè)事件都不發(fā)生的概率至少是2-n

Lovász局部引理將這個(gè)問(wèn)題推廣到了每個(gè)事件都和另外的一小部分事件非獨(dú)立的情況。40Kingman定理(次可加遍歷)對(duì)非負(fù)整數(shù)s,t,0≤s≤t,設(shè)Xs,t是一組隨機(jī)變量，滿足以下條件（1）只要s<t<u,Xs,u≤Xs,t+Xt,u;（2）{Xs,t}的聯(lián)合分布與{Xs+1,t+1}的聯(lián)合分布一樣（3）期望gt=E[X0,t]存在，并對(duì)某個(gè)常熟K和所有t>1

滿足gt≥Kt,則有：limXs,t/t=m(m>0)(t→∞)以概率為1存在且是一階矩收斂

41定理1假設(shè)對(duì)兩種酶，這些位點(diǎn)分別以概率pa,pb∈(0,1)獨(dú)立分布。設(shè)Ys,t是第s個(gè)和第t個(gè)重合切割位點(diǎn)間解的個(gè)數(shù)，則存在一個(gè)有限常數(shù)m>0，使

limlog(Y0,t)/t=m(m>0)(t→∞)42定理2假設(shè)對(duì)兩種酶，這些位點(diǎn)分別以概率pa,pb∈(0,1)獨(dú)立分布。設(shè)Zl是從0開(kāi)始到常為l的一段的解數(shù)，則：lim(logZl/l)=mpapb(m>0)(l→∞)則Zl

≈exp(mpapbl)（l為DNA子片段長(zhǎng)度）說(shuō)明：雙消化問(wèn)題的解作為DNA片段長(zhǎng)度的函數(shù)指數(shù)的增長(zhǎng)433.7多重解分類對(duì)于長(zhǎng)的DNA有許多DDP的解，這樣的結(jié)果困難性什么也不知道不知道指數(shù)增長(zhǎng)率、確定Kingman定理中常數(shù)K也很困難具有多重解的小例子在極長(zhǎng)的DNA中也存在。443.7.1多重解的反射性只要a,b是DDP（雙消化問(wèn)題）的解，則a和b的轉(zhuǎn)置a’,b’也是DDP的解，稱：（a’,b’）是（a,b）的反射453.7.2重疊等價(jià)許多不同的圖譜可能有同樣的重疊數(shù)據(jù)，具有同一重疊數(shù)據(jù)的這些解稱為重疊等價(jià)46重疊尺寸等價(jià)圖譜{a1,a2,…an},{b1,b2,…bm}和{c1,c2,…cl}的DDP兩個(gè)解有同樣一組重疊尺寸數(shù)據(jù)，

則稱DDP兩個(gè)解重疊尺寸等價(jià)47邊的交錯(cuò)和歐拉路一個(gè)路或回路的相繼的邊的染色不同，稱為交錯(cuò)的如果一個(gè)路或回路通過(guò)圖的每條邊恰好一次，則稱該路是歐拉的483.7.3重疊尺寸等價(jià)命題：當(dāng)圖譜{a1,a2,…an}和{b1,b2,…bm}每一個(gè)都有互不相同的元素，則重疊等價(jià)與重疊尺寸等價(jià)相同片段的尺寸一般都是知道的重疊等價(jià)推出重疊尺寸等價(jià)493.7.4Kotig定理設(shè)G是邊染色的連通圖且頂點(diǎn)的度為偶數(shù)，則當(dāng)且僅當(dāng)G是平衡圖時(shí)，G存在一個(gè)交錯(cuò)的歐拉回路平衡圖：每個(gè)