《單體型問題及其算法研究》是依託中國科學技術大學，由徐雲擔任項目負責人的面上項目。
基本介紹
- 中文名：單體型問題及其算法研究
- 項目類別：面上項目
- 項目負責人：徐雲
- 依託單位：中國科學技術大學
中文摘要,結題摘要,
中文摘要
人類是雙倍體結構，需將一條複合的基因型序列分解為兩條單體型序列，這就是單體型推導或分型問題。隨著國際HAPMAP計畫和我國生物學領域相關研究的如火如荼地開展，單體型推導等問題得到重視和廣泛研究。計算生物學是一種低成本、快速、大規模數據處理的可行手段，且當前出現的基於塊結構的方法和基於圖論的方法已成突破之勢，現在是切入研究的良好時機。本項目主要研究內容和方式：以單體型問題合理模型和基本算法研究為基礎，重點發展近期有前途的基於塊結構的算法和基於圖論方法的算法，以啟發式算法和並行化突出算法的實際套用效果。我們已在模型和基本算法以及塊劃分算法上取得一定成績，以此為基礎力使項目的創新體現在：建立融入連鎖不平衡特性的、合理的 k最少重組模型；套用統計和機器學習的方法提高塊劃分的合理性，改進我們提出的塊劃分算法；套用啟發式算法和並行化，使當前能解問題的規模(雜合位點數和個體數)由幾十量級提高到百位數。
結題摘要
人類是雙倍體結構，需將一條複合的基因型序列分解為兩條單體型序列，這就是單體型推導或分型問題。隨著國際HAPMAP計畫和我國生物學領域相關研究的如火如荼地開展，單體型推導等問題的計算生物學研究越來越重要。本項目以單體型問題表示模型和基本算法研究為基礎，重點發展基於塊結構的算法和基於圖論方法的算法，解決生物序列分析中的一些關鍵計算技術問題。通過三年的項目執行，我們已取得一些代表性的工作和成果：①對於單體型表示模型和推導算法，提出了以圖論方法為基礎的網路流模型和其上的一個啟發式推導算法FNphasing，該模型是首個具有全局視圖的表示模型，並且FNphasing算法在已有的測試數據集上計算精度和速度均為最好。本項科學意義在於全局視圖表示模型，避免了傳統方法的“黑箱”尋優做法。②對於傳統的快速2SNP算法進行了改造和最佳化，設計了一個計算速度與2SNP算法相當的單體型推導算法WinHap，而計算精度有明顯提升。本項科學意義在於可擴展的滑動視窗捕獲到的保守或頻繁信息，是基於分塊算法的真正目標和精髓。③對大規模生物序列分析中的關鍵計算技術和方法，提出了動態規劃計算的儘快計算模式和並行計算中的負載平衡方法，並在多序列公共子序列、Smith-Waterman序列比對和motif發現上，套用效果顯著。最後，在序列條數為800、長度為20000時，我們的算法FNphasing需要時間133.64s和空間為661MB，為目前性能最好。本項科學意義在於生物序列大數據處理的一種嘗試和突破。
