【正文】 ?易解的問題！ 有些問題至今只設計出算法時間復雜性為 O(2n)的算法，其中 n是問題的規(guī)模。 (not solvable practically)NPhard 60nC(2) motif finding 醫(yī)學上的問題：已知幾個串中有癌癥細胞，要求從中找出這幾個串它們的共性，也即是說，尋找一個子串，在每個串（或是大部分串）中都出現。 一般意義上，生物信息學是研究生物信息的采集、處理、存儲、傳播、分析和解釋等各方面的一門學科，它通過綜合利用 生物學 、 計算機科學 和 信息技術 揭示大量而復雜的生物數據所賦有的生物學奧秘。 2022年 4月 DNA堿基數目是 60億。 計算機的計算能力 以生物信息學為例 李紹華 信息學院計算機科學與技術系 20世紀三個重大的科技工程： （原子彈研制） （ HGP）：美英法德日中六國 Human Gene Program的目的： 完成人基因組 24條染色體上 5萬左右基因的作圖和 30億堿基的 DNA全序列的測定。2022年初這一數目已達 110億。 生物信息學的定義 生物信息學的研究 ? 以核酸蛋白質等生物大分子為主要 研究對象 ? 以信息、數理、計算機科學為主要 研究手段 ? 以計算機網絡為主要 研究環(huán)境 ? 以計算機軟件為主要 研究工具 ? 對序列數據進行 存儲、管理、注釋、加工 ? 對各種數據庫進行 查詢、搜索、比較、分析 ? 構建各種類型的專用 數據庫信息系統(tǒng) ? 研究開發(fā)面向生物學家的 新一代計算機軟件 生物信息學 – 研究方向 ? 基因組序列裝配 ? 基因識別 ? 基因功能預報 ? 基因多態(tài)性分析 ? 基因進化 ? mRNA結構預測 ? 基因芯片設計 ? 基因芯片數據分析 ? 疾病相關基因分析 ? 蛋白質序列分析 ? 蛋白質家族分類 ? 蛋白質結構預測 ? 蛋白質折疊研究 ? 代謝途徑分析 ? 轉錄調控機制 ? 蛋白質芯片設計 ? 蛋白質芯片數據分析 ? 藥物設計 生物信息學 – 研究方法 ? 利用數理統(tǒng)計、模式識別、動態(tài)規(guī)劃、密碼解讀、語意解析、信令傳遞、神經網絡、遺傳算法以及隱馬氏模型等各種方法 ? 對序列、結構數據進行 定性和定量分析 ，從中獲取基因編碼、基因調控、序列 結構 功能關系等理性知識 ? 闡明細胞、器官和個體的發(fā)生、發(fā)育、病變、衰亡的基本規(guī)律和 時空聯(lián)系 ? 探索生命起源、生物進化、生命本質等重大理論問題，最終建立 “ 生物學周期表 ” 生物信息學熱點問題（ 1） ? 基因組時期：序列－結構－功能 – DNA測序和拼接 – 分子生物數據庫 – 序列比對 – 分子進化 – 蛋白質質譜鑒定 – 序列注釋：基因預測、細胞定位 – 結構預測： RNA結構預測、蛋白質折疊 – 。 移除邊上的任意一點相當于刪除這條邊。 算法： //給定圖 G =V,E,其中 |V| =n， |E| =m 第一步：枚舉出 V中所有的子集： 子集總數 = (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足夠大時，全世界現有的計算機都無法在可接受的時間內求解。 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難解問題 ? 生物數據的海量性（人類基因組包含超過三十億個堿基對）和生物結構的復雜性 ? 生物結構的多態(tài)性和生物數據的非精確性 ? 生物計算問題的高計算復雜性（大量重要的生物計算問題是NP難解問題） 傳統(tǒng)計算技術在生物計算中的局限性 ? 如何解決生物計算中的 NP難解問題已成為生物信息學中最重要的課題之一 ? 常規(guī)算法：無法克服高復雜計算 ? 近似算法：不能達到所要求的精度 ? 啟發(fā)式算法：無法保證計算問題的完成 ? 概率算法：無法確定生物數據的分布 研究思路 參數計算理論 生物基礎問題參數化模型 參數化算法設計與分析方法 生物軟件的開發(fā)與應用 生物計算基礎問題 生物計算問題結果 生物計算問題參數化求解及應用過程 生物基礎問題求解技術應用 計算智能、數據挖掘 生物計算熱點問題 參數計算理論與技術 許多 NP難解問題在實際應用中存在一個在小范圍中變化的參數 k ，對這類問題，我們尋求時間復雜度為 f(k)nc 的算法 ? 這種算法不違反 P ? NP 的假設 ? 有這種算法的問題稱為 小參數可解 的 ? 當 k 值較小時， 小參數可解 算法是實際可行的 ? 沒有這種算法的問題稱為 小參數難解 的（為計算難解性研究提供了新技術） n k nc f(k) input putation time output 參數計算理論與算法技術 在生物計算中的應用 ? 生物問題數學建模中引入參數 ? 許多生物計算問題中所含參數的值只在小范圍中變化 ? 避開 NP難解問題的困境 例：當 n = 106, k = 60 時 , 常規(guī)算法時間復雜度： nk = 10360 參數算法時間復雜度： +n ? ? 實際有效的精確算法解決生物計算問題 。 ? 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