唐曉芬

(寧夏大學(xué)數(shù)學(xué)與計(jì)算機(jī)學(xué)院，寧夏 銀川 750004)

0 引言

1971年，Stephen A.Cook給出了NP-完全問(wèn)題的定義［1］。P類問(wèn)題為多項(xiàng)式界的問(wèn)題，而NP-完全問(wèn)題是這樣一類問(wèn)題，如果其中的某個(gè)問(wèn)題存在多項(xiàng)式界的算法，則NP類中的每一個(gè)問(wèn)題都存在一個(gè)多項(xiàng)式界算法。NP-完全問(wèn)題通常被認(rèn)為是一些人們難以在有限的時(shí)間、空間內(nèi)對(duì)問(wèn)題求出最佳解的問(wèn)題。目前為止已經(jīng)證明屬于NP-完全問(wèn)題的有兩千多個(gè)。

隨著新一代基因測(cè)序技術(shù)廣泛用于生物學(xué)研究，可獲得的基因數(shù)據(jù)呈指數(shù)級(jí)增加，如何對(duì)這些海量數(shù)據(jù)進(jìn)行快速、準(zhǔn)確分析并從中找到有用信息是目前值得研究的一個(gè)新領(lǐng)域。生物信息學(xué)是把統(tǒng)計(jì)理論和計(jì)算機(jī)科學(xué)應(yīng)用到分子生物學(xué)上，使用模式識(shí)別、數(shù)據(jù)挖掘和機(jī)器學(xué)習(xí)等原理和技術(shù)對(duì)海量的基因組測(cè)序數(shù)據(jù)進(jìn)行高效快速的統(tǒng)計(jì)分析，了解相關(guān)實(shí)驗(yàn)的生物學(xué)意義并理解生物學(xué)過(guò)程的一門(mén)學(xué)科［2］。在解決基因識(shí)別、序列分析及序列比對(duì)等問(wèn)題時(shí)需要用到一些先進(jìn)的信息處理及分析技術(shù)，生物信息學(xué)中有些涉及計(jì)算的問(wèn)題是NP-完全問(wèn)題。

1 生物信息學(xué)中的NP-完全問(wèn)題

1.1 構(gòu)建系統(tǒng)發(fā)生樹(shù)問(wèn)題

系統(tǒng)發(fā)生分析研究物種間的進(jìn)化關(guān)系，系統(tǒng)發(fā)生分析的目標(biāo)是通過(guò)比較物種之間的特征，構(gòu)建一棵系統(tǒng)發(fā)生樹(shù)。通過(guò)對(duì)相關(guān)生物學(xué)數(shù)據(jù)進(jìn)行分析，然后建模提取特征，進(jìn)而比較這些特征，由此研究生物進(jìn)化的歷史。系統(tǒng)發(fā)生樹(shù)根據(jù)物種之間的遺傳歷史描述它們的世襲關(guān)系。給定一個(gè)包含多條序列的物種集合，隨著序列條數(shù)的增大，系統(tǒng)發(fā)生樹(shù)數(shù)目呈指數(shù)形式增長(zhǎng)。已經(jīng)證明構(gòu)建系統(tǒng)發(fā)生樹(shù)是一個(gè)NP-完全問(wèn)題［3］。但是只有一棵樹(shù)代表了待分析基因或生物體之間的真實(shí)進(jìn)化關(guān)系，為了找出這棵反映真實(shí)進(jìn)化關(guān)系的樹(shù)，對(duì)每種可能的進(jìn)化樹(shù)都進(jìn)行窮舉是不可能的。這就需要研究在適當(dāng)?shù)臅r(shí)間內(nèi)，找到代表待分析基因或生物體之間的真實(shí)進(jìn)化關(guān)系的系統(tǒng)發(fā)生樹(shù)的最優(yōu)近似解算法。

1.2 序列多重比對(duì)問(wèn)題

目前，序列多重比對(duì)問(wèn)題涉及的NP-完全問(wèn)題有以下2個(gè):

(1)利用SP模型尋找最優(yōu)序列多重比對(duì)問(wèn)題。

為了找到多條序列的共性必須進(jìn)行序列多重比對(duì)。通過(guò)序列比對(duì)可以研究序列的同源性、序列始祖演化關(guān)系以及序列的保守性。同時(shí)對(duì)一組序列進(jìn)行比對(duì)，能發(fā)現(xiàn)多個(gè)序列中與結(jié)構(gòu)域和功能相關(guān)的保守序列片段。多序列比對(duì)對(duì)蛋白質(zhì)二級(jí)、三級(jí)結(jié)構(gòu)預(yù)測(cè)及推斷各個(gè)序列的進(jìn)化史來(lái)說(shuō)都非常重要。用人工進(jìn)行多序列比對(duì)是一項(xiàng)耗時(shí)且困難的工作，由算法或程序進(jìn)行多重序列比對(duì)時(shí)，要對(duì)所得到的比對(duì)結(jié)果進(jìn)行有效評(píng)價(jià)，以確定其優(yōu)劣。大多數(shù)的多序列比對(duì)算法是啟發(fā)式的并不是全局最優(yōu)的。SP逐對(duì)加和模型是一種多重序列比對(duì)的評(píng)價(jià)模型，即將一個(gè)序列多重比對(duì)所有列的得分全部加起來(lái)，其和作為該多重比對(duì)的得分。多重序列比對(duì)的最終目標(biāo)是得到一個(gè)得分最高的序列排列，從而分析各序列間的相似性和差異，通常用動(dòng)態(tài)規(guī)劃算法。SP逐對(duì)加和模型不是優(yōu)化的方法，因?yàn)閷?duì)于K條待比對(duì)序列動(dòng)態(tài)規(guī)劃算法的計(jì)算過(guò)程相當(dāng)于依次訪問(wèn)在K維空間組成的超晶格的每個(gè)節(jié)點(diǎn)，隨著待比對(duì)序列條數(shù)的增加，計(jì)算量和所要求的空間成指數(shù)增長(zhǎng)。已經(jīng)證明，利用SP模型尋找最優(yōu)多重序列比對(duì)是一個(gè)NP-完全問(wèn)題［4-6］。

(2)多序列的樹(shù)形比對(duì)問(wèn)題。

多序列樹(shù)形比對(duì)的原理是對(duì)K條待比對(duì)的序列，建立一棵具有K個(gè)葉節(jié)點(diǎn)的樹(shù)，其中每個(gè)葉節(jié)點(diǎn)對(duì)應(yīng)一條待比對(duì)序列。如果將序列也賦予樹(shù)的內(nèi)部節(jié)點(diǎn)，則可以計(jì)算樹(shù)中每個(gè)分支的權(quán)值。權(quán)值代表對(duì)應(yīng)分支連接的兩條序列之間的相似度，所有權(quán)值的和就是這多序列樹(shù)形比對(duì)的得分。如何尋找一種樹(shù)的內(nèi)部節(jié)點(diǎn)序列排列方式，使得樹(shù)的得分最大就是樹(shù)形比對(duì)要解決的問(wèn)題。樹(shù)形比對(duì)實(shí)際上是多序列組合比對(duì)問(wèn)題，是一個(gè)NP-完全問(wèn)題。

1.3 基因表達(dá)數(shù)據(jù)中尋找最顯著雙聚類問(wèn)題

聚類是分析基因表達(dá)數(shù)據(jù)最通用的方法，對(duì)基因和條件進(jìn)行聚類的雙聚類方法，可以發(fā)現(xiàn)基因子集在條件子集下表現(xiàn)出相似的表達(dá)模式，對(duì)于揭示僅僅在部分條件下活躍的生物過(guò)程是非常有用的，在給定的基因表達(dá)數(shù)據(jù)矩陣中，尋找滿足縮放波動(dòng)一致性約束的最大雙聚類簇有助于研究基因的共調(diào)控網(wǎng)絡(luò)，基因縮放模式雙聚類是生物學(xué)家感興趣的一種模式?；蚩s放模式雙聚類簇發(fā)現(xiàn)問(wèn)題是一個(gè)NP-完全問(wèn)題［7-8］

2 NP-完全問(wèn)題的解決方法

目前對(duì)于生物信息學(xué)中的NP-完全問(wèn)題，通常用一些近似的方法來(lái)求解具體問(wèn)題。對(duì)于多重序列比對(duì)問(wèn)題，盲目地搜索整個(gè)搜索空間的方法效率低下，用人工智能空間搜索策略的剪枝技術(shù)可以提高搜索效率，根據(jù)具體問(wèn)題將搜索空間限定在一個(gè)較小的區(qū)域范圍內(nèi)。目前已有的系統(tǒng)發(fā)生樹(shù)的構(gòu)建方法根據(jù)建樹(shù)算法在執(zhí)行過(guò)程中采用的搜索方式可分為3類:(1)窮盡搜索法，對(duì)每種可能的樹(shù)都進(jìn)行搜索并判斷是否能表示所分析物種的進(jìn)化關(guān)系;(2)分枝約束法，即根據(jù)一定的約束條件將所搜索空間限制在一定范圍內(nèi)，產(chǎn)生可能的樹(shù)，然后選擇最優(yōu)。這是人工智能技術(shù)中的一種空間搜索策略，這種搜索方式不需要搜索整個(gè)樹(shù)空間，可以提高算法效率;(3)啟發(fā)式方法或經(jīng)驗(yàn)性方法，即根據(jù)先驗(yàn)知識(shí)或一定的指導(dǎo)性規(guī)則壓縮搜索空間，提高計(jì)算速度。這種方法能處理大量的分類單元，雖然不能保證所構(gòu)建的樹(shù)是最優(yōu)的，但實(shí)際結(jié)果往往接近于最優(yōu)。

目前對(duì)于NP-完全問(wèn)題的解法可總結(jié)為以下幾種。

(1)只求解規(guī)模比較小的問(wèn)題。

(2)利用動(dòng)態(tài)規(guī)劃、分枝約束等技術(shù)減小搜索空間，加快問(wèn)題的求解速度。

(3)針對(duì)具體問(wèn)題的特點(diǎn)，根據(jù)問(wèn)題的實(shí)際輸入，涉及實(shí)用求解算法，這樣的算法雖然在最壞情況下其時(shí)間復(fù)雜度是非多項(xiàng)式的，但是算法執(zhí)行的平均效率和復(fù)雜度與多項(xiàng)式的算法相當(dāng)。

(4)采用近似算法或啟發(fā)式方法，尋找相應(yīng)問(wèn)題比較接近最優(yōu)解的最優(yōu)解，或利用常規(guī)的求解技術(shù)求解。比如，利用神經(jīng)網(wǎng)絡(luò)、遺傳算法、粒子群優(yōu)化等計(jì)算智能方法。

計(jì)算智能作為人工智能的一個(gè)分支，是以自適應(yīng)的機(jī)制研究和模擬自然智能并建立模型，以實(shí)現(xiàn)對(duì)復(fù)雜問(wèn)題的求解。隨著技術(shù)的進(jìn)步，在科學(xué)研究和工程實(shí)踐中遇到的問(wèn)題變得越來(lái)越復(fù)雜，采用傳統(tǒng)的計(jì)算方法來(lái)解決這些問(wèn)題面臨著計(jì)算復(fù)雜度高、計(jì)算時(shí)間長(zhǎng)等問(wèn)題，特別是對(duì)于一些NP難問(wèn)題，傳統(tǒng)算法根本無(wú)法在可以忍受的時(shí)間內(nèi)求出精確的解。因此，為了在求解時(shí)間和求解精度上取得平衡，計(jì)算機(jī)科學(xué)家提出了很多具有啟發(fā)式特征的計(jì)算智能算法。目前已有的計(jì)算智能的主要方法有神經(jīng)網(wǎng)絡(luò)、遺傳算法、免疫算法、模擬退火算法、蟻群算法、粒子群算法、遺傳編程等。目前，有學(xué)者研究利用計(jì)算智能的方法解決生物信息學(xué)中的NP-完全問(wèn)題并取得了比較好的效果［9-14］。

隨著計(jì)算智能研究的深入和應(yīng)用的日益廣泛，利用計(jì)算智能算法解決生物學(xué)中NP-完全問(wèn)題的研究方向?yàn)?在研究和改進(jìn)現(xiàn)有算法的基礎(chǔ)上，在各學(xué)科不斷交叉發(fā)展的大背景下，將新的智能模擬算法以及各種智能算法的綜合集成用于可進(jìn)行多目標(biāo)優(yōu)化的生物信息學(xué)問(wèn)題，構(gòu)成一個(gè)優(yōu)勢(shì)互補(bǔ)、復(fù)合協(xié)同的綜合集成系統(tǒng)。

目前將計(jì)算智能方法用于解決生物信息學(xué)問(wèn)題的文獻(xiàn)很多，但是它們普遍存在這樣的問(wèn)題，側(cè)重于算法設(shè)計(jì)，較少提供生物學(xué)家易用的程序或工具，對(duì)所提出方法的生物學(xué)意義驗(yàn)證較少，大多不具實(shí)用性。因此，今后將計(jì)算智能算法應(yīng)用于生物信息學(xué)領(lǐng)域的研究應(yīng)該注重針對(duì)所研究問(wèn)題提出的任一解決方法，對(duì)該方法的合理性和可靠性進(jìn)行統(tǒng)計(jì)分析，通過(guò)多種不同分析方法進(jìn)行驗(yàn)證，并能開(kāi)發(fā)相應(yīng)工具或軟件，使所提出的算法具有較高的可信度和實(shí)際的生物學(xué)意義。

3 結(jié)束語(yǔ)

如何從海量生物數(shù)據(jù)中挖掘信息，幫助人們改善其生存環(huán)境和提高生活質(zhì)量，促成了結(jié)合數(shù)據(jù)挖掘和模式識(shí)別等理論的新興交叉科學(xué)——生物信息學(xué)的發(fā)展。目前生物信息學(xué)研究的熱點(diǎn)包括:海量生物數(shù)據(jù)的有效分析、整理;基因組組分信息分析與數(shù)據(jù)處理，揭示生物信息編碼系統(tǒng)的規(guī)律、演化和關(guān)系;利用基因芯片進(jìn)行全基因組轉(zhuǎn)錄分析，在此基礎(chǔ)上研究疾病發(fā)病機(jī)制、疾病分型和識(shí)別疾病;通過(guò)對(duì)蛋白質(zhì)進(jìn)行結(jié)構(gòu)和功能分析獲取隱含其中的有用生物學(xué)信息。這些研究能夠?yàn)槿藗兝斫馍瓦M(jìn)化、發(fā)現(xiàn)新藥物和新療法提供幫助。在急劇增長(zhǎng)的數(shù)據(jù)面前，如果僅僅依靠傳統(tǒng)生物試驗(yàn)方法由人工驗(yàn)證組分信息、確定疾病發(fā)生的機(jī)理以及測(cè)定蛋白質(zhì)功能結(jié)構(gòu)，完成這些工作所需設(shè)備價(jià)格昂貴而且非常耗時(shí)，在這種情況下急需依靠模式識(shí)別、數(shù)據(jù)挖掘和計(jì)算智能等技術(shù)建立自動(dòng)識(shí)別方法，以提高試驗(yàn)效率，降低試驗(yàn)代價(jià)。

［1］Stephen A Cook.The complexity of theorem-proving procedures［C］//Proceedings of the Third Annual ACM Symposium on Thoery of Computing.1971:151-158.

［2］Hogeweg P，Hesper B.Interactive instruction on population interactions［J］.Comput.Biol.Med，1978，8(4):319-327.

［3］Yue F，Tang J.A divide-and-conquer implementation of three sequence alignment and ancestor inference［C］//Proc.1st IEEE International Conference on Bioinformatics and Biomedicine(BIBM).2007:143-150.

［4］Allocco D J，Kohane I S，Butte A J.Quantifying the relationship between co-expression，co-regulation and gene function［J］.BMC Bioinformatics，2004，5(1):18.

［5］Yang Z.Inference of selection from multiple species alignments［J］.Curr.Opin.Genet.Dev.，2002，12(6):688-694.

［6］Hein J.An algorithm combining DNA and protein alignment［J］.J.Theor.Biol.，1994，167(2):169-174.

［7］Cheng Y，Church G M.Biclustering of expression data［C］//Proceedings of the Eighth International Conference on Intelligent Systems for Molecular Biology.2000:93-103.

［8］Cano C，Adarve L，López J.et al.Possibilistic approach for biclustering microarray data［J］.Comput Biol.Med.，2007，37(10):1426-1436.

［9］Handl J，Kell D B，Knowles J.Multiobjective optimization in bioinformaties and computational biology［J］.IEEE/ACM Transaetionson Computational Biology and Bioinformaties(TCBB)，2007，4(2):279-292.

［10］Mitra Sushmita.Computational intelligence in bioinformaties［J］.Lecture Notes in Computer Science，2005，3400:134-152.

［11］Queiroz A，Donoghue M，Kim J.Separate versus combined analysis of phylogenetic evidence［J］.Annual Review of E-cology and Systematics，1995，26(1):657-681.

［12］Andries P Engelbrecht.計(jì)算智能導(dǎo)論［M］.譚營(yíng)譯.北京:清華大學(xué)出版社，2010.

［13］李伍舉.計(jì)算機(jī)輔助分子生物學(xué)試驗(yàn)設(shè)計(jì)與分析［M］.北京:軍事醫(yī)學(xué)科技出版社，2009.

［14］［英］楊子恒.計(jì)算分子進(jìn)化［M］.鐘揚(yáng)，張文娟譯.上海:復(fù)旦大學(xué)出版社，2008.