【正文】 S′)/(LN(N?1)/2)顯然，SPS 值反映了堿基對準(zhǔn)確對齊的比率。將圖中最大權(quán)值的邊連接起來的最大權(quán)值路徑，正好對應(yīng)輸入序列中保守區(qū)域的歸并，也就是所求調(diào)和序列對應(yīng)的路徑。提出了用于進(jìn)行全局DNA 多序列比對的一種方法：MWPAlign(maximum weighted pathalignment)。上述方法各有其不同的優(yōu)點，但它們中的大多數(shù)對于大量輸入序列，其時空復(fù)雜度依然是實際應(yīng)用的一個瓶頸，至少都O(N2L2)其中 N 是序列條數(shù)，L 是序列平均長度。根據(jù)SP 目標(biāo)函數(shù)，在比對結(jié)果的每一列中，將每對堿基給定一個分值 (例如：， 和?？偨Y(jié)本文提出了一種新的算法 MWPAlign，用圖結(jié)構(gòu)解決 DNA 多序列比對問題，其最大的特色有兩點：① 不需要進(jìn)行多序列比對就可以得到包含了所有輸入序列中保守區(qū)域的調(diào)和序列；② 對于大量數(shù)據(jù)有較好的比對結(jié)果和較優(yōu)的時間復(fù)雜度。對于蛋白質(zhì)序列，Σ包含 20 個不同的字母，分別代表 20 種不同的氨基酸，將其統(tǒng)稱為殘基。但是，不同的添加順序會產(chǎn)生不同的比對結(jié)果，所以，確定合適的比對順序是漸進(jìn)比對方法的一個關(guān)鍵問題。漸進(jìn)比對方法迭代地利用兩序列動態(tài)規(guī)劃算法，先由兩條序列的比對開始，逐漸添加新序列，直到所有序列都加入為止。假設(shè)一條長度為 m 的生物序列是由 m 個字符組成的字符串，字符串中的字符取自于一個有限的字母表Σ，對于DNA序列，Σ包含 A、T、C、G 四個字母，分別代表 4 種不同的核苷酸，將其統(tǒng)稱為堿基。所得調(diào)和序列是輸入序列中保守區(qū)域的拼接，通過得到的調(diào)和序列和每條輸入序列的兩兩比對，就很容易分辨輸入序列中保守的堿基和變異的堿基，從而構(gòu)造多序列比對結(jié)果。其中：“—”代表空位：x 和 y 代表兩個不同的堿基)，然后將這些分值 累加起來，得到每列的分值，最后將每列的分值累加，即可得到 SPScore。針對這個問題，本文提出了一種基于圖模型的新方法