基因組學問題的精確算法

《基因組學問題的精確算法》是依託西安電子科技大學，由王新輝擔任項目負責人的青年科學基金項目。

基本介紹

• 中文名：基因組學問題的精確算法
• 項目類別：青年科學基金項目
• 項目負責人：王新輝
• 依託單位：西安電子科技大學

中文摘要

本課題主要研究精確算法在基因組學中兩個常見問題中的套用：序列比對問題和基因表達及調控分析問題.這兩個問題在基因組學中有著重要的套用,但傳統的模型和方法缺乏穩定性和精確性,不能夠揭示生物過程的內在機理,故組合最佳化模型是一種新的有效途徑.但組合最佳化模型通常是NP-難問題,並且其近似解在生物學上意義不大,故尋找複雜度低,實際可行的精確算法成為解決此類問題的重關鍵.本課題以此為出發點,結合這些基因組學中問題本身的結構,利用生物進化保守性以及DNA的三維結構,設計這些問題新的最佳化模型；然後利用精確算法中新出現的技巧:固定參數化算法和樹寬圖的概念,設計複雜度低的可以在實際中套用的算法；把得到的算法進一步推廣到其他基因組學中的問題上以及組合最佳化問題上,促進這些問題精確算法的改進；利用得到的算法研究與樹寬相關問題的精確算法的理論；根據得到的算法和理論討論精確算法的下界,從而促進精確算法、其理論和套用的研究

結題摘要

近些年,由於新一代測序技術的發展,使得臨床醫學基因組學研究成為可能.但是隨著海量數據的產生,這使得基因組學問題模型變得更加複雜,算法複雜度更高.模型求解成為解決這些醫學問題的瓶頸,和模型結構相結合的算法成為解決此類問題的一個有效途徑.本課題集中在基因組學若干問題上,給出其數學模型,給出與模型結合的精確算來求解生物醫學中的問題. 本課題經過三年的研究,部分結果已發表,部分結果尚待發表,主要結果包含以下幾個方面： 設計了基因表達調節問題的數學模型以及相關的精確算法.在基因表達與調節問題中的結合位點識別問題上,結合DNA的三維結構,給出了一種非常有效的尋找結合位點的方法.相比於已有的方法,此方法可進一步提高結合位點識別的準確度和精度；利用設計的算法,研究基因表達以及基因組學和免疫系統的關係,發現了一個重要的致病基因以及其功能;另一方面,設計了一個整合統計和網路分析的模型,利用精確算法,尋求最小子圖,尋找發病基因和疾病的關係,以及基因組和免疫系統的關係.設計了細菌種群和環境因素問題的模型和精確算法.在研究細菌種群的時候,如何正確的判斷細菌種群和環境因素之間的關係時問題得核心.由於環境因素眾多,這些環境因素可能相互影響,需要用多元分析的方法正確揭示這些關係.我們設計了一個新的多元分析的方法,此方法在研究細菌種群和基因表達的關聯性中有著重要的套用.根據所有相關的基因以及相應的環境條件,根據時間節點,組建不同的網路,然後通過尋找這些網路間的相似子圖,來發現基因,細菌和環境條件的關係.對於每一個時間節點的網路建立,需要正確計算環境因素和基因的關係.把所設計的模型套用到老年痴呆模型,發現幾個特別的基因在老年痴呆病的發作中發揮著重要的套用;把所設計的模型利用到細菌種群資料庫上,得到了一系列細菌的共存性和排斥性;所設計的模型用於驗證類藥物對提高調節性免疫細胞的活性調節上,發現了一種藥物的調節作用.設計了序列比對問題的精確算法.對於序列比對問題,把此問題轉化為一個Steiner樹模型,設計了一個算法,可以估計相對保守性序列的長度,以此為長度作為固定參數,設計了一個精確算法,複雜度大為降低,在理論上得到預期的結果.對於臨床醫學中的實際問題,結合數據的特點,其提出了樹星的概念,指出所有子圖都可以轉化為一個或者若干樹星e,而樹星的數目是有限的,故算法求解的空間也非常有限,故很大程度的降低。