《基因組比較與分析算法研究》是依託山東大學，由朱大銘擔任項目負責人的面上項目。
基本介紹
- 中文名：基因組比較與分析算法研究
- 項目類別：面上項目
- 項目負責人：朱大銘
- 依託單位：山東大學
中文摘要,結題摘要,
中文摘要
翻轉與移位排序、短塊移動排序、樣本斷點距離、和片段框架填充，均為基因組比較與分析的代表性問題。設計無向基因組翻轉和移位排序問題的新近似算法，改進算法的近似性能比；設計基因組短塊移動排序的改進近似算法，證明該問題的複雜性；設計零樣本斷點距離問題的確定精確算法和隨機求解算法，改進算法的時間複雜性，設計樣本斷點距離問題的實用參數算法；設計單面片段框架填充問題的新近似算法，改進算法近似性能比；證明單面片段框架填充問題子問題的複雜性，設計其近似算法；設計雙面片段框架填充問題的改進近似算法。算法設計均以達到以前未曾達到的量化性能指標為目標，複雜性研究則以證明目前尚未確定複雜性問題的NP-難解性為目標。將設計出的新算法實現為生物信息學軟體，用於以基因組比較分析為基礎的分子生物學和醫學研究與實踐中。
結題摘要
項目研究內容以基因組結構比較分析為背景。研究基因組結構差異分析的組合最佳化問題模型，和解答問題的算法。 將無向基因組移位排序的近似性能比由1.408改進為1.375。設計出無向斷點圖2-圈分解的多項式時間算法，解決了一個開放20年的基因組重排研究中的基本問題。設計出基因組雙面片段填充近似性能比為1.5的多項式時間近似算法，並將近似性能比進一步改進為1.4+e。設計出(1,2)-樣本斷點距離問題的新動態規划算法，最長樣本公共子序列問題的新動態規划算法。最長樣本公共子序列用於表示基因組保守子序列，在基因組功能分析研究中具有重要意義。設計出基因組短交換排序問題判定版本的多項式算法，解決了開放10年的基因組比較領域的典型問題。給出轉錄組組裝新算法，計算精度和運算時間好於原有算法。給出一個利用自頂向下蛋白質質譜數據，鑑定蛋白質的有向圖模型。這一模型可有效避免鑑定過程中的蛋白質丟失問題，並能保證計算速度。在國家自然科學基金資助下，於2016年舉辦了第十屆國際算法前沿年會(FAW2016)，於2018年舉辦了第24屆國際計算與組合年會(Cocoon2018)。發表期刊論文11篇，SCI收錄10篇，國際會議論文15篇。
