生物序列比對(duì)算法綜述

1、word生物序列比對(duì)算法綜述【摘 要】 隨著生物信息學(xué)的快速開展，序列比對(duì)算法成為研究的熱點(diǎn)問(wèn)題。本文介紹序列比對(duì)算法的概念及研究，并針對(duì)幾種常用的序列比對(duì)算法進(jìn)行比擬。同時(shí)也簡(jiǎn)單說(shuō)明序列比對(duì)算法的改良方向?！娟P(guān)鍵詞】 生物信息學(xué) 序列比對(duì) 準(zhǔn)確率 時(shí)空效率隨著生命科學(xué)研究的興起和計(jì)算機(jī)技術(shù)的飛速開展，生物信息學(xué)已成為自然科學(xué)的核心領(lǐng)域之一1。基因序列比對(duì)是生物信息處理的最根本方法，對(duì)發(fā)現(xiàn)基因功能、比擬基因、探究生物進(jìn)化等具有非常重要的作用。1 序列比對(duì)算法概述所謂序列比對(duì)2，是指兩個(gè)或多個(gè)序列按字母比擬，盡可能確切地反映它們之間的相似和相異性，用于說(shuō)明序列之間的同源關(guān)系。通過(guò)序列比對(duì)，找出序

2、列之間的相似性，發(fā)現(xiàn)與結(jié)構(gòu)相聯(lián)系的保守序列片段，以及檢測(cè)新測(cè)定序列與數(shù)據(jù)庫(kù)中結(jié)構(gòu)和功能的序列之間的相似性關(guān)系，從而以足夠的可信度確定新序列的結(jié)構(gòu)和功能信息。目前的序列比對(duì)方法很多。本文主要針對(duì)常用的算法，按照比對(duì)的序列數(shù)目進(jìn)行相關(guān)介紹：1.1 雙序列比對(duì)根據(jù)算法結(jié)構(gòu)的不同，將雙序列比對(duì)算法分為三類3：動(dòng)態(tài)規(guī)劃的優(yōu)化方法，啟發(fā)式算法和大型數(shù)據(jù)庫(kù)搜索設(shè)計(jì)的概率方法。1.1.1 動(dòng)態(tài)規(guī)劃的優(yōu)化算法Needleman-Wunsch算法是最早的序列比對(duì)算法，屬于全局序列比對(duì)，在生物信息處理中應(yīng)用廣泛。Smith-Waterman算法是一種局部相似性的動(dòng)態(tài)規(guī)劃算法，在識(shí)別局部相似性時(shí)具有很高的靈敏度，是雙

3、序列比對(duì)算法中最根本的算法。1.1.2 啟發(fā)式算法1FASTA算法FASTA是雙序列比對(duì)啟發(fā)式算法，采用了改良的wilbllr和Lipmall算法以集中反映具有顯著意義的比對(duì)結(jié)果。它的根本思想是：一個(gè)能揭示出真實(shí)序列關(guān)系的比對(duì)至少包含一個(gè)兩條序列都擁有的片段，把查詢序列中的所有片段編成Hash表，然后在數(shù)據(jù)庫(kù)搜索時(shí)查詢這個(gè)Hash表，以檢索出可能的匹配，這樣命中的片段就能很快地被鑒定出來(lái)。2BLAST算法BLAST算法可以兼顧搜尋的速度以及搜尋結(jié)果的精確度，它比FASTA速度更快。它的根本思想是：產(chǎn)生比FASTA更少而更有意義的增強(qiáng)點(diǎn)，以提高整個(gè)算法的速度。BLAST算法在不失敏感性的前提下大

4、大提高了算法的效率。3BLAT算法Blat算法最初用于人類基因組拼接和注釋過(guò)程中的大規(guī)模數(shù)據(jù)比對(duì)任務(wù)上。其速度快、共線性輸出結(jié)果簡(jiǎn)單易讀，存在的局限性是對(duì)于特殊的任務(wù)需要選擇適宜的軟件，如：用于遠(yuǎn)親緣物種間的核酸序列比對(duì)時(shí)，比對(duì)精度就不夠高；在重復(fù)搜索短小匹配片段的同時(shí)，會(huì)產(chǎn)生過(guò)多的沒(méi)有生物學(xué)意義的序列比對(duì)碎片。1.1.3 大型數(shù)據(jù)庫(kù)搜索設(shè)計(jì)的概率方法為根底的算法MUMmer算法是一種基于后綴樹數(shù)據(jù)結(jié)構(gòu)的全基因組比對(duì)方法，利用后綴樹的數(shù)據(jù)結(jié)構(gòu)有效地將算法的時(shí)間和空間復(fù)雜度由N 3降到了N。與BLAST算法相比，其后綴樹法在速度上快得多，且能處理大量的插入和刪除片段，能識(shí)別重復(fù)片段和單核酸多態(tài)性

5、等多種全基因組序列中的復(fù)雜片段。1.2 多序列比對(duì)多序列比對(duì)的常用算法有累進(jìn)算法、隱馬爾科夫模型、迭代比對(duì)法等。累進(jìn)方法是最常用的啟發(fā)式多序列比對(duì)算法。其中的CLUSTAL算法是由Feng和Doolittle提出的，基于相似序列通常具有進(jìn)化相關(guān)性這一假設(shè)的算法，它是多序列比對(duì)算法中使用最廣泛的。隱馬爾科夫模型是目前較先進(jìn)的多序列比對(duì)方法，跟常規(guī)的方法相比，它可以發(fā)現(xiàn)序列久遠(yuǎn)的同源性。迭代方法也基于一個(gè)能產(chǎn)生比對(duì)的算法，并通過(guò)迭代方式精細(xì)多序列比對(duì)，直到比對(duì)結(jié)果不再改良為止。這類算法不能提供獲得優(yōu)化比對(duì)結(jié)果的保證，但卻具有魯棒性和對(duì)序列個(gè)數(shù)不敏感等特性。2 序列比對(duì)算法比擬通過(guò)上述介紹，本文對(duì)幾

6、種最常用的基因序列比對(duì)算法進(jìn)行如下比擬如表1：在實(shí)際試驗(yàn)中處理生物信息數(shù)據(jù)時(shí)，考慮各種序列比對(duì)算法的速度和適用范圍，啟發(fā)式算法的應(yīng)用最為廣泛。進(jìn)一步，雖然BLAT算法的適用范圍較BLAST小，但兩者原理相似，且BLAT速度更快，便于處理大量的基因數(shù)據(jù)，在進(jìn)行簡(jiǎn)單的DNA基因序列比對(duì)任務(wù)時(shí)，研究者更青睞BLAT算法。3 結(jié)語(yǔ)序列比對(duì)是生物信息學(xué)中最重要、最根本的方法，對(duì)于從大量生物數(shù)據(jù)中提取有價(jià)值的信息有重大的意義。我國(guó)在序列比對(duì)方面研究較為落后，且目前提出的算法較少，大多數(shù)都是在幾種根本序列比對(duì)算法的根底上進(jìn)行的改良。如：張濤濤、郭茂祖等介紹了一種參數(shù)序列比對(duì)方法4，該方法把最正確比對(duì)作為權(quán)值和罰分的函數(shù)，可以系統(tǒng)地得到參數(shù)的選擇對(duì)最正確比對(duì)結(jié)果的影響。準(zhǔn)確率和運(yùn)算速度是評(píng)價(jià)序列比對(duì)算法的重要依據(jù)，因此，獲得比對(duì)準(zhǔn)確率更高、時(shí)間空間效率更好的序列比對(duì)算法是生物信息學(xué)研究的一個(gè)重要課題。參考文獻(xiàn)：1許忠能著.生物信息學(xué)M.北京：清華大學(xué)出版社，2009.2何萬(wàn)雙.雙序列比對(duì)算法研究D.湖南：國(guó)防科技大學(xué)，