【正文】 點集 V的一個子集 V’ ? V， 使得若 (u,v)是 G的一條邊，則 v∈ V’或 u∈ V’。 設(shè) f = 1%, p =∞，則 Acc_Speed =100 結(jié)論：一個問題的求解若有 1%的串行度，則 無論有多少臺計算機并行計算 ，其計算速度至多是單臺計算機計算同一個問題的 100倍！ 易難 /難解 /不可解問題 從時間復(fù)雜性分析來說，許多問題的算法時間復(fù)雜性是 O(nc)的，其中 n是問題的規(guī)模， c是常量。 P=？ NP 1． P類問題 is in NP類問題： P ? NP 即 : P類問題一定也是 NP類問題； 2. NP類問題 is in P類問題？ NP ? P ?不知道！ 計算機理論假設(shè)： NP類問題 is not in P類問題！ 即 P≠NP 關(guān)鍵科學(xué)問題： 大量重要的生物組合計算問題是 NP難解問題 ? 生物數(shù)據(jù)的海量性（人類基因組包含超過三十億個堿基對）和生物結(jié)構(gòu)的復(fù)雜性 ? 生物結(jié)構(gòu)的多態(tài)性和生物數(shù)據(jù)的非精確性 ? 生物計算問題的高計算復(fù)雜性（大量重要的生物計算問題是NP難解問題） 傳統(tǒng)計算技術(shù)在生物計算中的局限性 ? 如何解決生物計算中的 NP難解問題已成為生物信息學(xué)中最重要的課題之一 ? 常規(guī)算法：無法克服高復(fù)雜計算 ? 近似算法：不能達到所要求的精度 ? 啟發(fā)式算法：無法保證計算問題的完成 ? 概率算法：無法確定生物數(shù)據(jù)的分布 研究思路 參數(shù)計算理論 生物基礎(chǔ)問題參數(shù)化模型 參數(shù)化算法設(shè)計與分析方法 生物軟件的開發(fā)與應(yīng)用 生物計算基礎(chǔ)問題 生物計算問題結(jié)果 生物計算問題參數(shù)化求解及應(yīng)用過程 生物基礎(chǔ)問題求解技術(shù)應(yīng)用 計算智能、數(shù)據(jù)挖掘 生物計算熱點問題 參數(shù)計算理論與技術(shù) 許多 NP難解問題在實際應(yīng)用中存在一個在小范圍中變化的參數(shù) k ，對這類問題，我們尋求時間復(fù)雜度為 f(k)nc 的算法 ? 這種算法不違反 P ? NP 的假設(shè) ? 有這種算法的問題稱為 小參數(shù)可解 的 ? 當(dāng) k 值較小時， 小參數(shù)可解 算法是實際可行的 ? 沒有這種算法的問題稱為 小參數(shù)難解 的（為計算難解性研究提供了新技術(shù)） n k nc f(k) input putation time output 參數(shù)計算理論與算法技術(shù) 在生物計算中的應(yīng)用 ? 生物問題數(shù)學(xué)建模中引入?yún)?shù) ? 許多生物計算問題中所含參數(shù)的值只在小范圍中變化 ? 避開 NP難解問題的困境 例：當(dāng) n = 106, k = 60 時 , 常規(guī)算法時間復(fù)雜度： nk = 10360 參數(shù)算法時間復(fù)雜度： +n ? ? 實際有效的精確算法解決生物計算問題 。 ?難解的問題！ 比如： SAT, VC, CLIQUE, IS, TSP, ……… ?不可解的問題！ 即：任何計算機不論耗費多少時間也不能解的問題。 算法： //給定圖 G =V,E,其中 |V| =n， |E| =m 第一步：枚舉出 V中所有的子集： 子集總數(shù) = (n1) + (n2) +(n3) +…+ (nn) =2n 第二步：判斷每個子集是否是圖 G的頂點覆蓋：for i =1 to m do…… 算法時間復(fù)雜性： O(2n*m) ?可計算否？ 例 : ? 假設(shè) n=56, 在一臺運行速度為 億次級每秒的計算機里用枚舉法求解 VC問題，須花時多少？ ? 計算：我們假設(shè)該機器每秒鐘可判斷一億種的方案是否正確！則有： ? 2^56種方案 /1億種每秒 /60/60/24/365 =(年 )！ 結(jié)論：對于 O(2n)的算法，當(dāng) n足夠大時，全世界現(xiàn)有的計算機都無法在可接受的時間內(nèi)求解。 ? 子串相似性的定義：在串中間插、刪、改的次數(shù)不超過 6次，使得兩個子串相同。 移除邊上的任意一點相當(dāng)于刪除這條邊。 熱點 Ⅰ ： 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 gtt