【正文】 若 n比 60 大得多， ≈n60 實際中無法使用，需要對它進行改進。 移除邊上的任意一點相當于刪除這條邊。 兩條序列之間的比對 計算機科學(xué)當中已經(jīng)有比較成熟的串問題的算法 AGGCTATCACCTGACCTCCAGGCCGATGCCC TAGCTATCACGACCGCGGTCGATTTGCCCGAC AGGCTATCACCTGACCTCCAGGCCGATGCCC TAGCTATCACGACCGCGGTCGATTTGCCCGAC 分子的動態(tài)模擬 代謝途徑模擬 計算在生物問題中的角色 實驗產(chǎn)生的龐大生物數(shù)據(jù) 計算 實驗 專業(yè)領(lǐng)域知識 理論模型 或假說 證實 /新數(shù)據(jù) 合理 設(shè)計 數(shù)據(jù)挖掘 …. 計算扮演一個十分重要的角色 ….. 生物信息學(xué)中的幾個計算問題 ? 舉例： – Vertex cover – motif finding – DSSP (Distinguishing String Selection Problems) 一、 Vertex cover ? DNA sequences A,G,T,C代表四個 DNA的基本元素 105個互不相同的 DNA序列 G A T T C C A G T…………………………………… ? Give n(here,n= 105) DNA sequences, can you find 60 of them whose remove makes the remaining sequences consistent? ? 問題： 105個基因序列中 ,只去掉 60個 ,使得剩下的序列相似 . ? 模型： – 作一個圖，每個 DNA串是圖中的一個點。 熱點 Ⅰ ： DNA測序和拼接 ? 鳥槍法 (Shotgun)測序：得到 DNA片斷 隨機地切很多次 基因組 forwardreverse linked reads ? plasmids (2 – 10 Kbp) ? cosmid (40 Kbp) known dist ~500 bp ~500 bp 序列拼接：將片斷拼接為完整基因組 DNA片斷（ Reads） 基因組 全基因組 Shotgun 拼接 1. 找重疊 reads 4. 最后推導(dǎo)出一致的序列 ..ACGATTACAATAGGTT.. 2. 把重疊 reads合并成 contigs 3. 把 contigs 連接起來形成 supercontigs ? 比較片段集合中所有的片段對 ,獲得可能存在的重疊部分(Overlap) ? 建立所有片段的相互組合關(guān)系 (Layout) ,以片段為頂點 ,重疊的片段相互連接，構(gòu)成圖 Phrap算法 Phrap 算法最后一步是定義有向代權(quán)圖 ,并在圖中找 出一條最佳路徑 ,使得這條路徑經(jīng)過每個頂點恰好一次 Hamiltonian 路徑問題 Euler 算法 ? 建立所有片段的相互關(guān)系 , 即構(gòu)造 deBrujin 圖 . 以每個片段為圖中的線 ,重復(fù)片段則相當于用膠水膠在一塊 ,用統(tǒng)一的一條線來表示 疊放重復(fù)片斷 將重復(fù)片斷看作一個 拼接成長序列 ,即找出一條歐拉路線 , 使得此路徑經(jīng)過每一條線恰好一次 Eulerian路徑問題 ? 序列拼接問題可以轉(zhuǎn)換為 – Hamiltonian 路徑問題 – Eulerian 路徑問題 轉(zhuǎn)換為計算問題 熱點 Ⅱ ：生物信息數(shù)據(jù)庫 ? DNA序列： A、 C、 G、 T組成的字符串 atggcaattaaaattggtatcaatggttttggtcgtatcggccgtatcgtattccgtgca gcacaacaccgtgatgacattgaagttgtaggtattaacgacttaatcgacgttgaatac atggcttatatgttgaaatatgattcaactcacggtcgtttcgacggcactgttgaagtg aaagatggtaacttagtggttaatggtaaaactatccgtgtaactgcagaacgtgatcca gcaaacttaaactggggtgcaatcggtgttgatatcgctgttgaagcgactggtttattc ttaactgatgaaactgctcgtaaacatatcactgcaggcgcaaaaaaagttgtattaact ggcccatctaaagatgcaacccctatgttcgttcgtggtgtaaacttcaacgcatacgca ggtcaagatatcgtttctaacgcatcttgtacaacaaactgtttagctcctttagcacgt gttgttcatgaaactttcggtatcaaagatggtttaatgaccactgttcacgcaacgact gcaactcaaaaaactgtggatggtccatcagctaaagactggcgcggcggccgcggtgca tcacaaaacatcattccatcttcaacaggtgcagcgaaagcagtaggtaaagtattacct gcattaaacggtaaattaactggtatggctttccgtgttccaacgccaaacgtatctgtt gttgatttaacagttaatcttgaaaaaccagcttcttatgatgcaatcaaacaagcaatc aaagatgcagcggaaggtaaaacgttcaatggcgaattaaaaggcgtattaggttacact gaagatgctgttgtttctactgacttcaacggttgtgctttaacttctgtatttgatgca gacgctggtatcgcattaactgattctttcgttaaattggtatc . . . . . . caaaaatagggttaatatgaatctcgatctccattttgttcatcgtattcaa caacaagccaaaactcgtacaaatatgaccgcacttcgctataaagaacacggcttgtgg cgagatatctcttggaaaaactttcaagagcaactcaatcaactttctcgagcattgctt gctcacaatattgacgtacaagataaaatcgccatttttgcccataatatggaacgttgg gttgttcatgaaactttcggtatcaaagatggtttaatgaccactgttcacgcaacgact acaatcgttgacattgcgaccttacaaattcgagcaatcacagtgcctatttacgcaacc aatacagcccagcaagcagaatttatcctaaatcacgccgatgtaaaaattctcttcgtc ggcgatcaagagcaatacgatcaaacattggaaattgctcatcattgtccaaaattacaa aaaattgtagcaatgaaatccaccattcaattacaacaagatcctctttcttgcacttgg ? 蛋白質(zhì)序列： 20種氨基酸構(gòu)成的序列（ A、 R、 N、 D、 C、 Q、 E、 G、 H、 I、L、 K、 M、 F、 P、 S、 T、 W、 Y和 V） 龐大的數(shù)據(jù)信息需要數(shù)據(jù)庫保存 ? DNA數(shù)據(jù)庫 – EMBL – GenBank – DDBJ ? 蛋白質(zhì)數(shù)據(jù)庫 – SWISSPROT – PIR – PDB 熱點 Ⅲ