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

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

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

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

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

5、earch類,2. 序列比對,生物學(xué)問題：序列的相似性－>同源性原始序列：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)配全基因組比對,Open Problems:,快速的多序列比對算法快速的全基因組比對算法,3. 進化樹,生物學(xué)問題：根據(jù)形態(tài)、DNA、行為學(xué)特征推導(dǎo)種群進化關(guān)系樹,進化樹問題的數(shù)學(xué)描述,輸入：N個物種的特征（DNA、形態(tài)。。。）輸出：以

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

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

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

10、EKVFQYANDNGVDGEWTYTE,殘基和結(jié)構(gòu)的匹配： environment: E_s,兩個殘基相鄰的衡量: 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識別,生物學(xué)觀點：一個蛋白質(zhì)結(jié)構(gòu)可以包含多個DOMAIN: DOMAIN是蛋白質(zhì)折疊、功能和演化的基本單位不同的蛋白質(zhì)具有相同的DOMAIN識別DOMAIN有助于蛋白質(zhì)折疊數(shù)學(xué)觀點：最小割,actin,DOMAIN識別,生物學(xué)的不嚴(yán)格表述：DOMAIN連接緊致，接近球狀DOMAIN之間作用相對較弱可操作的定義：DOMAIN內(nèi)部殘

12、基相互作用較強DOMAIN之間殘基相互作用較弱現(xiàn)有識別方法不實用SCOP數(shù)據(jù)庫靠手工來維護,DOMAIN識別與最小割,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é)點：一個節(jié)點表示一個殘基邊：殘基－殘基之間的相互作用容量：根據(jù)生物學(xué)知識，比如相互作用的種類和強度確定邊的容量,,經(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序列輸出：各個功能位點：基因、啟動子、ncRNA。。?？梢岳玫闹R：生物學(xué)規(guī)律正例和反例當(dāng)前最好的方法：HMM形式語言,7. 蛋白質(zhì)質(zhì)譜鑒定,生物學(xué)問題：原有的Edman方法昂貴、耗時根據(jù)質(zhì)譜來測定蛋白質(zhì)氨基酸序列什么是質(zhì)譜？,樣品制備,,,一級質(zhì)譜：片段分離,MassSpectrometry,,,,,,,

15、,,,,,,,,,,,,,,,,,,,,,,,,,短肽段離子化，經(jīng)過電場，依據(jù)荷質(zhì)比的不同分離,二級質(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個碩士提生物學(xué)問題算法組：5人部分獨立的算

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

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

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

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

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

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

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

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

28、的長度t, (2)Repeat: 在P的鄰域內(nèi)進行搜索, 如果鄰域內(nèi)存在P’對應(yīng)的超串長度小于t, 則P<-P’; Until: P是鄰域內(nèi)的最小點。 Until 終止條件滿足,Heuristics:,1. 將排列環(huán)起來，搜索最短的環(huán)狀超串2. 整個group的移動3. 尋找排列中使得overlap最小的地方，將環(huán)截斷，形成多個線性的子超串contigs,結(jié)果：,找出的串可以近似看作最

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

30、是混合體？3。離子的修飾：脫氨、脫水、同位素等,組合優(yōu)化問題：,已知譜L，求序列S=A0A1A2…An ,滿足：同時 max f( spectrum(S), L )根據(jù)生物學(xué)知識確定合適的函數(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)系聚類,目標(biāo)：將蛋白質(zhì)分類，使得類內(nèi)蛋白質(zhì)連接緊密類間蛋白質(zhì)連接稀疏思路：第一步：先轉(zhuǎn)化到歐式空間第二步：使用Ward法聚類,轉(zhuǎn)換方法：,尋求方向Y，滿足：每個結(jié)點都盡量得靠近其鄰居即：m

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