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