兩序列比對算法

兩序列比對算法摘要：序列比對是生物信息學(xué)討論的一個基本方法，對于發(fā)覺生物序列中的功能、結(jié)構(gòu)和進(jìn)化信息具有重要的意義。兩序列比對中，典型的全局比對算法是Needleman一Wunsch算法;局部比對算法的基礎(chǔ)是Smitll—Waterman算法，本文對典型的雙序列比對算法進(jìn)行描述。關(guān)鍵詞：生物信息學(xué)；兩序列比對；算法引言：為了滿意基因組中獲得更多更有價值的信息，生物信息學(xué)快速進(jìn)展起來，生物信息學(xué)是一門多門科學(xué)交叉的學(xué)科，將數(shù)學(xué)、計算機科學(xué)應(yīng)用于生物大分子信息的獵取、加工、存儲、分類、檢索和分析等，以達(dá)到闡明和理解大量數(shù)據(jù)所蘊含的生物學(xué)意義的目的。通過對DNA和蛋白質(zhì)序列進(jìn)行相像性比較，指明序列間的保守區(qū)域和不同之處，為進(jìn)一步討論它們在結(jié)構(gòu)、功能以及進(jìn)化上的聯(lián)系供應(yīng)了重要的參考依據(jù)。而序列比對就是運用某種特定的數(shù)學(xué)模型或算法，找出兩個或多個序列之間的最大匹配堿基或殘基數(shù)，比對的結(jié)果反映了算法在多大程度上反映了序列之間的相像性關(guān)系以及它們的生物學(xué)特征。雙序列比對算法雙序列比對分為全局比對和局部比對，全局比對是考察兩個序列之間的全局相像性，局部比對貝此較序列片段之間的相像性。Needleman—Wunsch算法是典型的全局比對算法，適用于全局水平上相像性程度較高的兩個序列；Smitll—Waterman算法適用于查找局部相像序列對，該算法是目前被使用最廣泛的序列相像性比較算法之一，由所熟識的Needleman—Wunsch算法演化而來。Needleman-Wunsch算法使用迭代方法計算出兩個序列的相像分值，存于一個得分矩陣中，然后依據(jù)這個得分矩陣，通過動態(tài)規(guī)劃的方法回溯查找最優(yōu)的比對序列。具有很高的靈敏度使用二維表格，一個序列沿頂部綻開，一個序列沿左側(cè)綻開。而且也能通過以下三個途徑到達(dá)每個單元格：1.來自上面的單元格，代表將左側(cè)的字符與空格比對。2.來自左側(cè)的單元格，代表將上面的字符與空格比對。3.來自左上側(cè)的單元格，代表與左側(cè)和上面的字符比對(可能匹配也可能不匹配\該單元格的值來自于一下3個中的最大值:(1)上方的值-2(2)左邊的值-2(3)假如該單元格所在的行于所在的列對應(yīng)的字符相等，則為左上值加1,否則為左上值-1。SmitH—Waterman算法Smitll—Waterman算法主要分兩步，計算得分矩陣和查找最佳相像片段對。對于兩個序列S和T,令/S/和/t/分別為序列S和T的長度，S[i]和T[j](其中正整數(shù)ij滿意0<3/S/,0<j小于等于/T/)都屬于某個字符集。，對。中的任何元素和空符號，他們兩兩之間都有一個記分值，用記分函數(shù)6(x,y)表示。F(i,j)表示序列S的前綴S⑴S[2]……S[i-l]S[i]和序列T[1]T[2]……T[j-l]T[j]"的前綴之間的最佳相像性比較的得分。那么就有以下公式：Ff,；)=max{F￡-1,；-1)+(r6|/|,7]/|),F￡-1,j)+(r3j),F￡,；-!)+(r(,-),())其中：/0,())=F￡,())=F0,y)=0(iMi|,7]/|)=2,當(dāng)S|i|=7l/|(r6]小71/|)二一1,當(dāng)5“，71/|(r(",,)=(『￡,一)二2通過公式，可得到得分矩陣，得到得分矩陣以后，用動態(tài)規(guī)劃回溯的方法找到局部最大相像片段對。先找到得分矩陣中最大的元素，然后依據(jù)該元素原計算路徑一步一步往前回溯，直到回溯到"時停止。從得到的回溯路徑可以得到其正向路徑，就是兩序列的最佳相像片段對。到目前為止，兩序列比對問題已基本解決，標(biāo)準(zhǔn)方法是采納可以保證得到一個數(shù)學(xué)優(yōu)化的比對結(jié)果的動態(tài)規(guī)劃比對算法。兩序列的動態(tài)規(guī)劃比對算法是多序列比對的重要理論基礎(chǔ)。兩序列比對的一個主要目的是進(jìn)行數(shù)據(jù)庫相像性搜尋，F(xiàn)ASTA和BLAST是最常用的數(shù)據(jù)庫搜尋程序，均采納局域比對方法。FASTA:第一個廣泛使用的數(shù)據(jù)庫相像性搜尋程序，其基本思想是：一個能夠揭示出真實的序列關(guān)系的比對至少包含一個兩個序列都擁有的字（由連續(xù)字符組成的子序列），把查詢序列中的全部字編成索引，然后在數(shù)據(jù)庫中查詢這些索引字。FASTA程序并不討論每一個選中的字，而是查找包含若干個相鄰的選中片段，將這些片段組合起來予以評價；然后，那些最有可能的匹配序列將會通過局域比對而被進(jìn)一步評分，并對每一個檢索到的比對供應(yīng)一個統(tǒng)計學(xué)顯著性的評估。算法過程簡潔描述為：1依據(jù)點陣圖規(guī)律，從比對的全部結(jié)構(gòu)中計算出最佳的對角線。2使用字符方法查找查詢字符和測試序列之間的精確匹配。3當(dāng)全部的對角線發(fā)覺之后，通過增加空位來連接對角線。4在最佳對角線區(qū)域中計算出比對結(jié)果。BLAST:是目前使用最廣泛的數(shù)據(jù)庫搜尋算法，其基本思想是：通過產(chǎn)生數(shù)量較少，但質(zhì)量更好的匹配片段來提高搜尋速度，并把數(shù)據(jù)庫搜尋建立在嚴(yán)格的統(tǒng)計學(xué)基礎(chǔ)之上。其算法描述如下：首先是在數(shù)據(jù)庫中找出與查詢序列相同的匹配字串(hit),且這一局部字串中不含空位；一個匹配字串選中后，以此作為內(nèi)核向兩端延長，以找出盡可能長的相像序列片段，也即高分片段對HSP(highsequencepairs);設(shè)定一個統(tǒng)計顯著性閥值E，統(tǒng)計顯著性大于E的HSP將被舍棄，剩下的HSP即為高質(zhì)量的匹配片段對，由此在數(shù)據(jù)庫中搜尋出具有肯定可信度的同源序列。算法過程簡潔描述如下：1先將多個序列兩兩比對構(gòu)建距離矩陣，反映序列之間兩兩關(guān)系；2然后依據(jù)距離矩陣計算產(chǎn)生系統(tǒng)進(jìn)化指導(dǎo)樹,3對關(guān)系親密的序列進(jìn)行加權(quán)；然后從最緊密的兩條序列開頭，逐步引入接近的序列并不斷重新構(gòu)建比對，直到全部序列都被加入為止?，F(xiàn)狀與前景展望：序列比對是生物信息學(xué)的一個基礎(chǔ)而又重要的問題，也是生物信息學(xué)中的一大難題。雖然人們已提出大量的比對方法，但是對于分歧較大的序列，比對的精確率以及算法的時間簡單度都有待于提高。目前，序列比對中存在的主要問題在于：如何給出一個合理的優(yōu)化的相像性度量準(zhǔn)則以及如何提高分歧多序列比對的精確率。序列比對問題將來的進(jìn)展方向是基因組比較。參考文獻(xiàn)lWison.Ondistributionofthepotentialdiferencesproduetedbytheheartbeatwithinthebodyandatitssurface[J].Ain.HeartJ,1930;5(3):599-6022MaizelJV,FitchWM.Testingehtcovalonhypothesisofwvolution[J].Mol.Biol.Evol.1995(12):503—513.3TKAttwod,DJParry-Smith著.羅靜初等譯.生物信息學(xué)概論【M].北京：北京高校出版社，2ool:141-1454蔣文蓉，王少華，趙文耘.計算機幫助考試系統(tǒng)數(shù)據(jù)結(jié)構(gòu)的開發(fā)f