【正文】 頂點覆蓋 V’的大小是它所包含的頂點個數(shù) |V’|。 DNA序列數(shù)據(jù) : 14個月增長一倍 。 Leroy Hood, ISB 生物信息的海量性 近 20 年來，分子生物學(xué)發(fā)展的一個顯著特點是生物信息的劇烈膨脹，且迅速形成了巨量的生物信息庫。 熱點 Ⅰ ： 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ù)片段則相當(dāng)于用膠水膠在一塊 ,用統(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 熱點 Ⅲ ： 序列比對 ? 用于同源查找：從不同的生物中找到相似之處 ? 人類 vs. 老鼠 vs. 酵母 (以下數(shù)據(jù)來自 NCBI 疾病數(shù)據(jù)庫 ) Best Sequence Similarity Matches to Date Between Positionally Cloned Human Genes and S. cerevisiae Proteins Human Disease MIM Human GenBank BLASTX Yeast GenBank Yeast Gene Gene Acc for Pvalue Gene Acc for Description Human cDNA Yeast cDNA Hereditary Nonpolyposis Colon Cancer 120436 MSH2 U03911 MSH2 M84170 DNA repair protein Hereditary Nonpolyposis Colon Cancer 120436 MLH1 U07418 MLH1 U0