《生物信息學》學習報告

《《生物信息學》學習報告》由會員分享，可在線閱讀，更多相關《《生物信息學》學習報告（5頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、 實 驗 報 告 題 目 基于最大權值路徑算法的 DNA 多序列比對方法學習報告 學 院： 軟件學院 系 計算機 專業(yè)班級： 軟件工程 學生姓名： 何宇凡 學號： 406629515011 2016年 6月 1 日 摘要 在對《基于最大權值路徑算法的 DNA 多序列比對方法》的分析學習中，文中提出針對生物序列分析中的多序列比對問題，當輸入數(shù)據(jù)量比較大時，人們提出了很多

2、啟發(fā)式的算法來改善計算速度和比對結(jié)果。提出了用于進行全局DNA 多序列比對的一種方法：MWPAlign(maximum weighted pathalignment)。該算法把序列信息用 de Bruijn 圖的形式表示，并將輸入序列的信息記錄在圖的邊上，這樣，就將求調(diào)和序列的問題轉(zhuǎn)化為求圖的最大權值路徑問題，使多序列比對問題的時間復雜度降低到幾乎線性。 基礎知識 多序列比對是生物信息學中挑戰(zhàn)性的問題之一，并在序列裝配、序列注釋、基因和蛋白質(zhì)的結(jié)構和功能預測以及系統(tǒng)發(fā)育和進化分析等方面應用廣泛。它是SPS(sum-of-pairs scoring)意義下的 NP 完全問題?，F(xiàn)階段常用的比對

3、方法分類：精確比對方法、漸進比對方法、迭代比對方法、基于圖論的比對方法。具體介紹如下： 精確比對方法 精確比對方法完全基于動態(tài)規(guī)劃算法，最為經(jīng)典的是多維 Needlman-Wunsch 算法，但其可行的計算維數(shù)為 3。 漸進比對方法 迭代地利用兩序列動態(tài)規(guī)劃算法，先由兩條序列的比對開始，逐漸添加新序列，直到所有序列都加入為止。但是，不同的添加順序會產(chǎn)生不同的比對結(jié)果，所以，確定合適的比對順序是漸進比對方法的一個關鍵問題。而兩個序列越相似，人們對它們的比對就越有信心，因此，整個序列的比對應該從最相似的兩個序列開始，由近至遠逐步完成。 迭代比對方法 基于一個能產(chǎn)生比對的算法，并通過一系

4、列的迭代方式改進多序列比對，直到比對結(jié)果不再改善為止。基于這種思想的方法很多，例如模擬退火、遺傳算法、隱馬爾可夫模型等。其中，最有影響的多序列比對軟件包 SAGA(sequence alignment by genetic algorithm）基于遺傳算法構建，共設計了 22 種不同的遺傳算子，采用動態(tài)調(diào)度的策略控制 22 種遺傳算子的使用。 基于圖論的比對方法 一種以有向無環(huán)圖(directed acyclic graph，簡稱 DAG)的表示方式取代行列表示的全新多序列比對方法。。 上述方法各有其不同的優(yōu)點，但它們中的大多數(shù)對于大量輸入序列，其時空復雜度依然是實際應用的一個瓶頸，至少

5、都O(N2L2)其中 N 是序列條數(shù)，L 是序列平均長度。針對這個問題，本文提出了一種基于圖模型的新方法，將 de Bruijn graph 方法應用到 DNA 全局多序列比對中，使多序列比對的時空復雜度降低到線性 O(NL)。 基于最大權值路徑算法的 DNA 多序列比對方法 本算法用 de Bruijn graph[19]的形式表示輸入序列，將輸入序列的信息記錄在圖的邊上，定義邊的權值為經(jīng)過該邊的序列的條數(shù)，則邊的權值越大，說明此邊越有可能代表輸入序列的保守區(qū)域。將圖中最大權值的邊連接起來的最大權值路徑，正好對應輸入序列中保守區(qū)域的歸并，也就是所求調(diào)和序列對應的路徑。設想所有輸入序列都是

6、從一個祖先序列進化而來，我們要找的就是這個祖先序列。此過程不需要進行多序列比對，并且使尋找調(diào)和序列問題的時間復雜度大為降低，幾乎是線性的。最后，利用得到的調(diào)和序列和每條輸入序列進行兩兩比對得到比對結(jié)果。我們已經(jīng)使用模擬數(shù)據(jù)對本算法進行了測試，并且和現(xiàn)有方法進行了比較，結(jié)果表明：MWPAlign(maximum weighted path alignment)是可行的 DNA 多序列比對方法，其時間復雜度優(yōu)于現(xiàn)有的方法，并且在序列變異率較低時，比對結(jié)果優(yōu)于 CLUSTALW，T-Coffee 和 HMMT(hidden Markov model training)。 問題描述 多序列比對的

7、目標是使得參與比對的序列中有盡可能多的列具有相同的字符，即，使得相同殘基的位點位于同一列，這樣以便于發(fā)現(xiàn)不同的序列之間的相似部分，從而推斷它們在結(jié)構和功能上的相似關系，主要用于分子進化關系，預測蛋白質(zhì)[1] 的二級結(jié)構和三級結(jié)構、估計蛋白質(zhì)折疊類型的總數(shù)，基因組序列分析等。 假設一條長度為 m 的生物序列是由 m 個字符組成的字符串，字符串中的字符取自于一個有限的字母表Σ，對于DNA序列，Σ包含 A、T、C、G 四個字母，分別代表 4 種不同的核苷酸，將其統(tǒng)稱為堿基。對于蛋白質(zhì)序列，Σ包含 20 個不同的字母，分別代表 20 種不同的氨基酸，將其統(tǒng)稱為殘基。給定 N 條序列組成的序列組 S

8、=(s1，s2，。。。，sN)，其中：，為第 i 條序列的長度，則關于 S 的一個多序列比對可定義為一個矩陣。 該矩陣有如下特性： 1) 2) 如果刪除空位“—”，則 的每一行 與對應序列 相同； 3) S′中不存在只由空位“?”組成的列。 多序列比對結(jié)果的評判標準 目標函數(shù)用來評判序列比對結(jié)果的優(yōu)劣。在多序列比對中，最常用的目標函數(shù)是 Sum-of-Pairs(SP)[20]。根據(jù)SP 目標函數(shù)，在比對結(jié)果的每一列中，將每對堿基給定一個分值 (例如：， 和。其中：“—”代表空位：x 和 y 代表兩個不同的堿基)，然后將這些分值 累加起來，得到每列的分值，最后將每列的分值累加

9、，即可得到 SP-Score。假定比對結(jié)果為 S′=( sij ′ )，1≤i≤N，1≤j≤L，則SP-Score 計算公式如下： 如果輸入數(shù)據(jù)是標準比對庫(例如 BALIBASE(benchmark alignment database))中的序列，即有一個標準的比對結(jié)果，我們就可以計算一個相對的 SP-Score，定義為 SPS。假定對于標準庫的輸入序列，標準庫中比對結(jié)果為S*，某方法比對結(jié)果為 S′，則 SPS 定義如下： SPS=SP-Score(S′)/SP-Score(S*) 如果沒有標準比對庫，SPS 定義如下： SPS=SP-Score(S′)/(LN(N?1)

10、/2) 顯然，SPS 值反映了堿基對準確對齊的比率。為了反映所有序列準確對齊的比率，通常使用 CS(columnscore)值來計算。CS 值計算策略為：如果一列上的所有堿基都相等，則 ci=1；否則 ci=0。同樣，對于比對結(jié)果 S′，CS值計算公式為 基本上，SPS 值和 CS 值越高，說明比對結(jié)果越準確，越能反映序列的生物特性。在下面的實驗中，將采用 SPS和 CS 這兩個值來評估本算法的比對結(jié)果。 算法描述 MWPAlign 算法解決多序列比對問題的主要思想是：先求調(diào)和序列，然后用調(diào)和序列和每條輸入序列進行兩兩比對，得到最終比對結(jié)果。所得調(diào)和序列是輸入序列中保守區(qū)域的拼接，

11、通過得到的調(diào)和序列和每條輸入序列的兩兩比對，就很容易分辨輸入序列中保守的堿基和變異的堿基，從而構造多序列比對結(jié)果。 總結(jié) 本文提出了一種新的算法 MWPAlign，用圖結(jié)構解決 DNA 多序列比對問題，其最大的特色有兩點：① 不需要進行多序列比對就可以得到包含了所有輸入序列中保守區(qū)域的調(diào)和序列；② 對于大量數(shù)據(jù)有較好的比對結(jié)果和較優(yōu)的時間復雜度。此算法相對于其他方法可以明顯降低時間復雜度，并且在序列變異率較低時取得了很好的比對結(jié)果。但是，此算法也有一些不足之處有待改進：當序列之間變異率較大時，比對結(jié)果較差；并且，算法本。 參考文獻 [1] Batzoglou S. The many f

12、aces 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. CLU

13、STAL 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.