《基因組比較問題的算法與複雜性》是依託山東大學，由朱大銘擔任項目負責人的面上項目。
基本介紹
- 中文名：基因組比較問題的算法與複雜性
- 項目類別：面上項目
- 項目負責人：朱大銘
- 依託單位：山東大學
中文摘要,結題摘要,
中文摘要
基因組比較的核心問題是計算兩個基因組的量化距離。本課題討論基因組重組排序與基因組樣本斷點距離兩個基因組比較問題的算法與複雜性。設計有向基因組Reversal與Translocation排序的局部搜尋近似算法；設計有向基因組一般Translocation排序的新精確算法；設計無向基因組Cut-And-Paste排序新近似算法；證明基因組Transposition排序的複雜性；設計基因組短塊移動排序的改進近似算法；設計基因組樣本斷點距離問題的亞指數時間精確算法。力圖在上述內容研究中取得新突破。基因組比較算法有助於人們確定基因組的相同與不同區域，充分理解基因的結構與功能，定位控制基因功能的信息，從而找到克服人類疾病的新方法。
結題摘要
本項目研究了一類基因組比較問題的算法與計算複雜性。設計出一組基因組重組排序或基因組重組距離計算問題的近似算法，為項目的標誌性結果。基因組重組距離計算是計算比較基因組學的主流分支，近似算法則是解答NP-Hard最佳化問題的有效手段，也是算法與計算複雜性研究的核心內容。 在國家自然科學基金“基因組比較問題的算法與複雜性(61070019)”的資助下，完成如下主要研究成果：(1)設計出有向基因組一般移位排序的多項式時間算法；(2)設計出無向基因組切割再貼上排序近似性能比為2.25的多項式時間近似算法；(3)設計出基因組短塊移動排序近似性能比為14/11的多項式時間近似算法，進一步設計出整數排列逆序基因對數目足夠多時的(1+e)-近似算法；(4)設計出樣本斷點零距離問題(ZEBD)時間複雜性為O(n^2*1.86^n)的精確算法；(5)設計出單面片段框架填充問題近似性能比為5/4的多項式時間近似算法，設計出雙面片段填充問題近似性能比為1.5的多項式時間近似算法；(6)設計出無向基因組互動型移位排序近似性能比為1.408+e的多項式時間近似算法；(7)設計出最大不全k-滿足問題的盲目局部搜尋近似算法，近似性能比可達到2^(k-1)/(2^(k-1)-1)。已發表學術論文16篇，其中SCI收錄11篇，EI收錄7篇；期刊論文12篇，會議論文4篇；計算機學會倡導的頂級期刊論文9篇。受邀在全國年會做特邀報告一次。獲得山東省自然科學獎3等獎1項，山東大學優秀博士學位論文獎2項。培養博士生6名，碩士生5名。
