第三章 序列比對

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

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

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

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

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

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

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

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

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

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