第三講 限制圖譜與多重圖譜_第1頁
第三講 限制圖譜與多重圖譜_第2頁
第三講 限制圖譜與多重圖譜_第3頁
第三講 限制圖譜與多重圖譜_第4頁
第三講 限制圖譜與多重圖譜_第5頁
已閱讀5頁,還剩47頁未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡介

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

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

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

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

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

B

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

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

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

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

Lovász局部引理將這個問題推廣到了每個事件都和另外的一小部分事件非獨(dú)立的情況。40Kingman定理(次可加遍歷)對非負(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]存在,并對某個常熟K和所有t>1

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

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

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

≈exp(mpapbl)(l為DNA子片段長度)說明:雙消化問題的解作為DNA片段長度的函數(shù)指數(shù)的增長433.7多重解分類對于長的DNA有許多DDP的解,這樣的結(jié)果困難性什么也不知道不知道指數(shù)增長率、確定Kingman定理中常數(shù)K也很困難具有多重解的小例子在極長的DNA中也存在。443.7.1多重解的反射性只要a,b是DDP(雙消化問題)的解,則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兩個解有同樣一組重疊尺寸數(shù)據(jù),

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

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

最新文檔

評論

0/150

提交評論