生物信息學(xué)中的算法問(wèn)題

1、生物信息學(xué)中的算法問(wèn)題,,主要內(nèi)容,生物信息學(xué)中的算法問(wèn)題我們的工作 (ICT & IBP & BGI),一、生物學(xué) vs 信息科學(xué),,生物信息學(xué)的研究目標(biāo),特點(diǎn)：天然的形式化堿基：A,C,T,G四種常見(jiàn)氨基酸：20種目標(biāo)：以DNA序列作為源頭揭示“基因組信息結(jié)構(gòu)的復(fù)雜性及遺傳語(yǔ)言的根本規(guī)律”；之后進(jìn)行蛋白質(zhì)結(jié)構(gòu)和功能預(yù)測(cè)。,生物信息學(xué)的兩個(gè)挑戰(zhàn),高性能計(jì)算：海量的數(shù)據(jù)每14個(gè)月翻一番算法：海量

2、的數(shù)據(jù)使得原有算法不適用新需求,生物信息學(xué)的研究流程,第一步：生物學(xué)問(wèn)題的提出生物學(xué)為主第二步：數(shù)學(xué)建模、算法設(shè)計(jì)信息科學(xué)為主第三步：結(jié)果解釋、實(shí)驗(yàn)驗(yàn)證生物學(xué),生物信息學(xué)脈絡(luò),生物信息學(xué)問(wèn)題概覽（1）,基因組時(shí)期：序列－結(jié)構(gòu)－功能DNA測(cè)序和拼接比對(duì)進(jìn)化樹(shù)蛋白質(zhì)質(zhì)譜鑒定序列注釋?zhuān)夯蝾A(yù)測(cè)、細(xì)胞定位結(jié)構(gòu)預(yù)測(cè)：RNA結(jié)構(gòu)預(yù)測(cè)、蛋白質(zhì)折疊。。。。。。,生物信息學(xué)問(wèn)題概覽（2）,后基因組時(shí)期：相互作用－網(wǎng)絡(luò)－功能生物

3、芯片（DNA芯片、蛋白質(zhì)芯片）相互作用網(wǎng)絡(luò)調(diào)控網(wǎng)絡(luò)E-Cell藥物設(shè)計(jì)。。。。。。,1. 大規(guī)模測(cè)序和拼接,生物學(xué)問(wèn)題：從DNA片段恢復(fù)原始序列,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,DNA整體,切成小段,小段和載體結(jié)合,結(jié)合后進(jìn)行測(cè)序,全自動(dòng)的測(cè)序儀器：MegaBace,需要拼接！,因?yàn)檎麄€(gè)基因組太長(zhǎng)（上M),而每

4、次只能測(cè)得一個(gè)500的小片斷(read)問(wèn)題：如何根據(jù)read恢復(fù)原始順序？類(lèi)比：10本圣經(jīng)，都從隨機(jī)點(diǎn)起始剪成500個(gè)字母左右的小紙條，問(wèn)：給你這么一堆小紙條，你能讀出圣經(jīng)來(lái)嗎？,拼接問(wèn)題的數(shù)學(xué)描述,數(shù)學(xué)問(wèn)題：公共超串輸入：設(shè)有字符串S，預(yù)先估計(jì)其長(zhǎng)度大約為n，現(xiàn)在已知一個(gè)字符串集合R={R1,R2…Rn}，其中每個(gè)Ri都是S的一個(gè)子串。問(wèn)：原始序列S是什么？算法：Hamiltion路徑類(lèi)Euler路徑類(lèi)Local S

5、earch類(lèi),2. 序列比對(duì),生物學(xué)問(wèn)題：序列的相似性－>同源性原始序列：S: acgctgT: catgt可行解：S: a c g c t g - T: - c – a t g t S: a c g c t g - T: - c a – t g t S: - a c g c t g T: c a t

6、 g - t -,序列聯(lián)配：,兩序列聯(lián)配：全局聯(lián)配(Global Alignment)局部聯(lián)配(Local Alignment)空位處罰(Gap Penalty)多序列聯(lián)配全基因組比對(duì),Open Problems:,快速的多序列比對(duì)算法快速的全基因組比對(duì)算法,3. 進(jìn)化樹(shù),生物學(xué)問(wèn)題：根據(jù)形態(tài)、DNA、行為學(xué)特征推導(dǎo)種群進(jìn)化關(guān)系樹(shù),進(jìn)化樹(shù)問(wèn)題的數(shù)學(xué)描述,輸入：N個(gè)物種的特征（DNA、形態(tài)。。。）輸出：以

7、這N個(gè)特征為葉節(jié)點(diǎn)的一顆樹(shù)距離法：聚類(lèi)譜系樹(shù)簡(jiǎn)約法：最小突變樹(shù),4. 結(jié)構(gòu)預(yù)測(cè),結(jié)構(gòu)大致決定功能 一級(jí)結(jié)構(gòu) (氨基酸序列)二級(jí)結(jié)構(gòu) (螺旋、片層、回環(huán))超二級(jí)結(jié)構(gòu)（aba…)三級(jí)結(jié)構(gòu) (由二級(jí)結(jié)構(gòu)組合成三維構(gòu)像)四級(jí)結(jié)構(gòu)：多個(gè)亞基實(shí)驗(yàn)測(cè)定方法：x-ray晶體衍射N(xiāo)MR核磁共振實(shí)驗(yàn)耗時(shí)、昂貴一個(gè)蛋白質(zhì)結(jié)構(gòu)測(cè)定需要$200K or more需數(shù)月或者更長(zhǎng)有些蛋白質(zhì)還無(wú)法測(cè)定,蛋白質(zhì)結(jié)構(gòu)（2）,理論上可計(jì)算的。

8、能量最低原則變?cè)褐鞲傻膒si/phi angles側(cè)鏈的旋轉(zhuǎn)優(yōu)化問(wèn)題，但是搜索空間極其巨大局部極值點(diǎn),三種預(yù)測(cè)方法,ab initio 方法根據(jù)第一原理計(jì)算量極大，實(shí)際上不可行同源建模方法：基本假設(shè)：序列同源－>結(jié)構(gòu)相似有效，但是必須具有同源的序列Threading方法：基本假設(shè): 自然界中蛋白質(zhì)主鏈模式是有限的~90% 新蛋白質(zhì)和PDB某個(gè)已知蛋白質(zhì)結(jié)構(gòu)相似推論: 多個(gè)蛋白質(zhì)會(huì)具有相同的主鏈模

9、式預(yù)測(cè)問(wèn)題－>識(shí)別問(wèn)題能夠處理序列上不相似，但是結(jié)構(gòu)相似的情況,Threading方法,思路：將序列盡可能好地放入結(jié)構(gòu)模板中；設(shè)計(jì)評(píng)價(jià)函數(shù)，對(duì)匹配情況進(jìn)行打分； 關(guān)鍵:已知的結(jié)構(gòu)模板庫(kù)衡量匹配情況的打分函數(shù)尋求最優(yōu)的算法；,序列： MTYKLILNGKTKGETTTEAVDAATAEKVFQYANDNGVDGEWTYTE模板庫(kù)：,數(shù)學(xué)描述：,MTYKLILNGKTKGETTTEAVDAATA

10、EKVFQYANDNGVDGEWTYTE,殘基和結(jié)構(gòu)的匹配： environment: E_s,兩個(gè)殘基相鄰的衡量: E_p,空位罰分: E_g,min （ E_p + E_s + E_g ）,,,,Protein Threading by PROSPECT,prediction examples from CASP3 contest,actual,predicted,actual,actual,actual,predicted,pre

11、dicted,predicted,t49,t68,t57,t70,5. 蛋白質(zhì)DOMAIN識(shí)別,生物學(xué)觀(guān)點(diǎn)：一個(gè)蛋白質(zhì)結(jié)構(gòu)可以包含多個(gè)DOMAIN: DOMAIN是蛋白質(zhì)折疊、功能和演化的基本單位不同的蛋白質(zhì)具有相同的DOMAIN識(shí)別DOMAIN有助于蛋白質(zhì)折疊數(shù)學(xué)觀(guān)點(diǎn)：最小割,actin,DOMAIN識(shí)別,生物學(xué)的不嚴(yán)格表述：DOMAIN連接緊致，接近球狀DOMAIN之間作用相對(duì)較弱可操作的定義：DOMAIN內(nèi)部殘

12、基相互作用較強(qiáng)DOMAIN之間殘基相互作用較弱現(xiàn)有識(shí)別方法不實(shí)用SCOP數(shù)據(jù)庫(kù)靠手工來(lái)維護(hù),DOMAIN識(shí)別與最小割,bottleneck,interface,,,Network Flow Problem,source,sink,capacity,edge,node,,,,,,Ford-Fulkerson Theorem: the minimum cut of a network is equal to its maximum f

13、low,最小割,節(jié)點(diǎn)：一個(gè)節(jié)點(diǎn)表示一個(gè)殘基邊：殘基－殘基之間的相互作用容量：根據(jù)生物學(xué)知識(shí)，比如相互作用的種類(lèi)和強(qiáng)度確定邊的容量,,經(jīng)典解法及其結(jié)果：,maximum flow:Edmonds-Karp algorithm (1972)enumeration of all minimum cuts:Picard-Queyranne algorithm (1980)complexity: O (n3)(n is

14、the number of residues in structure),6. 序列注釋,輸入：DNA序列輸出：各個(gè)功能位點(diǎn)：基因、啟動(dòng)子、ncRNA。。?？梢岳玫闹R(shí)：生物學(xué)規(guī)律正例和反例當(dāng)前最好的方法：HMM形式語(yǔ)言,7. 蛋白質(zhì)質(zhì)譜鑒定,生物學(xué)問(wèn)題：原有的Edman方法昂貴、耗時(shí)根據(jù)質(zhì)譜來(lái)測(cè)定蛋白質(zhì)氨基酸序列什么是質(zhì)譜？,樣品制備,,,一級(jí)質(zhì)譜：片段分離,MassSpectrometry,,,,,,,

15、,,,,,,,,,,,,,,,,,,,,,,,,,短肽段離子化，經(jīng)過(guò)電場(chǎng)，依據(jù)荷質(zhì)比的不同分離,二級(jí)質(zhì)譜：片段再打斷,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,

16、,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,

17、,,,,,,,,,,,,,,,,,,,,,,,,肽段可能形成的離子,MS/MS Spectrum,y-ions,b-ions,LGEYGFQNALLVR,DeNOVO: 從質(zhì)譜猜原始序列,m/z,147,260,389,504,633,762,875,1022,1080,1166,1166,1020,907,778,663,534,405,292,145,88,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,

18、,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,

19、,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,% Relative Abundance,100,0,250,500,750,1000,我們的工作,,組織結(jié)構(gòu)：,生物組：4個(gè)碩士提生物學(xué)問(wèn)題算法組：5人部分獨(dú)立的算

20、法研究，做技術(shù)儲(chǔ)備生物信息算法設(shè)計(jì)與分析軟件組：8人高性能算法、機(jī)器軟件開(kāi)發(fā),合作：,生物物理所國(guó)家藥物篩選中心華大基因中心李明老師,基于Local Search的序列拼接算法,,現(xiàn)有算法：,Hamilton路徑類(lèi)算法Eulerian路徑類(lèi)算法,Hamilton路徑類(lèi)算法,包括：Phrap, CAP3, TIGR, GigAssembler生成圖：結(jié)點(diǎn)：每個(gè)片段自成一個(gè)結(jié)點(diǎn)邊：如果兩個(gè)結(jié)點(diǎn)間有Overla

21、p沿DNA序列從頭走到尾，將經(jīng)過(guò)每個(gè)結(jié)點(diǎn)一次且僅一次Hamilton Path,Hamilton Path,拼接三步曲,STEP 1。OverlapSTEP 2。LayoutSTEP 3。Consensus/Mosaic,STEP1。Overlap,這一步對(duì)所有的Read進(jìn)行兩兩比對(duì)，通常采用快速Smith-Waterman算法，以確定兩個(gè)Read之間是否有Overlap。考慮到各個(gè)堿基的出錯(cuò)概率，常常對(duì)Overlap進(jìn)行

22、打分，衡量Overlap的可能性高低，一般采用LLR（Log Likehood Ratio）方法打分。,STEP 2。Layout,根據(jù)Read之間的重疊信息形成Contig，即將各個(gè)Read merge起來(lái)，形成一個(gè)逐次鏈接的鏈接體。這一步實(shí)際上是在求一條Hamilton Path，通常采用的是貪心法。,STEP 3。Consensus,對(duì)于每個(gè)Contig，按照投票或者其他的原則計(jì)算出一個(gè)Sequence。,評(píng)價(jià),判定是否存在Ha

23、milton Path是NP完全問(wèn)題現(xiàn)在采用的是貪心法不存在有效算法出錯(cuò),出錯(cuò)例示,EULER Path類(lèi)算法,轉(zhuǎn)換成圖論問(wèn)題 de Bruijn圖結(jié)點(diǎn)：l-mers邊：兩個(gè)l-mers重疊（l-1)個(gè)單元片段：圖上一條路徑沿著DNA從頭走到尾，將經(jīng)過(guò)每條邊一次且僅一次。Euler Path附加條件：經(jīng)過(guò)每條路徑的特殊Euler Path.,STEP 1。Consensus,目的：排除Read中的錯(cuò)誤，獲得Error－

24、Free 的Read思路：使用Gk的近似－將所有的Read切割成小片k-mersk-mers: 是Solid如果出現(xiàn)在至少M(fèi)個(gè)Read中；否則稱(chēng)為Weak。,STEP 2。de Bruijn圖的構(gòu)造,結(jié)點(diǎn)：每個(gè)k-mers是結(jié)點(diǎn)邊： de Bruijn邊的構(gòu)造方法，v-u當(dāng)前僅當(dāng)v的尾巴和w的頭相同。每個(gè)Read表示成一條Path，每個(gè)Repeat表示成一個(gè)多入口、多出口的單一鏈，但是不知道出入口之間的對(duì)應(yīng)關(guān)系。如果沒(méi)有Rea

25、d來(lái)覆蓋這條單一鏈，則稱(chēng)為T(mén)angle。,STEP 3. Eulerian Super Path,在de Bruijn圖中尋找一條Eulerian Path，能夠覆蓋所有的Path。變換方法，等價(jià)變換，使得成為尋找一條Eulerian Path的問(wèn)題。,新方法：機(jī)器學(xué)習(xí)的方法,原始序列：概念C正例: 原始序列的所有子串反例：非子串目標(biāo)：通過(guò)正例和反例，學(xué)習(xí)出原始序列的近似C`。加強(qiáng)：不僅僅和已知的訓(xùn)練集一致，而且對(duì)于未知的樣

26、本，犯錯(cuò)誤的概率很小,PAC模型,原始概念C, 正例集POS，反例集NEG，如果算法A對(duì)于給定的ε,δ，在多項(xiàng)式時(shí)間內(nèi)結(jié)束，并輸出概念C’，滿(mǎn)足：C’和C的誤差小于ε則稱(chēng)為PAC算法,拼接與最短公共超串,Blumer定理：對(duì)于概念C,如果使用m/2個(gè)正例,m/2個(gè)反例，并且學(xué)習(xí)得到概念C’的size小于某個(gè)值時(shí)，那么A是一個(gè)PAC算法。利用最短公共超串，滿(mǎn)足Blumer定理的算法。,原始算法：,Group－Merge算法使用

27、O(n logn logn )個(gè)片段以（1- δ)的概率保證：學(xué)習(xí)得到串C’和原始串的誤差小于ε,評(píng)價(jià),優(yōu)點(diǎn)：堅(jiān)實(shí)的理論基礎(chǔ)對(duì)結(jié)果的加強(qiáng)：不僅僅是包含所有子串而是犯錯(cuò)誤的概率最小缺點(diǎn)：慢效果不好,Local Search算法：,可行解：片段的排列相鄰關(guān)系：兩個(gè)片段交換位置目標(biāo)函數(shù)：超串長(zhǎng)度,算法框架：,(0)計(jì)算并保存每?jī)蓚€(gè)子串之間的overlap數(shù) Repeat: (1)隨機(jī)選擇排列P,得到相應(yīng)的超串

28、的長(zhǎng)度t, (2)Repeat: 在P的鄰域內(nèi)進(jìn)行搜索, 如果鄰域內(nèi)存在P’對(duì)應(yīng)的超串長(zhǎng)度小于t, 則P<-P’; Until: P是鄰域內(nèi)的最小點(diǎn)。 Until 終止條件滿(mǎn)足,Heuristics:,1. 將排列環(huán)起來(lái)，搜索最短的環(huán)狀超串2. 整個(gè)group的移動(dòng)3. 尋找排列中使得overlap最小的地方，將環(huán)截?cái)啵纬啥鄠€(gè)線(xiàn)性的子超串contigs,結(jié)果：,找出的串可以近似看作最

29、短超串，算法可獨(dú)立用于求最短公共超串問(wèn)題；重復(fù)的片段在contigs的兩側(cè)；通常按這種方法找出的contig是原始串的子串；拼接水稻基因組聯(lián)盟1,10,11號(hào)染色體，效果得到了很高的評(píng)價(jià)用于華大基因中心水稻完全圖項(xiàng)目,DeNOVO算法,,質(zhì)譜的簡(jiǎn)化模型：,考慮26個(gè)英文字母，每個(gè)字母有權(quán)重W(c)對(duì)字符串S，已知質(zhì)譜＝問(wèn)：字符串＝？,難點(diǎn)：,1。一次打斷形成兩個(gè)離子，混雜在一起2。峰的類(lèi)型不知道，是b離子,y離子還

30、是混合體？3。離子的修飾：脫氨、脫水、同位素等,組合優(yōu)化問(wèn)題：,已知譜L，求序列S=A0A1A2…An ,滿(mǎn)足：同時(shí) max f( spectrum(S), L )根據(jù)生物學(xué)知識(shí)確定合適的函數(shù)f,結(jié)果1：,答案:LVNELTEFAK結(jié)果：LVNELTEFAKLVNELTHLPKLVNELTYSPK,結(jié)果2：,答案:HPEYAVSVLLR結(jié)果：HPEYAVSVLLRHPEYAVWLLRHPEYAVPVFPK

31、,結(jié)果3：,答案:HLVDEPQNLLK結(jié)果：HLVDEAGPNLLKHLVDEQPNLLKHLVDEPQNLLK,蛋白質(zhì)相互作用網(wǎng)絡(luò)分析,,復(fù)雜的蛋白質(zhì)相互作用網(wǎng)絡(luò),酵母: 2617蛋白, 11855連接,任務(wù)1：根據(jù)拓?fù)潢P(guān)系聚類(lèi),目標(biāo)：將蛋白質(zhì)分類(lèi)，使得類(lèi)內(nèi)蛋白質(zhì)連接緊密類(lèi)間蛋白質(zhì)連接稀疏思路：第一步：先轉(zhuǎn)化到歐式空間第二步：使用Ward法聚類(lèi),轉(zhuǎn)換方法：,尋求方向Y，滿(mǎn)足：每個(gè)結(jié)點(diǎn)都盡量得靠近其鄰居即：m

32、in定理：Y是對(duì)稱(chēng)陣AT (L-A)A的最小特征值對(duì)應(yīng)的特征向量其中L是Laplacian矩陣,聚類(lèi)結(jié)果分析：,1。類(lèi)內(nèi)連接緊密，類(lèi)間稀疏2。同一類(lèi)蛋白質(zhì)功能類(lèi)似,,,聚類(lèi)譜系圖,,任務(wù)2：蛋白質(zhì)相互作用網(wǎng)絡(luò)的譜分析,,譜分析,1。正特征值相應(yīng)的特征向量，絕對(duì)值較大分量相應(yīng)蛋白質(zhì)近似成團(tuán)；2。正特征值相應(yīng)的特征向量，絕對(duì)值較大分量相應(yīng)蛋白質(zhì)近似成二部圖；,,,團(tuán)和二部圖,團(tuán)：,分析：同一團(tuán)的蛋白質(zhì)生物學(xué)功能相似應(yīng)