《生物信息學》學習報告

實 驗 報 告 題 目 基于最大權值路徑算法的 DNA 多序列比對方法學習報告 學 院： 軟件學院 系 計算機 專業(yè)班級： 軟件工程 學生姓名： 何宇凡 學號： 406629515011 2016年 6月 1 日 摘要 在對《基于最大權值路徑算法的 DNA 多序列比對方法》的分析學習中，文中提出針對生物序列分析中的多序列比對問題，當輸入數據量比較大時，人們提出了很多啟發(fā)式的算法來改善計算速度和比對結果。提出了用于進行全局DNA 多序列比對的一種方法：MWPAlign(maximum weighted pathalignment)。該算法把序列信息用 de Bruijn 圖的形式表示，并將輸入序列的信息記錄在圖的邊上，這樣，就將求調和序列的問題轉化為求圖的最大權值路徑問題，使多序列比對問題的時間復雜度降低到幾乎線性。 基礎知識 多序列比對是生物信息學中挑戰(zhàn)性的問題之一，并在序列裝配、序列注釋、基因和蛋白質的結構和功能預測以及系統發(fā)育和進化分析等方面應用廣泛。它是SPS(sum-of-pairs scoring)意義下的 NP 完全問題?，F階段常用的比對方法分類：精確比對方法、漸進比對方法、迭代比對方法、基于圖論的比對方法。具體介紹如下： 精確比對方法 精確比對方法完全基于動態(tài)規(guī)劃算法，最為經典的是多維 Needlman-Wunsch 算法，但其可行的計算維數為 3。 漸進比對方法 迭代地利用兩序列動態(tài)規(guī)劃算法，先由兩條序列的比對開始，逐漸添加新序列，直到所有序列都加入為止。但是，不同的添加順序會產生不同的比對結果，所以，確定合適的比對順序是漸進比對方法的一個關鍵問題。而兩個序列越相似，人們對它們的比對就越有信心，因此，整個序列的比對應該從最相似的兩個序列開始，由近至遠逐步完成。 迭代比對方法 基于一個能產生比對的算法，并通過一系列的迭代方式改進多序列比對，直到比對結果不再改善為止。基于這種思想的方法很多，例如模擬退火、遺傳算法、隱馬爾可夫模型等。其中，最有影響的多序列比對軟件包 SAGA(sequence alignment by genetic algorithm）基于遺傳算法構建，共設計了 22 種不同的遺傳算子，采用動態(tài)調度的策略控制 22 種遺傳算子的使用。 基于圖論的比對方法 一種以有向無環(huán)圖(directed acyclic graph，簡稱 DAG)的表示方式取代行列表示的全新多序列比對方法。。 上述方法各有其不同的優(yōu)點，但它們中的大多數對于大量輸入序列，其時空復雜度依然是實際應用的一個瓶頸，至少都O(N2L2)其中 N 是序列條數，L 是序列平均長度。針對這個問題，本文提出了一種基于圖模型的新方法，將 de Bruijn graph 方法應用到 DNA 全局多序列比對中，使多序列比對的時空復雜度降低到線性 O(NL)。 基于最大權值路徑算法的 DNA 多序列比對方法 本算法用 de Bruijn graph[19]的形式表示輸入序列，將輸入序列的信息記錄在圖的邊上，定義邊的權值為經過該邊的序列的條數，則邊的權值越大，說明此邊越有可能代表輸入序列的保守區(qū)域。將圖中最大權值的邊連接起來的最大權值路徑，正好對應輸入序列中保守區(qū)域的歸并，也就是所求調和序列對應的路徑。設想所有輸入序列都是從一個祖先序列進化而來，我們要找的就是這個祖先序列。此過程不需要進行多序列比對，并且使尋找調和序列問題的時間復雜度大為降低，幾乎是線性的。最后，利用得到的調和序列和每條輸入序列進行兩兩比對得到比對結果。我們已經使用模擬數據對本算法進行了測試，并且和現有方法進行了比較，結果表明：MWPAlign(maximum weighted path alignment)是可行的 DNA 多序列比對方法，其時間復雜度優(yōu)于現有的方法，并且在序列變異率較低時，比對結果優(yōu)于 CLUSTALW，T-Coffee 和 HMMT(hidden Markov model training)。 問題描述 多序列比對的目標是使得參與比對的序列中有盡可能多的列具有相同的字符，即，使得相同殘基的位點位于同一列，這樣以便于發(fā)現不同的序列之間的相似部分，從而推斷它們在結構和功能上的相似關系，主要用于分子進化關系，預測蛋白質[1] 的二級結構和三級結構、估計蛋白質折疊類型的總數，基因組序列分析等。 假設一條長度為 m 的生物序列是由 m 個字符組成的字符串，字符串中的字符取自于一個有限的字母表Σ，對于DNA序列，Σ包含 A、T、C、G 四個字母，分別代表 4 種不同的核苷酸，將其統稱為堿基。對于蛋白質序列，Σ包含 20 個不同的字母，分別代表 20 種不同的氨基酸，將其統稱為殘基。給定 N 條序列組成的序列組 S=(s1，s2，。。。，sN)，其中：，為第 i 條序列的長度，則關于 S 的一個多序列比對可定義為一個矩陣。 該矩陣有如下特性： 1) 2) 如果刪除空位“—”，則 的每一行 與對應序列 相同； 3) S′中不存在只由空位“?”組成的列。 多序列比對結果的評判標準 目標函數用來評判序列比對結果的優(yōu)劣。在多序列比對中，最常用的目標函數是 Sum-of-Pairs(SP)[20]。根據SP 目標函數，在比對結果的每一列中，將每對堿基給定一個分值 (例如：， 和。其中：“—”代表空位：x 和 y 代表兩個不同的堿基)，然后將這些分值 累加起來，得到每列的分值，最后將每列的分值累加，即可得到 SP-Score。假定比對結果為 S′=( sij ′ )，1≤i≤N，1≤j≤L，則SP-Score 計算公式如下： 如果輸入數據是標準比對庫(例如 BALIBASE(benchmark alignment database))中的序列，即有一個標準的比對結果，我們就可以計算一個相對的 SP-Score，定義為 SPS。假定對于標準庫的輸入序列，標準庫中比對結果為S*，某方法比對結果為 S′，則 SPS 定義如下： SPS=SP-Score(S′)/SP-Score(S*) 如果沒有標準比對庫，SPS 定義如下： SPS=SP-Score(S′)/(LN(N?1)/2) 顯然，SPS 值反映了堿基對準確對齊的比率。為了反映所有序列準確對齊的比率，通常使用 CS(columnscore)值來計算。CS 值計算策略為：如果一列上的所有堿基都相等，則 ci=1；否則 ci=0。同樣，對于比對結果 S′，CS值計算公式為 基本上，SPS 值和 CS 值越高，說明比對結果越準確，越能反映序列的生物特性。在下面的實驗中，將采用 SPS和 CS 這兩個值來評估本算法的比對結果。 算法描述 MWPAlign 算法解決多序列比對問題的主要思想是：先求調和序列，然后用調和序列和每條輸入序列進行兩兩比對，得到最終比對結果。所得調和序列是輸入序列中保守區(qū)域的拼接，通過得到的調和序列和每條輸入序列的兩兩比對，就很容易分辨輸入序列中保守的堿基和變異的堿基，從而構造多序列比對結果。 總結 本文提出了一種新的算法 MWPAlign，用圖結構解決 DNA 多序列比對問題，其最大的特色有兩點：① 不需要進行多序列比對就可以得到包含了所有輸入序列中保守區(qū)域的調和序列；② 對于大量數據有較好的比對結果和較優(yōu)的時間復雜度。此算法相對于其他方法可以明顯降低時間復雜度，并且在序列變異率較低時取得了很好的比對結果。但是，此算法也有一些不足之處有待改進：當序列之間變異率較大時，比對結果較差；并且，算法本。 參考文獻 [1] Batzoglou S. The many faces of sequence alignment. Briefings in Bioinformatics, 2005,6(1):6?22. [2] Needlman SB, Wunsch CD. A general method application to the search for similarities in the amino acid sequence of two proteins. Journal of Molecular Biology, 1970,48(3):443?453. [3] Thompson JD, Higgins DG, Gibson TJ. CLUSTAL W. Improving the sensitivity of progressive multiple sequence alignmentthrough sequence weighting, position-specific gap penalties and weight matrix choice. Nucleic Acids Research, 1994,22(22): 4673?4680. [4] Notredame C, Higgins DG, Heringa J. T-Coffee: A novel method for fast and accurate multiple sequence alignment. Journal ofMolecular Biology, 2000,302(1):205?217. [5] Barton GJ, Sternberg MJE. A strategy for the rapid multiple alignment of protein sequences. Journal of Molecular Biology, 1987,198(2):327?337.