多序列比對算法綜述

王櫻 李錫輝

【摘要】在生物信息學(xué)中，如何對多組基因序列進(jìn)行有效且快速的比對一直都是熱門課題之一，也是至今仍未解決的NP難題之一。本文詳細(xì)介紹序列比對的背景與意義，并針對幾種常用的多序列比對算法進(jìn)行比較，并提出了多序列比對算法研究的方向。

【關(guān)鍵詞】生物信息學(xué)序列比對動態(tài)規(guī)劃算法

一、背景與意義

隨著人類基因組計(jì)劃的順利實(shí)施和信息技術(shù)的迅速發(fā)展，GeneBank、EMBL和DDBJ國際三大核酸序列數(shù)據(jù)庫數(shù)據(jù)量呈指數(shù)增長。生物學(xué)家、數(shù)學(xué)家和計(jì)算機(jī)科學(xué)家都面臨著一個相同的并且嚴(yán)峻的問題，如何利用、表達(dá)這些數(shù)據(jù)進(jìn)而分析與解釋基因序列間的潛在關(guān)系，從中發(fā)掘出對人類有利的信息。為迎接挑戰(zhàn)，一門涉及生物、數(shù)學(xué)、物理、化學(xué)、計(jì)算機(jī)科學(xué)等諸多科學(xué)的新型學(xué)科應(yīng)運(yùn)而生，并且日益成為二十一世紀(jì)自然科學(xué)的核心領(lǐng)域之一。

生物信息學(xué)的主要研究對象是DNA序列和蛋白質(zhì)序列，主要通過分類、分析和檢索核苷酸序列或氨基酸序列，獲取基因編碼和調(diào)控、代謝途徑、DNA和蛋白質(zhì)結(jié)構(gòu)功能及其相互關(guān)系等各方面的知識。所以在生命起源、生物進(jìn)化以及細(xì)胞、器官和個體的出現(xiàn)、生長、病變、消亡等生命科學(xué)問題中，生物信息學(xué)都起著非常重要的作用。生物信息學(xué)是發(fā)現(xiàn)生命科學(xué)問題中的基本規(guī)律和時空聯(lián)系，發(fā)掘生物序列數(shù)據(jù)中蘊(yùn)含的生物學(xué)意義的交叉學(xué)科[1]。

在生物信息學(xué)中，序列比對是最基本、最重要的操作。對于基因序列，通過比對可以推測出哪個基因家族可能包含該序列，并可以推測出該序列可能具有的生物學(xué)功能；對于蛋白質(zhì)序列，通過比對可以推測出該序列可能的功能和結(jié)構(gòu)，并可以找出與它同源的蛋白質(zhì)序列。所以在生物信息學(xué)中，序列比對具有非常重要的意義和實(shí)用價值。目前，國際上提出了眾多經(jīng)典的比對算法，也開發(fā)了眾多的序列比對軟件。但對于同一組序列，不同的軟件采用不同的序列比對算法，其運(yùn)算速度和比對結(jié)果都有很大差異。有些軟件考慮了比對結(jié)果而運(yùn)行時間較長，而有些軟件運(yùn)算速度很快比對結(jié)果卻不理想。一般情況下兩者不能同時兼得。所以，對于序列比對算法的研究還有待繼續(xù)深入。

二、多序列比對的研究現(xiàn)狀及發(fā)展趨勢

多序列比對是雙序列比對的一般性推廣。由于核酸數(shù)據(jù)庫容量的增長呈指數(shù)級，序列比對的數(shù)量通常都會遠(yuǎn)遠(yuǎn)大于兩個，使用動態(tài)規(guī)劃算法來解決比對問題已經(jīng)是不可行的了，這使得多序列比對成為一NP難題。為了解決這一難題，人們提出了許多近似算法。

2.1動態(tài)規(guī)劃算法

多序列比對最早采用的是動態(tài)規(guī)劃算法來解決。動態(tài)規(guī)劃算法中最為經(jīng)典的是Needleman-Wunsch算法，其解決思路是把整個問題分解成多個相互聯(lián)系的子問題，通過依次解決每個子問題，從而解決整個問題。動態(tài)規(guī)劃算法最初用于求解兩個序列的比對，當(dāng)把動態(tài)規(guī)劃的基本思想推廣到多序列比對時，3個很短序列的比對還可以順利進(jìn)行。比對序列的數(shù)量如果超過3個，由于需要很大的存儲空間和很長的運(yùn)行時間，比對根本無法進(jìn)行下去。所以多序列比對問題不能采用動態(tài)規(guī)劃算法來解決。Carrillo和Lipman等人對該算法進(jìn)行了改進(jìn)，提出了Carrillo-Lipman算法，通過減少存儲空間將序列比對的數(shù)量提高到10。2004年，唐玉榮等人對動態(tài)規(guī)劃算法進(jìn)行了優(yōu)化[2]，與基本動態(tài)規(guī)劃法敏感性相同，但降低了算法的時間復(fù)雜度，并在減少存儲空間方面也有一定的效果。

2.2啟發(fā)式算法

目前，絕大多數(shù)算法屬于啟發(fā)式算法，包括星比對算法，漸進(jìn)式比對算法，迭代細(xì)化方法等。其中應(yīng)用最早的是星比對算法，而應(yīng)用最廣并且效果較好的是漸進(jìn)式比對算法。Hogeweg和Hesper首先提出漸進(jìn)式比對算法，而后Feng和Taylor對其加以完善。與動態(tài)規(guī)劃算法相比，該算法在計(jì)算速度、存儲空間和序列數(shù)目等方面都更加優(yōu)良。并且，漸進(jìn)式比對算法能夠直接用于構(gòu)造進(jìn)化樹，反映序列間的進(jìn)化關(guān)系。2005年，段敏等人提出了一種用減少序列比對過程中總評分的方法來達(dá)到局部優(yōu)化目的的多序列比對算法[3]。啟發(fā)式算法雖然在一定層度上減少了算法的運(yùn)行時間和存儲空間，但都有一些不足之處。星比對算法中，無論采用何種方法并不能保證找到的序列是最好的中心序列。漸進(jìn)式比對算法中，構(gòu)造的指導(dǎo)樹有時不一定真正反映系統(tǒng)的進(jìn)化信息，根據(jù)指導(dǎo)樹漸進(jìn)比對容易產(chǎn)生局部最優(yōu)化問題。迭代細(xì)化算法中，無法采用何種迭代策略得到的結(jié)果最優(yōu)。

2.3隨機(jī)算法

多序列比對中，應(yīng)用最多的隨機(jī)算法有遺傳算法、模擬退火算法和粒子群算法等。遺傳算法是一種全局意義上的自適應(yīng)隨機(jī)搜索方法，它借鑒生物進(jìn)化規(guī)律，模擬生物進(jìn)化過程中的一系列事件，包括突變、交配和選擇，最終得到一個優(yōu)化解。模擬退火算法則是模擬物理中的退火過程并結(jié)合復(fù)雜系統(tǒng)中的組合優(yōu)化之間的相似性來尋找最優(yōu)解。2008年，向昌盛等人提出了將遺傳算法和模擬退火算法相結(jié)合的遺傳退火進(jìn)化思想[4]，設(shè)計(jì)了運(yùn)用該思想進(jìn)行多序列比對的算法過程，實(shí)驗(yàn)結(jié)果表明該算法是行之有效的。2011年，徐小俊等人針對粒子群優(yōu)化易陷入局部最優(yōu)、收斂速度慢的現(xiàn)象，提出了一種分段取值慣性權(quán)重（SW）方法[5]，該方法在解決多序列比對問題時可以有效地避免算法早熟，并提高解的精度。

2.4分治算法

分治算法是把一個大問題分解成若干個小問題來解決。Stoye提出了一種新的分治算法DCA，將Carrillo-Lipman算法引入進(jìn)來。在不影響特征表現(xiàn)的前提下，把序列分割成完全滿足Carrillo-Lipman算法長度要求的子序列，使用Carrillo-Lipman算法進(jìn)行序列比對。2000年Stoye又提出了一種OMA算法，以達(dá)到減少存儲空間的目的。2009年，業(yè)寧等人設(shè)計(jì)了一個DCA-ClustalW算法來解決多序列比對問題[6]，從縱向和橫向兩個方面將復(fù)雜問題簡單化，并在BaliBase基準(zhǔn)數(shù)據(jù)集上測試了算法的可行性。

2.5其他算法

2006年，陳娟等人給出了多重序列比對的蟻群算法[7]，結(jié)果顯示蟻群算法可以有效解決多重序列比對問題并具有自適應(yīng)性、魯棒性等特點(diǎn)。而文獻(xiàn)[8，9]針對蟻群算法易于陷入局部最優(yōu)解、收斂速度慢等問題，提出了改進(jìn)的方法。

三、結(jié)論

生物信息學(xué)中最基本和最核心的問題之一就是多序列比對。由于多序列比對處理的數(shù)據(jù)越來越龐大和復(fù)雜，所以其算法對計(jì)算精度和運(yùn)算速度的要求也越來越高。如何能快速有效的獲得比對的結(jié)果，一直苦惱著眾多的學(xué)者們。

參考文獻(xiàn)

[1]孫嘯，陸祖宏，謝建明.生物信息學(xué)基礎(chǔ).北京：清華大學(xué)出版社，2005，10-17

[2]唐玉榮，一種優(yōu)化的生物序列比對算法.計(jì)算機(jī)工程與設(shè)計(jì)，2004，25（11）：1936-1945

[3]段敏，許龍飛.生物DNA序列比對算法研究.佳木斯大學(xué)學(xué)報，2005，23（2）：153-158

[4]向昌盛，周建軍，周子英.模擬退火遺傳算法在生物多序列比對中的應(yīng)用.湖南農(nóng)業(yè)科學(xué)，2008，（4）：29-34

[5]徐小俊，雷秀娟，郭玲.基于SWGPSO算法的多序列比對.計(jì)算機(jī)工程，2011，37（6）：184-186

[6]業(yè)寧，張倩倩，許翠云.一種多序列比對分值算法DCA-ClustalW.計(jì)算機(jī)與數(shù)學(xué)工程，2010，38（11）：30-33

[7]陳娟，陳.多重序列比對的蟻群算法.計(jì)算機(jī)應(yīng)用，2006，26（6）：124-128

[8]彭東海，駱嘉偉，袁輝勇.基于改進(jìn)蟻群算法的多序列比對.計(jì)算機(jī)工程與應(yīng)用，2009，45（33）：114-119

[9]李方潔，劉希玉.基于漸進(jìn)蟻群算法的DNA多序列比對.網(wǎng)絡(luò)安全技術(shù)與應(yīng)用，2010，（9）：78-80