【正文】 AAGGGCGTCAATAGCGCTGTGGACGAGACAGAGGGAATGGGGCAAGGAGCGAGGCTGGGGCTCTCACCGCGACTTGAATGTGGATGAGAGTGGGACGGTGACGGCGGGCGCGAAGGCGAGCGCATCGCTTCTCGGCCTTTTGGCTAAGATCAAGTGTAGTATCTGTTCTTATCAGTTTAATATCTGATACGTCCTCTATCCGAGGACAATATATTAAATGGATTGATCAATCCGCTTCAGCCTCCCGAGTAGCTGGGACTACAGACGGTGCCATCACGCCCAGCTCATTGTTGATTCCCGCCCCCTTGGTAGAGACGGGATTCCGCTATATTGCCTGGGCTGGTGTCGAACTCATAGAACAAAGGATCCTCCCTCCTGGGCCTGGGCGTGGGCTCGCAAAACGCTGGGATTCCCGGATTACAGGCGGGCGCACCACACCAGGAGCAAACACTTCCGGTTTTAAAAATTCAGTTTGTGATTGGCTGTCATTCAGTATTATGCTAATTAAGCATGCCCGGTTTTAAACCTCTTAAAACAACTTTTAAAATTACCTTTCCACCTAAAACGTTAAAATTTGTCAAGTGATAATATTCGACAAGCTGTTATTGCCAAACTATTTTCCTATTTGTTTCCTAATGGCATCGGAACTAGCGAAAGTTTCTCGCCATCAGTTAAAAGTTTGCGGCAGATGTAGACCTAGCAGAGGTGTGCGAGGAGGCCGTTAAGACTATACTTTCAGGGATCATTTCTATAGTGTGTTACTAGAGAAGTTTCTCTGAACGTGTAGAGCACCGAAAACCACGAGGAAGAGAGGTAGCGTTTTCATCGGGTTACCTAAGTGCAGTGTCCCCCCTGGCGCGCAATTGGGAACCCCACACGCGGTGTAGAAATATATTTTAAGGGCGCG 生物信息學 在生物信息的急劇膨脹的壓力下誕生。到 1999年 12月其數(shù)目已達 30億，它們來自 47000種生物。 得到以下數(shù)據(jù)：遺傳圖、物理圖、全序列圖。預計 2022年達到 300億。 如果兩個序列具有足夠的相似性，則認為兩者具有同源性。 －表示相似的子串 k＝ 20， 每個串長度為 2022 序列模體 (Motif) TGTGAAAGACTGTTTTTTTGATCGTTTTGACAAAAATGGAAGTCCACA AAGTCCACATTGATTATTTGCACGGCGTCACACTTTGCTATCCCATAG TGATGTACTGCATGTATGCAAAGGACGTCAGATTACCGTGCAGTACAG TAAACGATTCCACTAATTTATTCCATGTCACTCTTTTCGCATCTTTGT ACATTACCGCCAATTCTGTAACAGAGATCACACAAAGCGACGGTGGGG ACTTTTTTTTCATATGCCTGACGGAGTTGACACTTGTAAGTTTTCAAC PevznerSze, ISMB’2022 … … … … … … … … … … … … ? （ 15， 6）模型的問題：查找一個長度為15的子串，使得它在所有的 20個串中都存在，（允許存在 6個誤差）。 如：圖靈停機問題 P類與 NP類問題 P類問題：已找到在 O(nc)時間求解的確定性算法的問題， c為常數(shù)； NP類問題：若告訴我答案，便可在 O(nc)時間內(nèi)驗證答案是否正確的問題。 是不是什么問題都是并行計算機可解的？ 并行計算 ?阿姆達爾定律： Acc_Speed =1/(f+(1f)/p) 其中， f為求解某個問題的計算存在的必須串行執(zhí)行的操作占整個計算的百分比； p為處理器的數(shù)目；Acc_Speed為并行計算機系統(tǒng)最大的加速能力。 – 這個圖上的信息量可以用計算機來計算，大約為 10萬的平方。同時，由這些原始數(shù)據(jù)分析加工而來的蛋白質(zhì)結構等數(shù)據(jù)信息也被世界各地的分子生物學、生物信息學等學科領域?qū)＜逸斎攵墧?shù)據(jù)庫中。 ?近年來 GenBank中的 DNA堿基數(shù)目呈指數(shù)增加，大約每14個月增加一倍。 可定位與疾病有關的基因 ?新藥設計和疫苗制備。 ?各種生物的 EST序列已達 600多萬條，其中人類的 EST序列已超過 300 萬條，估計覆蓋人類基因 90％以上； ?UniGene的數(shù)目約達 7萬個；自 1999年初單核苷酸多態(tài)性 ( SNPs,Single Nucleotide Polymorphisms )數(shù)據(jù)庫出現(xiàn)以來，到 2022年 3月 20日 SNP的總數(shù)是 26569，現(xiàn)在已超過 350萬 計算機運算速度 : 18個月增長一倍 。 生物信息學熱點問題（ 2） ? 后基因組時期：相互作用－網(wǎng)絡－功能 – 生物芯片（ DNA芯片、蛋白質(zhì)芯片） – 相互作用網(wǎng)絡 – 調(diào)控網(wǎng)絡 – 藥物設計 – 。 – 在圖中找到 60個點后就沒有邊了，系統(tǒng)可用 – 如果超過 60個點還有邊，系統(tǒng)不可用 ? 問題等價于： Give a graph ,can you find 60 vertices whose remove makes the graph has no edge? ? Vertex cover(點覆蓋 ):Give a graph, can you find k vertices such that each edge has at least one end in these k vertices? ? 另一種說法： ? Give a graph G of n vertices , decide if there are k vertices whose remove makes the graph edgeless. ? Try any subset of 60 vertices and check if it make a vertex cover(點覆蓋 ) ? 圖中每 60個點拿出來試一試： 若 n比 60 大得多， ≈n60 實際中無法使用，需要對它進行改進。 設 f = 1%, p =∞，則 Acc_Speed =100 結論：一個問題的求解若有 1%的串行度，則 無論有多少臺計算機并行計算 ，其計算速度至多是單臺計算機計算同一個問題的 100倍！ 易難 /難解 /不可解問題 從時間復雜性分析來說，許多問題的算法時間復雜性是 O(nc)的，其中 n是問題的規(guī)模， c是常量。 ?難解的問題！ 比如： SAT, VC, CLIQUE, IS, TSP, ……… ?不可解的問題！ 即：任何計算機不論耗費多少時間也不能解的問題。 ? 子串相似性的定義：在串中間插、刪、改的次數(shù)不超過 6次，使得兩個子串相同。 熱點 Ⅰ ： DNA測序和拼接 ? 鳥槍法 (Shotgun)測序：得到 DNA片斷 隨機地切很多次 基因組 forwardreverse linked reads ? plasmids (2 – 10 Kbp) ? cosmid (40 Kbp) known dist ~500 bp ~500 bp 序列拼接：將片斷拼接為完整基因組 DNA