在利用動(dòng)態(tài)規(guī)劃（DP）進(jìn)行全局比對(duì)（一）中淺顯的探討了動(dòng)態(tài)規(guī)劃的中心思想以及如何使用動(dòng)態(tài)規(guī)劃方法來(lái)解決問題。在本文將簡(jiǎn)要的介紹早期生物信息學(xué)中是如何利用動(dòng)態(tài)規(guī)劃方法來(lái)進(jìn)行序列比對(duì)的。
在探討動(dòng)態(tài)規(guī)劃實(shí)現(xiàn)的比對(duì)算法之前，我們還是需要先了解下序列比對(duì)的一些基本信息：
- 兩個(gè)堿基的比對(duì)方式有三種：
A A -
G - G
即兩個(gè)堿基比對(duì)上了（兩個(gè)堿基不一定完全相同），兩個(gè)堿基中的一個(gè)比對(duì)上了一個(gè)空位
- 為方便計(jì)算，這里的空位罰分一律記為-5分，extending_gap也同樣的記為-5分。
- 這里的替換矩陣使用更加簡(jiǎn)單的核酸替換矩陣。
-
比對(duì)序列也使用兩條簡(jiǎn)單序列AAG和AGC。
核酸替換矩陣
接下來(lái)我們將開始使用動(dòng)態(tài)規(guī)劃方法進(jìn)行序列比對(duì)。
1、第一步，畫格子
在使用動(dòng)態(tài)規(guī)劃方法時(shí)，第一步依舊是畫格子。
比對(duì)矩陣
需要聲明的是第二行和第二列空著的位置表示gap。
2、填網(wǎng)格
第一個(gè)網(wǎng)格位置的值表示gap對(duì)上gap（無(wú)意義），得分為零。
每個(gè)位置的積分公式.png
從上面的公式可以看出，網(wǎng)格中每個(gè)位置的得分都等于等號(hào)右邊3個(gè)式子中的最大值。（Xi aligned to Yi）表示此位置的兩個(gè)堿基正好對(duì)上，其替換得分（s(xi, yi)）由替換打分矩陣可查得。若為下面兩個(gè)式子則表示堿基對(duì)上一個(gè)空位（gap），因此其值等于空位罰分+左側(cè)(xi aligned to a gap)或上方值 (xi aligned to a gap)。
第一行或者第一列表示所有堿基都比對(duì)上了空位，得分總分為-5*3=-15。
image.png
最后得到的打分矩陣如下：
image.png
3、比對(duì)結(jié)果
image.png
由于在-3得分有兩個(gè)來(lái)源，因此有兩種比對(duì)結(jié)果，這兩種比對(duì)結(jié)果的得分都為-6。
參考：北京大學(xué)公開課——生物信息學(xué): 導(dǎo)論與方法
