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

王櫻 李錫輝

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

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

一、背景與意義

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

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

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

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

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

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

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

2.2啟發(fā)式算法

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

2.3隨機(jī)算法

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

2.4分治算法

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

2.5其他算法

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

三、結(jié)論

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

參考文獻(xiàn)

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

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

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

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

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

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

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

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

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