【正文】 AACAGAGATCACACAAAGCGACGGTGGGG ACTTTTTTTTCATATGCCTGACGGAGTTGACACTTGTAAGTTTTCAAC PevznerSze, ISMB’2022 … … … … … … … … … … … … ? （ 15， 6）模型的問題：查找一個長度為15的子串，使得它在所有的 20個串中都存在，（允許存在 6個誤差）。 ? Give k DNA sequences,find a pattern of length 15 that is similar to a subsequence in each sequence. ? Give a kpartile graph,find a set of vertices,one from each row,such that all these k vertices are connected.（ 最大團） ? 計算量為 nk=202220NPhard! ? 改進： n5Xn5=n10 2n10 =4n5 n5Xn5=n10 5行 n5 5行 5行 n5 5行 是不是什么問題都是單計算機可解的？ 例一：求圖 G的最小頂點覆蓋問題： 問題描述：無向圖 G=(V,E)的頂點覆蓋是它的頂點集 V的一個子集 V’ ? V， 使得若 (u,v)是 G的一條邊，則 v∈ V’或 u∈ V’。 頂點覆蓋 V’的大小是它所包含的頂點個數(shù) |V’|。 算法： //給定圖 G =V,E,其中 |V| =n， |E| =m 第一步：枚舉出 V中所有的子集： 子集總數(shù) = (n1) + (n2) +(n3) +…+ (nn) =2n 第二步：判斷每個子集是否是圖 G的頂點覆蓋：for i =1 to m do…… 算法時間復雜性： O(2n*m) ?可計算否？ 例 : ? 假設 n=56, 在一臺運行速度為 億次級每秒的計算機里用枚舉法求解 VC問題，須花時多少？ ? 計算：我們假設該機器每秒鐘可判斷一億種的方案是否正確！則有： ? 2^56種方案 /1億種每秒 /60/60/24/365 =(年 )！ 結論：對于 O(2n)的算法，當 n足夠大時，全世界現(xiàn)有的計算機都無法在可接受的時間內求解。 是不是什么問題都是并行計算機可解的？ 并行計算 ?阿姆達爾定律： Acc_Speed =1/(f+(1f)/p) 其中， f為求解某個問題的計算存在的必須串行執(zhí)行的操作占整個計算的百分比； p為處理器的數(shù)目；Acc_Speed為并行計算機系統(tǒng)最大的加速能力。 設 f = 1%, p =∞，則 Acc_Speed =100 結論：一個問題的求解若有 1%的串行度，則 無論有多少臺計算機并行計算 ，其計算速度至多是單臺計算機計算同一個問題的 100倍！ 易難 /難解 /不可解問題 從時間復雜性分析來說，許多問題的算法時間復雜性是 O(nc)的，其中 n是問題的規(guī)模， c是常量。?易解的問題！ 有些問題至今只設計出算法時間復雜性為 O(2n)的算法，其中 n是問題的規(guī)模。 ?難解的問題！ 比如： SAT, VC, CLIQUE, IS, TSP, ……… ?不可解的問題！ 即：任何計算機不論耗費多少時間也不能解的問題。 如：圖靈停機問題 P類與 NP類問題 P類問題：已找到在 O(nc)時間求解的確定性算法的問題， c為常數(shù)； NP類問題：若告訴我答案，便可在 O(nc)時間內驗證答案是否正確的問題。 P=？ NP 1． P類問題 is in NP類問題： P ? NP 即 : P類問題一定也是 NP類問題； 2. NP類問題 is in P類問題？ NP ? P ?不知道！ 計算機理論假設： NP類問題 is not in P類問題！ 即 P≠NP 關鍵科學問題： 大量重要的生物組合計算問題是 NP難解問題 ? 生物數(shù)據(jù)的海量性（人類基因組包含超過三十億個堿基對）和生物結構的復雜性 ? 生物結構的多態(tài)性和生物數(shù)據(jù)的非精確性 ? 生物計算問題的高計算復雜性（大量重要的生物計算問題是NP難解問題） 傳統(tǒng)計算技術在生物計算中的局限性 ? 如何解決生物計算中的 NP難解問題已成為生物信息學中最重要的課題之一 ? 常規(guī)算法：無法克服高復雜計算 ? 近似算法：不能達到所要求的精度 ? 啟發(fā)式算法：無法保證計算問題的完成 ? 概率算法：無法確定生物數(shù)據(jù)的分布 研究思路 參數(shù)計算理論 生物基礎問題參數(shù)化模型 參數(shù)化算法設計與分析方法 生物軟件的開發(fā)與應用 生物計算基礎問題 生物計算問題結果 生物計算問題參數(shù)化求解及應用過程 生物基礎問題求解技術應用 計算智能、數(shù)據(jù)挖掘 生物計算熱點問題 參數(shù)計算理論與技術 許多 NP難解問題在實際應用中存在一個在小范圍中變化的參數(shù) k ，對這類問題，我們尋求時間復雜度為 f(k)nc 的算法 ? 這種算法不違反 P ? NP 的假設 ? 有這種算法的問題稱為 小參數(shù)可解 的 ? 當 k 值較小時， 小參數(shù)可解 算法是實際可行的 ? 沒有這種算法的問題稱為 小參數(shù)難解 的（為計算難解性研究提供了新技術） n k nc f(k) input putation time output 參數(shù)計算理論與算法技術 在生物計算中的應用 ? 生物問題數(shù)學建模中引入參數(shù) ? 許多生物計算問題中所含參數(shù)的值只在小范圍中變化 ? 避開 NP難解問題的困境 例：當 n = 106, k = 60 時 , 常規(guī)算法時間復雜度： nk = 10360 參數(shù)算法時間復雜度： +n ? ? 實際有效的精確算法解決生物計算問題