《新一代測序技術下單體型組裝問題計算模型和算法研究》是依託湖南師範大學，由謝民主擔任項目負責人的面上項目。
基本介紹
- 中文名：新一代測序技術下單體型組裝問題計算模型和算法研究
- 項目類別：面上項目
- 項目負責人：謝民主
- 依託單位：湖南師範大學
項目摘要,結題摘要,
項目摘要
單體型在複雜疾病致病基因定位等領域有重要的套用，而直接測定單體型代價過分昂貴，因此利用DNA片段數據組裝出單體型的計算問題深受研究，已有多個計算模型。這些模型絕大多數是NP-難及APX-難的，已有啟發式算法的驗證實驗均隱含著一個片段覆蓋單體型的大部分區域，已有精確算法則受片段覆蓋深度不能太大的約束。目前開始使用的新一代測序技術存在著能直接測序的片段較短、測序誤差較大和覆蓋深度大的特點，因此已有模型和算法的有效性受到了挑戰。本項目將深入分析新一代測序技術產生數據的特徵，結合分子遺傳學規律提出適用新一代測序技術的具有更高單體型重建精度的計算模型，對目前研究的單體型組裝問題進行擴展，使之適應病毒群需要組裝出多個單體型的場合。進而利用參數計算、圖論算法和聚類分析等技術，尋求實用有效算法。本項目的開展將進一步激發單體型計算模型及算法研究，有力地促進單體型檢測及其套用。
結題摘要
在本基金的支持下，課題組在新一代測序技術下單體型組裝計算問題組合最佳化模型的構建、高效算法的設計與分析上取得了顯著的進展。通過對單體型組裝問題相關真實生物數據的整合和數據特徵的抽取，課題組完成了模擬數據生成器的設計和測試平台的建設；結合圖論和聚類分析等技術提出了一個新的平衡最佳化劃分單體型組裝模型；課題組根據單體型組裝的實質是利用片段包含的兩個雜合SNP位點之間的組合模式來組裝一條染色體上較大區域的SNP序列，把片段數據轉化成兩位點連鎖圖，提出了新的連鎖圖示簽最佳化單體型組裝模型。這些新的單體型模型比已有的模型在單體型重建精度上有明顯的改善。通過對新一代測序技術下真實生物數據特徵的挖掘，課題組發現了測序片段數據具有一些小參數特徵：一個片段覆蓋的雜合SNP位點和覆蓋一個SNP位點的片段數通常都比較小；進而利用參數計算理論，為多個NP-難的單體型組裝最佳化模型設計了快速的參數化動態規劃精確算法。動態規劃遞推過程中要保留的中間計算結果的多少是影響動態規划算法時空複雜度的決定因素，課題組通過大量的測試發現只保留一部分較優的中間結果能大大加快算法的速度，而對最終計算結果沒有顯著影響。為了進一步加快單體型的重建，課題組為單體型組裝設計了基於top-k箇中間最優解的啟發式動態規划算法。項目促進了單體型計算模型及算法研究，項目的研究成果為生物信息學中大量複雜的計算問題的實用算法設計提供了新思路，也將促進單體型在複雜疾病全基因關聯分析中的套用。
