《生物信息學(xué)》學(xué)習(xí)報(bào)告

《《生物信息學(xué)》學(xué)習(xí)報(bào)告》由會(huì)員分享，可在線閱讀，更多相關(guān)《《生物信息學(xué)》學(xué)習(xí)報(bào)告（5頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

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

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

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

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

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

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

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

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

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

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

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