动态规画技巧简介DynamicProgrammingStillwatersrundeep.流静水深流静水深,人静心深人静心深Wherethereislife,thereishope。有生命必有希望。有生命必有希望The Heaviest Non-decreasing Subsequence Problem Let S be a sequence of integers. A heaviest non-decreasing subsequence of S is a non-decreasing subsequence with the maximum sum.(這是2000年全國大專軟體設計競賽大學甲組的試題)動態規畫技巧與序列分析費氏數(Fibonacci number)最長共同子序列兩個序列的分析多重序列分析費氏數(Fibonacci number)費氏數(Fibonacci number)How to compute 請問F10是多少？ F10F9F8F8F7F7F6列表式計算如果我們從F0、F1、往F10邁進，很快我們就可以算出F10F0F1F2F3F4F5F6F7F8F9F10011235813 21 34 55好漢做事好漢當上代數的時候，小明同學在後面.z.z.z.。 後來，老師發現了，就生氣地說： 旁邊的同學，把睡覺的叫起來！語畢， 不知道是哪個活得不耐煩的同學答道： 是你自己把他弄睡著的，你自己去把他叫醒 最長共同子序列動態規畫(dynamic programming)基本上，動態規畫技巧有三個主要部份：遞迴關係(recurrence relation)列表式運算(tabular computation)路徑迴溯(traceback)最長共同子序列(LCS, Longest Common Subsequence)問題首先我們先解釋什麼是子序列(subsequence) ，所謂子序列就是將一個序列中的一些(可能是零個)字元去掉所得到的序列，例如：pred、sdn、predent等都是 ”president” 的子序列。給定兩序列，最長共同子序列(LCS)問題是決定一個子序列，使得 (1) 該子序列是這兩序列的子序列；(2) 它的長度是最長的。LCS例如： 序列一：president 序列二：providence它的一個LCS為LCS例如： 序列一：president 序列二：providence它的一個LCS為 priden ( PResIDENt PRovIDENce )LCS又例如： 序列一：algorithm 序列二：alignment它的一個LCS為LCS又例如： 序列一：algorithm 序列二：alignment它的一個LCS為 algm or algt ( ALGorithM ALiGnMent )How to compute LCS?給定兩序列及，令len(i, j)表示與的LCS之長度，則下列遞迴關係可用來計算len(i, j)：極樂世界老師： 小明，你的毛病就是用詞不當，現在考考你 。用一句成語來形容老師很開心，而且成語中要包含數字。小明： 極樂世界老師： 小明，你的毛病就是用詞不當，現在考考你 。用一句成語來形容老師很開心，而且成語中要包含數字。小明：含笑九泉兩個序列的分析兩個序列的分析在1970年代，分子生物學家Needleman 及Wunsch 15以動態程式設計技巧(dynamic programming)分析了氨基酸序列的相似程度；有趣的是，在同一時期，計算機科學家Wagner及Fisher 22也以極相似的方式來計算兩序列間的編輯距離(edit distance)，而這兩個重要創作當初是在互不知情下獨立完成的。雖然分子生物學家看的是兩序列的相似程度，而計算機科學家看的是兩序列的差異，但這兩個問題已被證明是對偶問題(dual problem)，它們的值是可藉由公式相互轉換的。三種常用的序列分析方法 目前序列分析工具可說是五花八門 ，僅管如此，有三種構想是較受大家所青睬的：第一種是Smith-Waterman的方法，這種方法很精細地計算兩序列間最好的k 個區域排比(local alignment)，雖然這個方法很精確，但因耗時較久，所以多半應用在較短序列間的比較，然而，也有一些學者試著去改善它的一些計算複雜度，使它在長序列的比較上也有一些實際的應用。三種常用的序列分析方法(續)第二種是Pearson的FASTA方法，這種方法先以較快方式找到一些有趣的區域，然後再以Smith-Waterman的方法應用在那些區域中。如此一來，它的計算速度就比Smith-Waterman快，而且在很多情況下，它的精細程度也不差。第三種是Altschul等人所製作的BLAST ，它的最初版本完全沒有考慮間隔(gap)，所以在計算上比其他方式快了許多。雖然它不夠經細，但它的計算速度使得它在生物序列資料庫的搜尋上有很大的優勢，也因此它可說是目前最受歡迎的序列分析工具。此外，1997年剛出爐的Gapped BLAST已針對精細程度做了很大的改進，且在計算速度上仍維持相當的優勢。為什麼要用排比(alignment)？早期的序列分析通常是以點矩陣(dot matrix)方法來進行的，這種方法是以二維平面將兩序列間相同的地方點出來，從而藉由目視的方式看看兩序列有那些相似的地方。這種方法最大的優點是一目了然且計算簡單；然而，當序列較長的時候，藉由目視方法去分析它們是一種很沒有效率的方式況且有些生物序列(如蛋白質序列)並不是只有相同字符才相似，這時候點矩陣方法就無法看出整體的相似程度。於是有人建議以排比(alignment)來顯示兩序列的相似程度排比(alignment)給定兩序列，它們的整體排比(global alignment)是在兩序列內加入破折號(dash)，使得兩序列變得等長且相對的位置不會同時都是破折號。例如：假設兩序列為及，下圖列出了它們的一種排比。圖圖: 及的一種可能排比。排比的評分方式有那麼多種不同的排比組合，到底要挑那一個排比呢？為了要挑出較理想的排比，通常我們需要一些評分方式來做篩選工作。最簡單的評分方式是將每一個配對基底(aligned pair)都給一個分數，再看看那一種排比的總分最高。令w(a,b)代表a與b配對所得到的分數(通常w(*,-)及w(-,*)是負值；mismatch也是負值；只有match是正值，而蛋白質序列分析則採用PAM矩陣或BLOSUM矩陣來決定這些值)在上述的簡單評分原則下，前圖的排比所得到的分數為w(C,C) + w(T,T) + w(T,-) + w(A,A)最佳排比演算法 同盟線性評分法(affine gap penalties)我們可以用動態規畫技巧由小到大依序將S(i, j)算出，並且記錄最佳值的由來，如此一來，在計算完了之後，我們也能一舉將最佳排比回溯出來。 在比較生物序列時，我們通常會對每個破折號區域另外扣一個懲罰分數(令其為)，破折號區域也就是我們常說的間隔(gap)，如果破折號發生在第一個序列我們稱之為插入間隔(insertion gap)；如果發生在第二個序列我們稱之為刪除間隔(deletion gap)。例如在前圖的排比中，我們有一個長度為2 的刪除間隔及一個長度為1 的插入間隔，所以在排比分數上還要扣去兩個間隔的分數(2)。我們通常稱這樣的評分方式為同盟線性評分法(affine gap penalties)最佳排比演算法 最佳排比演算法(續) 遞迴關係的白話解說雖然上面的遞迴關係有些複雜，但在計算上也是很直截了當的。我們利用矩陣D 來記錄以刪除間隔結束的最佳分數，如果緊接著又是刪除動作時，我們就不必再扣懲罰分數了；同樣地，我們利用矩陣I 來記錄以插入間隔結束的最佳分數，如果緊接著又是插入動作時，我們就不必再扣懲罰分數了。我們可以用動態規畫技巧由小到大依序將D(i, j)、I(i, j)及S(i, j)算出，並且記錄最佳值的由來，如此一來，在計算完了之後，我們也能一舉將最佳排比回溯出來。區域排比(local alignment)在做生物序列排比時，有時更有趣的是找出局部區域的相似程度，此時我們考慮的是所謂的區域排比(local alignment)，也就是我們不必從頭到尾排比整個序列，而只要找出序列一的某個區段和序列二的某個區段之最佳排比即可。我們在此以最簡單的評分方式(也就是以每一個配對基底(aligned pair)分數的總和為排比分數)來說明如何計算最佳區域排比。最佳區域排比的演算法 為什麼要加個0？和整體排比(global alignment)的遞迴關係相比較，你會發現這裡的遞迴關係只多了0 這一項，原因是整體排比要從序列前端開始排起，而區域排比卻是任一個地方都可能是個起點，如果往前連接分數小於0 ，我們就不該往前串聯，而以此點做為一個起點(S(i, j)=0 )試試看。多個最佳區域排比有些人感興趣的是找出k 個最好的區域排比或是分數至少有設定值那麼高的所有區域排比，這樣的計算在你熟悉動態規畫技巧後應不至於難倒你的。上述的方式也就是一般俗稱的Smith-Waterman方法 (實際上，整體排比問題是由Needleman及Wunsch15所提出；而區域排比問題則是由Smith及Waterman21所提出)，它基本上需要與兩序列長度乘積成常數正比的時間與空間。在序列很長時，這種計算時間及空間都是很難令人接受的！FASTA 在分析兩個序列時，Smith-Waterman的方法也許勉強可以接受，但如果以它做為資料庫搜尋的引擎，那就有些龜速了，因為這將會耗費不少寶貴的時光。FASTA(唸成”fast-AY”，而不是”FAST-uh”)及BLAST(Basic Local Alignment Search Tool，唸成BLAST)就這樣應運而生了。這兩種方法都設法不去計算動態規畫設計表(dynamic programming table)的每一點，而是以近似方法(heuristic mathod)來做排比，因此在計算速度上勝過Smith-Waterman方法很多，非常適合做資料庫搜尋。FASTA(續)首先，讓我們約略地看一下FASTA這個方法，這個方法讓使用者選定參數ktup (k-tuple，在DNA序列分析時這個值通常設成 6 到 8 ；蛋白質序列則常使用 1 到 2 的值)，FASTA只考慮那些長度至少為 ktup 的那些相似子序列，試著藉由它們找出一些可能有相似性的對角區域(diagonal band)，然後再將Smith-Waterman的方法套用在這些小區域上。在BLAST橫掃千軍前，FASTA曾是最常被用來分析序列的工具。在FASTA中，因為它試著去串聯那些 ktup序列，所以耗費了不少時間。BLAST初版的BLAST則以長度至少為 w 的相似區段著眼，只往對角線(diagonal)方向試著去延伸，直到分數的降低程度超過使用者所給定的範圍為止，因為它完全不考慮間隔(gap)，所以非常地有效率，但缺點是有時不夠敏銳(sensitive)。不過在第二版的BLAST中，已針對這樣的缺點加以修正，它在延伸對角線時採用的策略是跳著延伸(註：延伸對角線耗去了大部份初版BLAST執行的時間)，這個立論基礎是如果它真是分數很高的相似區段，跳著延伸也不會錯過。BLAST(續)利用延伸對角線所省下的時間，新的BLAST也試著去考慮串聯一些分數高的相似區段，也就是說某些有間隔的排比在新的BLAST中也可被發現。新版的BLAST已幾乎取代初版的BLAST。龜兔賽跑阿強上課總是打瞌睡， 老師忍無可忍地把昏睡中的阿強叫醒，並問他 龜兔賽跑中，你知道兔子為什麼會輸嗎？ 不知道阿強睡眼惺忪地回答。 因為兔子在打瞌睡老師生氣的說. 喔！我明白了阿強若有所悟 原來沒打瞌睡的全是烏龜啊！ 多重序列分析多重序列排比多序列的分析一直是計算生物學上很重要的課題，但是它的問題複雜度卻令人沮喪。粗略地說，比較兩個長度皆為n的序列所需的時間(也就是動態規畫矩陣點)是和n的平方成常數正比的；而比較k個長度皆為n的序列所需的時間則和n的k次方成常數正比。試想如果我們要同時比較10個長度只有200的序列所需的時間是多少呢？它基本上會和200的10次方成常數正比，而這卻是很龐大的數目。多重序列排比的計算方法因此，在計算方法上有兩種不同的流派：一種是Lipman等人提出的方式，他們做的是同時比較多個序列，但試著去降低計算時所用的動態規畫矩陣點，據他們的論文指出，這種方式比較10個長度為200的序列也不會遭遇太大的問題；另一種方式是Feng及Doolittle所採用的，它根據序列遠近程度的演化樹來做序列排比，一旦gap在某個比較中出現後，它就會被保留到最後，這種方法用來比較k個長度皆為n的序列所需時間約略與成常數正比，所以非常廣受歡迎。多重序列排比的評分方式最廣為接受的一種方式稱為SP (Sum-of Pairs)分數，這種方式將多重序列排比投影到每一對序列上所得的排比分數總和起來，做為該多重排比的分數。這種方式若要直接採用同盟線性評分方式，則會滋生非常多的動態規畫設計表，但若稍稍放鬆一下，類似同盟線性評分方式(quasi affine gap penalties)雖然不夠精準，但卻可較有效率地計算多重排比的分數，是最常被用到的變形評分方式。此外，有些人建議某些序列組合應加權計分；也有人根據演化樹來計算分數都是老師惹的禍在經過了數天的苦讀熬夜，甚至通宵之後，三個學生總算通過了期末考，考完當天：甲生說：這樣熬下來，我看起來真是憔悴，你們看看我的臉，彷彿老了十年呢. 乙生說：你那樣還好，我看起來才糟呢，我看起來像只剩十年可活了.嗚 丙生嘆了一口氣說唉我看起來像是已經死了十年了