《基因組比較中三個組合問題的算法研究》是依託山東大學，由姜海濤擔任項目負責人的青年科學基金項目。
基本介紹
- 中文名：基因組比較中三個組合問題的算法研究
- 項目類別：青年科學基金項目
- 項目負責人：姜海濤
- 依託單位：山東大學
中文摘要,結題摘要,
中文摘要
計算基因組距離是基因組比較和重組研究的重要內容之一。斷點距離是最基本的基因組比較量化依據；移位距離是經典的基因組重組距離量化形式之一。本課題中討論基因組片段填充的斷點距離問題、基因組PQ-樹的相似性比較問題和基因組移位重組距離問題的算法和計算複雜性。(1)設計有重複基因組雙面填充的第一個非平凡近似算法，改進有重複基因組單面填充的近似算法的近似比，並證明有重複基因組片段填充的不可近似性；(2)證明基因組PQ-樹斷點中心問題是NP-完全的，並改進基因組PQ-樹斷點中心問題的參數化算法的時間複雜度；(3)設計無向基因組移位排序問題的第一個參數化算法，並改進該問題近似算法的近似比。力圖在上述內容研究中取得新進展。基因組比較算法有助於簡化全基因組測序過程，依據基因組上的相同和不同區域，快速定位致病基因並充分理解其結構與功能，為遺傳疾病的基因治療提供新思路。
結題摘要
基因組的比較與重組是計算基因組學研究的重要內容之一，對於探究物種間的進化規律，分析基因的功能都有著重要的指導意義。本項目中，重點研究了基因組比較中的三個組合最佳化問題：（1）基因組序列的片段填充問題；（2）基因組PQ-樹的相似性比較問題；（3）基因組排列的移位重組排序問題，並拓展研究了：（4）基因組排列的短塊移動排序問題；（5）基因組最長帶恢復問題。對上述問題，從計算複雜性、多項式時間近似算法、參數算法、核心化等分析解決NP-困難問題的角度進行了深入研究，取得了的研究成果如下： （1）提出以最大化公共鄰接數為最佳化目標的基因組序列片段填充問題，並證明了最優填充方案的公共鄰接數的下界。設計了單面片段填充問題的近似性能比為4/3的近似算法；後來又將近似性能比依次改進至5/4和6/5，並證明該問題是APX-hard的。設計了雙面片段填充問題的近似性能比為3/2的近似算法。（2）證明了基因組PQ-樹斷點中心問題是NP-完全的，並對於比較一棵PQ-樹基因組和一個排列的特殊問題，設計了時間複雜度為O*(3K)的參數算法。（3）將基因組移位排序問題的近似算法的近似性能比改進至1.408+e。（4）證明了基因組短塊移動排序問題最優解的更緊下界，並設計了近似性能比為5/4的近似算法。（5）證明基因組最長帶恢復問題存在大小為18K的亞核和78K的核。 證明問題的計算複雜性可以從理論上說明求解問題的困難程度，近似性能比和時間複雜度分別是評估近似算法和參數算法優劣的量化指標。項目中的絕大多數研究成果還是當前解決該問題的最好結果，我們也一直期待著和致力於研究出更好的成果。
