生物序列比對算法綜述

1、word生物序列比對算法綜述【摘 要】 隨著生物信息學(xué)的快速開展，序列比對算法成為研究的熱點問題。本文介紹序列比對算法的概念及研究，并針對幾種常用的序列比對算法進行比擬。同時也簡單說明序列比對算法的改良方向。【關(guān)鍵詞】 生物信息學(xué) 序列比對 準確率 時空效率隨著生命科學(xué)研究的興起和計算機技術(shù)的飛速開展，生物信息學(xué)已成為自然科學(xué)的核心領(lǐng)域之一1?；蛐蛄斜葘κ巧镄畔⑻幚淼淖罡痉椒ǎ瑢Πl(fā)現(xiàn)基因功能、比擬基因、探究生物進化等具有非常重要的作用。1 序列比對算法概述所謂序列比對2，是指兩個或多個序列按字母比擬，盡可能確切地反映它們之間的相似和相異性，用于說明序列之間的同源關(guān)系。通過序列比對，找出序

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

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

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

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

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