第三章 序列比對(duì)

1、1第三章第三章序列比對(duì)序列比對(duì)1序列比對(duì)的概念序列比對(duì)的概念序列比對(duì)的定義是：根據(jù)特定的計(jì)分規(guī)則，兩個(gè)或多個(gè)符號(hào)序列按位置比較后排列，盡可能反映序列間的相似性，這一過程稱為序列比對(duì)。2序列比對(duì)的意義序列比對(duì)的意義生物信息學(xué)形成早期的主要研究內(nèi)容就是序列比對(duì)，而當(dāng)時(shí)序列比對(duì)研究的課題主要是生物大分子的進(jìn)化。核酸序列與蛋白質(zhì)序列的突變是經(jīng)實(shí)驗(yàn)證明的生物學(xué)現(xiàn)象，而現(xiàn)代生物學(xué)認(rèn)為正是這種生物大分子序列的不斷變化形成了生物進(jìn)化的分子基礎(chǔ)。即在地質(zhì)

2、年代早期的地球生物中的核酸、蛋白質(zhì)等序列經(jīng)過幾十億年的演變后，成為了現(xiàn)今極其多樣化的生物大分子序列。我們并不知道這些分子序列祖先演化的實(shí)際過程，但可以找到現(xiàn)存序列的相似性，根據(jù)相似性去推導(dǎo)演化的過程。正是通過序列比對(duì)找出序列之間的相似性。序列比對(duì)找到的是相似性，可用這相似性去進(jìn)行同源性分析。后文所講到的分子系統(tǒng)發(fā)育分析，就是通過序列比對(duì)，再進(jìn)行聚類分析，然后依據(jù)所得結(jié)果確定被測(cè)分子序列的親緣關(guān)系，構(gòu)建進(jìn)化樹。序列比對(duì)的一個(gè)用途就是用于搜

3、索相似序列。當(dāng)你獲得一段DNA序列或氨基酸序列后，發(fā)現(xiàn)對(duì)它一無所知時(shí)，可以在核酸序列數(shù)據(jù)庫中搜索關(guān)于這一序列的信息，一個(gè)有效的方法是采用比對(duì)算法在數(shù)據(jù)庫中找到一系列與該序列有相似性的序列，并按相似程度由高到低排列?，F(xiàn)在應(yīng)用的多個(gè)序列搜索軟件的本質(zhì)差異基本上是比對(duì)算法的差異，隨著數(shù)據(jù)庫規(guī)模的擴(kuò)大，對(duì)快速搜索的要求越來越高，而優(yōu)化比對(duì)算法是解決問題的方案之一。在基因組測(cè)序中，序列比對(duì)更是有重要作用?；蚪M測(cè)序一般要將若干個(gè)拷貝的長核酸序列打

4、斷成有重疊區(qū)域的許多小片斷，測(cè)序儀對(duì)小片斷進(jìn)行測(cè)序，然后把已知堿基排列順序的小片斷用比對(duì)算法找到有重疊區(qū)的另外的片斷，把它們邊接起來還原成原來的長核酸序列，得到長核酸序列的堿基排列順序。序列比對(duì)還可以尋找序列中的特定位點(diǎn)。當(dāng)一個(gè)基因的某一位點(diǎn)發(fā)生突變時(shí)，它與原基因進(jìn)行比對(duì)時(shí)就能發(fā)現(xiàn)這個(gè)位點(diǎn)，這在尋找致病基因時(shí)尤為重要。同時(shí)，通過比對(duì)，可找出不同序列間一些保守性的區(qū)域，它們可能行使重要的功能。經(jīng)常會(huì)用比對(duì)確認(rèn)氨基酸序列的保守區(qū)以了解該區(qū)的

5、特定結(jié)構(gòu)與功能。在進(jìn)行蛋白質(zhì)結(jié)構(gòu)預(yù)測(cè)、基因預(yù)測(cè)時(shí)，比對(duì)也是一種基本的研究手段之一。蛋白質(zhì)結(jié)構(gòu)預(yù)測(cè)中，大部分的成果都是來自序列比對(duì)，研究的模式主要是有若干已知結(jié)構(gòu)及氨基酸順序的序列，把待測(cè)的序列與已知結(jié)構(gòu)的序列進(jìn)行比對(duì)，通過相似性去預(yù)測(cè)待測(cè)序列局部或全部的結(jié)構(gòu)。而在蛋白質(zhì)的分類中，有的方法就是利用比對(duì)獲得氨基酸序列的相似性，以此相似性為基礎(chǔ)進(jìn)行分類。在基因預(yù)測(cè)中常要在待測(cè)序列中搜尋起始密碼子、結(jié)束密碼子、多聚A帽子序列等特自位點(diǎn)以增加預(yù)測(cè)

6、的命中率。3全局比對(duì)與局部比對(duì)全局比對(duì)與局部比對(duì)根據(jù)對(duì)比對(duì)后要排列的片斷范圍可將比對(duì)分為全局比對(duì)與局部比對(duì)。3列比對(duì)都采用這種方法，其中當(dāng)兩字母相同時(shí)取1分，兩字母不同時(shí)取1分，空格對(duì)字母時(shí)每個(gè)空格計(jì)2分。匹配計(jì)分的優(yōu)點(diǎn)是簡單易掌握，缺點(diǎn)是沒有考慮不匹配時(shí)的相似性質(zhì)。5比對(duì)的算法過程比對(duì)的算法過程有不少的序列比對(duì)算法已出現(xiàn)在文獻(xiàn)及應(yīng)用軟件中，其中一些得到廣泛的應(yīng)用，如動(dòng)態(tài)規(guī)劃法、累進(jìn)方法等。兩序列比對(duì)與多序列比對(duì)的算法有差異，所以一般是

7、分開介紹。兩序列比對(duì)的經(jīng)典方法是動(dòng)態(tài)規(guī)劃法，點(diǎn)陣法也用得較多，我國學(xué)者沈世鎰等創(chuàng)造了統(tǒng)計(jì)判決算法。多序列比對(duì)的常用方法是累進(jìn)方法、隱馬爾可夫模型、動(dòng)態(tài)規(guī)劃法等，也有些算法相對(duì)簡單，如星比對(duì)方法。5.1兩個(gè)序列比對(duì)全局比對(duì)動(dòng)態(tài)規(guī)劃法是Needle與Wunsch在1970年提出，一直沿用至今，這個(gè)算法是生物信息學(xué)的基礎(chǔ)算法之一。動(dòng)態(tài)規(guī)劃算法是把一個(gè)大問題分成多級(jí)的小問題，逐級(jí)求每個(gè)小問題的最優(yōu)答案，各級(jí)問題的最優(yōu)答案加起來就是這個(gè)大問題的最

8、優(yōu)答案。如果不加限制空格的加入，任兩個(gè)序列的比對(duì)結(jié)果都會(huì)有無限多個(gè)，因?yàn)橹灰尤氩煌目崭駭?shù)目就行了。因此首先規(guī)定空格對(duì)空格無效。動(dòng)態(tài)規(guī)劃算法將比對(duì)全過程分為若干步，每一步增加一個(gè)位置。因?yàn)榭崭駥?duì)空格無效，所以增加一個(gè)位置時(shí)有三種情況：第一個(gè)序列增加一個(gè)字母而第二個(gè)序列增加一個(gè)空格；第一個(gè)序列增加一個(gè)空格而第二個(gè)序列增加一個(gè)字母；兩個(gè)序列都增加一個(gè)字母。這樣要進(jìn)行n步的話就可能有3n種可能。動(dòng)態(tài)規(guī)劃算法的巧妙之處是把第一序列已比對(duì)字母且

9、第二序列已比對(duì)字母都相同的各種比對(duì)結(jié)果放在一起進(jìn)行判斷，只留最優(yōu)結(jié)果。例如對(duì)序列g(shù)c與at進(jìn)行比對(duì)，其中中間過程中的三個(gè)結(jié)果（都是第一序列的g已比對(duì)且第二序列的a已比對(duì)）：g–ggaaa是放在一起的，并且被判斷，只留出最優(yōu)結(jié)果（即舍去了第1與第2個(gè)比對(duì)結(jié)果）。用這種篩選方面一直進(jìn)行下去，直到所有的字母都進(jìn)行過比對(duì)為止。最后所得的最優(yōu)解就是動(dòng)態(tài)規(guī)劃算法的最后結(jié)果。因此，用動(dòng)態(tài)規(guī)劃算法進(jìn)行兩序列比對(duì)的過程可用矩陣顯示，矩陣中的每一元素可表示

10、第一序列已比對(duì)字母且第二序列已比對(duì)字母相同的各種比對(duì)結(jié)果的最優(yōu)者，最后的一格（即右下格）的最優(yōu)結(jié)果就是整個(gè)比對(duì)的最優(yōu)結(jié)果。在具體算的過程中，每一格只用最優(yōu)比對(duì)的得分來表示。矩陣的計(jì)算過程可表示如下：對(duì)于序列I，序列J，如果采用特定的計(jì)分規(guī)則（字母相同1分；字母不同1分；字母對(duì)空格2分），除左上第一格外，每一格均有：Mi1j2（表示縱向增加一個(gè)位置是字母對(duì)空格，因此減2分）Mij=maxMi1j1S(ij)（表示斜向增加一個(gè)位置是字母對(duì)字