生物信息學(xué)學(xué)習(xí)報(bào)告(存儲版)
【正文】 序列的信息記錄在圖的邊上，定義邊的權(quán)值為經(jīng)過該邊的序列的條數(shù)，則邊的權(quán)值越大，說明此邊越有可能代表輸入序列的保守區(qū)域。對于蛋白質(zhì)序列，Σ包含 20 個不同的字母，分別代表 20 種不同的氨基酸，將其統(tǒng)稱為殘基。假定比對結(jié)果為 S′=( sij ′ )，1≤i≤N，1≤j≤L，則SPScore 計(jì)算公式如下：如果輸入數(shù)據(jù)是標(biāo)準(zhǔn)比對庫(例如 BALIBASE(benchmark alignment database))中的序列，即有一個標(biāo)準(zhǔn)的比對結(jié)果，我們就可以計(jì)算一個相對的 SPScore，定義為 SPS?？偨Y(jié)本文提出了一種新的算法 MWPAlign，用圖結(jié)構(gòu)解決 DNA 多序列比對問題，其最大的特色有兩點(diǎn)：① 不需要進(jìn)行多序列比對就可以得到包含了所有輸入序列中保守區(qū)域的調(diào)和序列；② 對于大量數(shù)據(jù)有較好的比對結(jié)果和較優(yōu)的時間復(fù)雜度。算法描述MWPAlign 算法解決多序列比對問題的主要思想是：先求調(diào)和序列，然后用調(diào)和序列和每條輸入序列進(jìn)行兩兩比對，得到最終比對結(jié)果。根據(jù)SP 目標(biāo)函數(shù)，在比對結(jié)果的每一列中，將每對堿基給定一個分值 (例如：， 和。問題描述 多序列比對的目標(biāo)是使得參與比對的序列中有盡可能多的列具有相同的字符，即，使得相同殘基的位點(diǎn)位于同一列，這樣以便于發(fā)現(xiàn)不同的序列之間的相似部分，從而推斷它們在結(jié)構(gòu)和功能上的相似關(guān)系，主要用于分子進(jìn)化關(guān)系，預(yù)測蛋白質(zhì)[1] 的二級結(jié)構(gòu)和三級結(jié)構(gòu)、估計(jì)蛋白質(zhì)折疊類型的總數(shù)，基因組序列分析等。上述方法各有其不同的優(yōu)點(diǎn)，但它們中的大多數(shù)對于大量輸入序列，其時空復(fù)雜度依然是實(shí)際應(yīng)用的一個瓶頸，至少都O(N2L2)其中 N 是序列條數(shù)，L 是序列平均長度。具體介紹如下：精確比對方法精確比對方法完全基于動態(tài)規(guī)劃算法，最為經(jīng)典的是多維 NeedlmanWunsch 算法，但其可行的計(jì)算維數(shù)為 3。提出了用于進(jìn)行全局DNA 多序列比對的
電大資料相關(guān)推薦
鄂ICP備17016276號-1