第三講限制圖譜與多重圖譜生命是什么？生命是物質的一種運動形態(tài)

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

圖論的誕生圖論起源于1736年Euler的一篇文章，該文章解決了Konigsberg（哥尼斯堡）七橋問題。Konigsberg（哥尼斯堡）七橋問題：能否從某點出發(fā)通過每橋恰好回到原地？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定理：圖中任意奇頂點的個數(shù)必為偶數(shù)10推論：在一次圍棋比賽中，下過奇數(shù)盤棋的人數(shù)是偶數(shù)11問題？共有100塊糖，從2013年元旦開始吃，每天至少吃一塊，共有多少種吃法？123.3區(qū)間圖區(qū)間圖的研究源于1959年Benzer（研究細菌結構）的一篇文章基因沿染色體線性排列區(qū)間圖是分子生物學現(xiàn)代實踐的核心13

圖譜A和圖譜BA假設A圖譜假設有4個限制位點

B

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

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

問題類（可能解多項式時間可驗證）NPC類：問題A為NPC類，當且僅當A屬于NP類且所有NP類問題均可多項式變換到A29雙消化問題(DDP)單獨使用某種酶后，有一列片段長度作為數(shù)據(jù)a=‖A‖={ai:1≤i≤n}來自第一個分解b=‖B‖={bi:1≤i≤m}來自第二個分解30雙消化問題(DDP)當兩種限制酶同時使用，DNA在兩組限制模式的所有出現(xiàn)處被切割，得到一列雙消化片段長度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‖是重集：可能有一些片段長的值出現(xiàn)不止一次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次在不能區(qū)分長度相同片段情況下，上例中：n=4,m=6有（4！*6！）/（2！2!）=4320個圖譜構形36Kingman定理概率論中非常有用的工具雙消化解的個數(shù)隨長度指數(shù)級增長37概率算法與隨機算法的應用區(qū)別在概率算法中，我們僅關心組合對象是否存在，若一個事件的發(fā)生概率為非零，就足夠了在隨機算法中，算法性能是非常重要的，我們不能容忍非常小的成功概率。38隨機算法在計算生物學中，可利用Lovász局部引理來證明事件發(fā)生存在性利用Markov和Chebyshev不等式來證明近似算法的有界性

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

Lovász局部引理將這個問題推廣到了每個事件都和另外的一小部分事件非獨立的情況。40Kingman定理(次可加遍歷)對非負整數(shù)s,t,0≤s≤t,設Xs,t是一組隨機變量，滿足以下條件（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]存在，并對某個常熟K和所有t>1

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

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

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

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

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