【正文】 1999年 12月其數(shù)目已達 30億，它們來自 47000種生物。 Leroy Hood, ISB 生物信息的海量性 近 20 年來，分子生物學(xué)發(fā)展的一個顯著特點是生物信息的劇烈膨脹，且迅速形成了巨量的生物信息庫。 可定位與疾病有關(guān)的基因 ?新藥設(shè)計和疫苗制備。 計算機的計算能力 以生物信息學(xué)為例 李紹華 信息學(xué)院計算機科學(xué)與技術(shù)系 20世紀(jì)三個重大的科技工程： （原子彈研制） （ HGP）：美英法德日中六國 Human Gene Program的目的： 完成人基因組 24條染色體上 5萬左右基因的作圖和 30億堿基的 DNA全序列的測定。 得到以下數(shù)據(jù)：遺傳圖、物理圖、全序列圖。 基因中包含了人類的遺傳密碼；基因測序的完成，意味著密碼已 “ 偷到 ”，可這個密碼里寫的是什么呢？ ? 生物信息學(xué) ? 研究熱點 ? 計算問題 ? 研究思路 ccgtacgtacgtagagtgctagtctagtcgtagcgccgtagtcgatcgtgtgggtagtagctgatatgatgcgaggtaggggataggatagcaacagatgagcggatgctgagtgcagtggcatgcgatgtcgatgatagcggtaggtagacttcgcgcataaagctgcgcgagatgattgcaaagragttagatgagctgatgctagaggtcagtgactgatgatcgatgcatgcatggatgatgcagctgatcgatgtagatgcaataagtcgatgatcgatgatgatgctagatgatagctagatgtgatcgatggtaggtaggatggtaggtaaattgatagatgctagatcgtaggtagtagctagatgcagggataaacacacggaggcgagtgatcggtaccgggctgaggtgttagctaatgatgagtacgtatgaggcaggatgagtgacccgatgaggctagatgcgatggatggatcgatgatcgatgcatggtgatgcgatgctagatgatgtgtgtcagtaagtaagcgatgcggctgctgagagcgtaggcccgagaggagagatgtaggaggaaggtttgatggtagttgtagatgattgtgtagttgtagctgatagtgatgatcgtag ………………………………… 基因序列中包含著有機體的大量信息 gcgtacgtacgtagagtgctagtctagtcgtagcgccgtagtcgatcgtgtgggtagtagctgatatgatgcgaggtaggggataggatagcaacagatgagcggatgctgagtgcagtggcatgcgatgtcgatgatagcggtaggtagacttcgcgcataaagctgcgcgagatgattgcaaagragttagatgagctgatgctagaggtcagtgactgatgatcgatgcatgcatggatgatgcagctgatcgatgtagatgcaataagtcgatgatcgatgatgatgctagatgatagctagatgtgatcgatggtaggtaggatggtaggtaaattgatagatgctagatcgtaggtagtagctagatgcagggataaacacacggaggcgagtgatcggtaccgggctgaggtgttagctaatgatgagtacgtatgaggcaggatgagtgacccgatgaggctagatgcgatggatggatcgatgatcgatgcatggtgatgcgatgctagatgatgtgtgtcagtaagtaagcgatgcggctgctgagagcgtaggcccgagaggagagatgtaggaggaaggtttgatggtagttgtagatgattgtgtagttgtagctgatagtgatgatcgtag ……. 通過對生物數(shù)據(jù)的分析可以獲得基因序列中所包含的有機體的大量重要信息 分子生物學(xué)是一門信息科學(xué) 。 ?近年來 GenBank中的 DNA堿基數(shù)目呈指數(shù)增加，大約每14個月增加一倍。 2022年 4月 DNA堿基數(shù)目是 60億。預(yù)計 2022年達到 300億。 DNA序列數(shù)據(jù) : 14個月增長一倍 。同時，由這些原始數(shù)據(jù)分析加工而來的蛋白質(zhì)結(jié)構(gòu)等數(shù)據(jù)信息也被世界各地的分子生物學(xué)、生物信息學(xué)等學(xué)科領(lǐng)域?qū)＜逸斎攵墧?shù)據(jù)庫中。 一般意義上，生物信息學(xué)是研究生物信息的采集、處理、存儲、傳播、分析和解釋等各方面的一門學(xué)科，它通過綜合利用 生物學(xué) 、 計算機科學(xué) 和 信息技術(shù) 揭示大量而復(fù)雜的生物數(shù)據(jù)所賦有的生物學(xué)奧秘。 如果兩個序列具有足夠的相似性，則認(rèn)為兩者具有同源性。 – 兩個串比較，不相同的話加一條邊進行連接，每條邊對應(yīng)兩個不同的 DNA。 – 這個圖上的信息量可以用計算機來計算，大約為 10萬的平方。 (not solvable practically)NPhard 60nC(2) motif finding 醫(yī)學(xué)上的問題：已知幾個串中有癌癥細(xì)胞，要求從中找出這幾個串它們的共性，也即是說，尋找一個子串，在每個串（或是大部分串）中都出現(xiàn)。 －表示相似的子串 k＝ 20， 每個串長度為 2022 序列模體 (Motif) TGTGAAAGACTGTTTTTTTGATCGTTTTGACAAAAATGGAAGTCCACA AAGTCCACATTGATTATTTGCACGGCGTCACACTTTGCTATCCCATAG TGATGTACTGCATGTATGCAAAGGACGTCAGATTACCGTGCAGTACAG TAAACGATTCCACTAATTTATTCCATGTCACTCTTTTCGCATCTTTGT ACATTACCGCCAATTCTGTAACAGAGATCACACAAAGCGACGGTGGGG ACTTTTTTTTCATATGCCTGACGGAGTTGACACTTGTAAGTTTTCAAC PevznerSze, ISMB’2022 … … … … … … … … … … … … ? （ 15， 6）模型的問題：查找一個長度為15的子串，使得它在所有的 20個串中都存在，（允許存在 6個誤差）。 頂點覆蓋 V’的大小是它所包含的頂點個數(shù) |V’|。 是不是什么問題都是并行計算機可解的？ 并行計算 ?阿姆達爾定律： Acc_Speed =1/(f+(1f)/p) 其中， f為求解某個問題的計算存在的必須串行執(zhí)行的操作占整個計算的百分比； p為處理器的數(shù)目；Acc_Speed為并行計算機系統(tǒng)最大的加速能力。?易解的問題！ 有些問題至今只設(shè)計出算法時間復(fù)雜性為 O(2n)的算法，其中 n是問題的規(guī)模。 如：圖靈停機問題 P類與 NP類問題 P類問題：已找到在 O(nc)時間求解的確定性算法的問題， c為常數(shù)； NP類問題：若告訴我答案，便可在 O(nc)時間內(nèi)驗證答案是否正確的問