【文章內(nèi)容簡(jiǎn)介】 SmithWateman算法是在 NeedlemanWunsch算法基礎(chǔ)上發(fā)展而來的，它是一種局部聯(lián)配 (Local alignment)算法。 這二種算法均可以用于核酸和蛋白質(zhì)序列。在給定空位罰值和替換矩陣情況下，它們總是能給出具有最高聯(lián)配值的聯(lián)配。但是，這個(gè)聯(lián)配并不需要達(dá)到生物學(xué)意義上的顯著水平。 許多程序可通過匿名 ftp服務(wù)用于兩條序列的聯(lián)配計(jì)算。 GCG軟件包中， BESFIT和 GAP程序便是用于兩對(duì)序列的聯(lián)配。在一些網(wǎng)站可以進(jìn)行兩條序列的聯(lián)配分析，例如：ALIGN(ign(ograms/)。 ALIGN允許用戶提供序列進(jìn)行聯(lián)配， 允許選擇替換矩陣，但不能設(shè)置空位罰值。 Align只能進(jìn)行數(shù)據(jù)庫(kù)中已有序列間的聯(lián)配分析。 從整體上分析兩個(gè)序列的關(guān)系，即考慮序列總長(zhǎng)的整體比較，用類似于使整體相似 (global similarity)最大化的方式，對(duì)序列進(jìn)行聯(lián)配。兩個(gè)不等長(zhǎng)度序列的聯(lián)配分析必需考慮在一個(gè)序列中圈掉一些堿基或在另一序列作空位 (gap)處理。 Needleman 和 Wunsch(1970)的法則為這些步驟提供了實(shí)例。這一算法是 為氨基酸序列發(fā)展 的，但也可以用于核苷酸序列。算法最初尋求的是使兩條序列間的距離最小。盡管這類距離的元素是以一種特定的方式定義的，但該算法的良好特性在于它確定了最短距離。這是一個(gè)動(dòng)態(tài)規(guī)劃(dynamic programming)的方法。 NeedlemanWunsch算法 NeedlemanWunsch算法 將兩條聯(lián)配的序列沿雙向表的軸放置。從任一堿基對(duì)，即表中的任一單元開始，聯(lián)配可延三種可能的方式延伸：如果堿基不匹配，則每一序列加上一個(gè)堿基，并給其增加一個(gè)規(guī)定的距離權(quán)重；或在一個(gè)序列中增加一個(gè)堿基而在另一序列中增加一個(gè)空位或反之亦然。引入一個(gè)空位時(shí)也將增加一個(gè)規(guī)定的距離權(quán)重。 NeedlemanWunsch算法 因此，表中的一個(gè)單元可以從 (至多 )三個(gè)相鄰的單元達(dá)到。我們把到左上角單元距離最小的方向看作相似序列延伸的方向。等距離時(shí)意味著存在兩種可能的方向。將這些方向記錄下來，并在研究了所有的單元之后，沿著記錄的方向就有一條路徑可從右下角 (兩個(gè)序列的末端 )追蹤到左上角 (兩個(gè)序列的起點(diǎn) )。由此所產(chǎn)生的路徑將給出具有最短距離的序列聯(lián)配。 NeedlemanWunsch算法 以兩個(gè)短序列 CTGTATC和 CTATAATCCC為例： 設(shè)堿基錯(cuò)配時(shí)距離權(quán)重為 1，引入一個(gè)空位時(shí)距離權(quán)重為 3。該圖邊緣的行和列作為起始條件增加到表中。在單元 5行 3列，即相應(yīng)較短序列 (第二序列 )的第 2個(gè) T堿基和較長(zhǎng)序列 (第一序列 )的第 1個(gè) T堿基位置，有 三 種可能的距離增量。設(shè)在各序列中增加堿基 T時(shí) (從 4行 2列移動(dòng) )對(duì)距離的貢獻(xiàn)為 0。從 5行 2列的位置作水平移動(dòng) (等價(jià)于增加第二序列的堿基 T而在第一序列引入一個(gè)空位 )，在本例中增加一個(gè)罰值 3。從 3列 4行向該單元作垂直移動(dòng)，使第一序列增加堿基 T而第二序列引入一個(gè)空位，結(jié)果也得到一個(gè)罰值 3。因此從該單元 (5行 3列 )所得到的最小距離的延伸方向是沿對(duì)角線和水平方向。在表中這兩個(gè)方向用箭頭表示。這兩種最短方向都使從左上角到該單元的距離為 6。沿箭頭所指方向在表中從右下角向左上角追蹤，得到 6種可能的聯(lián)配： 在上述 6種聯(lián)配中，距離均為 10，即在較短序列中有 6個(gè)匹配堿基、 1個(gè)錯(cuò)配堿基和 3個(gè)空位 NeedlemanWunsch算法 當(dāng)兩個(gè)序列被聯(lián)配時(shí)，通過計(jì)算其重排序列(shuffed version)的聯(lián)配距離，可以得到這兩個(gè)序列間的最小距離估計(jì)。如果實(shí)際得到的聯(lián)配距離小于重排序列距離的 95%，則表明實(shí)際的聯(lián)配距離達(dá)到了 5%的顯著水平，是不可能由機(jī)誤造成的。 SmithWaterman算法 由于親緣關(guān)系較遠(yuǎn)的蛋白質(zhì)序列可能只有一些相互獨(dú)立的相同片段，所以進(jìn)行局部相似性分析有時(shí)可能比整體相似性分析更合理。 Smith和 Waterman描述了一種查找具有最高相似性片段的算法。對(duì)于序列 A=(a1,a2,…,am) 和 B=(b1,b2,…,bn) ， Hij被定義為以 ai和 bj 堿基對(duì)結(jié)束的片段 (亞序列 )的相似性值。 與 NeedleWunsch算法一樣， SmithWaterman算法也要利用遞推關(guān)系來確定 相似性計(jì)算中包括 2個(gè)統(tǒng)計(jì)量：堿基對(duì) (序列因子 ) 的相似性值和空位權(quán)重 (k 為空位長(zhǎng)度 )。 SmithWaterman算法可以給出 2條序列的最大相似性值。 SmithWaterman算法 相似性分?jǐn)?shù)矩陣 在對(duì)蛋白質(zhì)數(shù)據(jù)庫(kù)搜索時(shí) ， 可采用不同的相似性分?jǐn)?shù)矩陣 ， 以提高搜索的靈敏度和準(zhǔn)確率 。常用的相似性矩陣有突變數(shù)據(jù)矩陣 (Mutation Data Matrix ， 簡(jiǎn)稱 MD) 和 模 塊 替 換 矩 陣(BLOcks Substitution Matrix， 簡(jiǎn)稱 BLOSUM)。 在序列比對(duì)中 ， 通常希望使用能夠反映一個(gè)氨基酸發(fā)生改變的概率與兩個(gè)氨基酸隨機(jī)出現(xiàn)的概率的比值的矩陣 。 這些比值可以用相關(guān)幾率 （ relatedness odds） 矩陣表示 。 這就是突變數(shù)據(jù)相似性分?jǐn)?shù)矩陣產(chǎn)生的基礎(chǔ) ，在序列比對(duì)過程中 ， 兩個(gè)序列從頭到尾逐個(gè)殘基進(jìn)行比對(duì) ， 所得幾率值的乘積就是整個(gè)比對(duì)的分值 。 在實(shí)際使用時(shí) ， 通常取幾率值的對(duì)數(shù)以簡(jiǎn)化運(yùn)算 。 因此 ， 常用的突變數(shù)據(jù)矩陣 PAM250實(shí)際上是幾率值的對(duì)數(shù)矩陣 （ 圖 3） 。 矩陣中值大于 0的元素所對(duì)應(yīng)的兩個(gè)殘基之間發(fā)生突變的可能性較大 ， 值小于 0的元素所對(duì)應(yīng)的兩個(gè)殘基之間發(fā)生突變的可能性較小 圖 3 突變數(shù)據(jù)相似性分?jǐn)?shù)矩陣 PAM250 突變數(shù)據(jù)矩陣 PAM即可接受點(diǎn)突變 (Point Accepted Mutation， 簡(jiǎn)稱 PAM)。 1個(gè) PAM的進(jìn)化距離表示 100個(gè)殘基中發(fā)生一個(gè)殘基突變的概率 。 對(duì)應(yīng)于一個(gè)更大進(jìn)化距離間隔的突變概率矩陣 ， 可以通過對(duì)初始矩陣進(jìn)行適當(dāng)?shù)臄?shù)學(xué)處理得到 [Dayhoff等 ， 1978]， 如常用的 PAM250矩陣 ， PAM250相似性分?jǐn)?shù)矩陣相當(dāng)于在兩個(gè)序列之間具有 20%的殘基匹配 (圖 3)。 主對(duì)角線上分?jǐn)?shù)值是指兩個(gè)相同殘基之間的相似性分?jǐn)?shù)值，有些殘基的分值較高，如色氨酸 W為 1半胱氨酸 C為 12，說明它們比較保守，不易突變；有的殘基的分值較低，如絲氨酸 S、丙氨酸 A、門冬酰氨 N三種氨基酸均為 2，這些氨基酸則比較容易突變。不同氨基酸之間的分?jǐn)?shù)值越高，它們之間的相似性越高，進(jìn)化過程中容易發(fā)生互相突變，如苯丙氨酸 F和酪氨酸 Y，它們之間的相似性分?jǐn)?shù)值是 7。而相似性分?jǐn)?shù)值為負(fù)數(shù)的氨基酸之間的相似性則較低，如甘氨酸和色氨酸之間為 7，它們?cè)谶M(jìn)化過程中不易發(fā)生互相突變。此外，表中把理化性質(zhì)相似的氨基酸按組排列在一起，如堿性氨基酸組氨酸 H、精氨酸 R和賴氨酸 K。 突變數(shù)據(jù)矩陣的產(chǎn)生基于相似性較高 （ 通常為85%以上 ） 的序列比對(duì) ， 那些進(jìn)化距離較遠(yuǎn)的矩陣 （ 如 PAM250） 是從初始模型中推算出來而不是直接計(jì)算得到的 ， 其準(zhǔn)確率受到一定限制 。 而序列分析的關(guān)鍵是檢測(cè)進(jìn)化距離較遠(yuǎn)的序列之間是否具有同源性 ， 因此突變數(shù)據(jù)矩陣在實(shí)際使用時(shí)存在著一定的局限性 。 而模塊替換矩陣 BLOSUM則以序列片段為基礎(chǔ)，它是基于蛋白質(zhì)模塊數(shù)據(jù)庫(kù) BLOCKS，Henikoff夫婦（ Henikoff和 Henikoff， 1992）從蛋白質(zhì)模塊數(shù)據(jù)庫(kù) BLOCKS中找出一組替換矩陣，用于解決序列的遠(yuǎn)距離相關(guān)。在構(gòu)建矩陣過程中，通過設(shè)置最小相同殘基數(shù)百分比將序列片段整合在一起，以避免由于同一個(gè)殘基對(duì)被重復(fù)計(jì)數(shù)而引入的任何潛在的偏差。在每一片段中，計(jì)算出每個(gè)殘基位置的平均貢獻(xiàn)，使得整個(gè)片段可以有效地被看作為單一序列。 通過設(shè)置不同的百分比，產(chǎn)生了不同矩陣。由此，例如高于或等于 80%相同的序列組成的串可用于產(chǎn)生BLOSUM80矩陣（ BlOcks SUbstitution Matrix 發(fā)音為blossom）；那些有 62%或以上相同的串用于產(chǎn)生BLOSUM62矩陣，依此類推。 BLOSUM與 BLOCKS對(duì)于同樣的序列比對(duì)產(chǎn)生的結(jié)果在局部有所不同，可能是一個(gè)認(rèn)為不相似不可以替換而另一個(gè)認(rèn)為相似可以替換。必須說明，如果比對(duì)這兩個(gè)序列高度相似，這些細(xì)微的差別對(duì)整個(gè)序列比對(duì)結(jié)果的影響不