寧靜，鐘一文，林娟，寧正元

（福建農(nóng)林大學(xué)計算機(jī)與信息學(xué)院，福建福州350002）

群智能優(yōu)化算法及其在生物信息學(xué)問題中的應(yīng)用

寧靜，鐘一文，林娟，寧正元

（福建農(nóng)林大學(xué)計算機(jī)與信息學(xué)院，福建福州350002）

生物信息學(xué)研究需要使用先進(jìn)的計算工具處理大量生物的模糊的和不確定的數(shù)據(jù)。群智能優(yōu)化算法以低成本、快速和準(zhǔn)確合理地解決復(fù)雜的搜索問題的優(yōu)點，使其成為一族能用以較好地解決生物信息學(xué)中的問題的啟發(fā)式算法。綜述群智能優(yōu)化算法及其在生物信息學(xué)問題中的應(yīng)用。

群智能；優(yōu)化算法；生物信息學(xué)

過去幾十年來，科學(xué)界所收集的有關(guān)的生物數(shù)據(jù)大規(guī)模增長，這種龐大的資源廣泛存在于基因組的形式、蛋白質(zhì)序列、基因表達(dá)數(shù)據(jù)等，導(dǎo)致我們需要有效的和高效的計算工具去存儲、分析和解釋這些大量的數(shù)據(jù)。

生物信息學(xué)作為應(yīng)用于生物發(fā)現(xiàn)的計算方法的科學(xué)包括以下幾個領(lǐng)域：生物科學(xué)、計算機(jī)科學(xué)、數(shù)學(xué)和統(tǒng)計學(xué)。各個領(lǐng)域最終目的是對生命科學(xué)有更深入的了解并且建立一個全球性視角，從此可以得出統(tǒng)一的生物學(xué)原理[1]。生物信息學(xué)研究的主要目標(biāo)是：

（1）為探索大量生物數(shù)據(jù)集之間的關(guān)系開發(fā)算法和建立數(shù)學(xué)模型；

（2）分析和解釋核苷酸和氨基酸序列、蛋白質(zhì)結(jié)構(gòu)域和蛋白質(zhì)結(jié)構(gòu)等多元的數(shù)據(jù)。

1 群智能優(yōu)化算法

為能夠提供一種有效存儲、檢索和管理大容量的生物數(shù)據(jù)庫開發(fā)工具。

智能優(yōu)化算法在這一領(lǐng)域的工作是由一組群居的昆蟲（如蜜蜂、白蟻和黃蜂）的共同行為啟發(fā)所產(chǎn)生的。這些昆蟲個體的行為常常太簡單，但是通過共同合作凝聚起來，卻可以完成許多復(fù)雜的、生存所必需的任務(wù)，因此他們是可以呈現(xiàn)高度的社會組織性智能行為。一些高等哺乳類動物（如獅子）也同樣具有這種群居性的社會生活。這種生物群居在一起所表現(xiàn)出來的集體智慧和社會行為被稱為群智能（swarm intelligence，SI）。

1.1 群智能與群智能優(yōu)化算法

受昆蟲的社會性行為啟發(fā)，研究人員通過對昆蟲的社會性進(jìn)行模擬，產(chǎn)生了一系列新的方法來解決許多傳統(tǒng)問題，這些新的解決問題的方法就是群智能所研究得。群智能系統(tǒng)通常由一組可以通過改變局部環(huán)境進(jìn)行彼此間的相互作用的能夠執(zhí)行某些操作的實體組成，這組主體能夠合作進(jìn)行分布問題求解。1999年，Bonabeau、Dorigo和Theraulaz給出了群智能的一種不嚴(yán)格定義[2]：任何一種由昆蟲群體或其它動物社會行為機(jī)制而激發(fā)設(shè)計出的算法或分布式解決問題的策略均屬于群智能。

群智能優(yōu)化算法中的每一個個體都需遵循以下規(guī)則：

（1）同質(zhì)性：群中的每個個體具有相同的行為模式。群在沒有領(lǐng)導(dǎo)者的情況下運(yùn)動，即使出現(xiàn)了臨時的領(lǐng)導(dǎo)者，群也按照其個體的行為模式運(yùn)動；

（2）位置：每個個體的運(yùn)動只被最接近它的群個體所影響；

（3）避免碰撞：避免與鄰近的個體相碰撞；

（4）速度一致：和鄰近的個體的平均速度保持一致；

（5）向中心聚集：向鄰近個體的平均位置移動。

群智能優(yōu)化算法的優(yōu)點[3]有以下幾點：

（1）分布性：群體中相互合作的個體是分布式的，不存在中心控制。這樣的分布式更適合于網(wǎng)絡(luò)環(huán)境下的工作狀態(tài)；

（2）魯棒性：系統(tǒng)沒有集中的控制指令和數(shù)據(jù)存儲，這樣的系統(tǒng)更具有魯棒性，不會由于某一個或者幾個個體的故障而影響整個問題的求解進(jìn)程；

（3）可擴(kuò)充性：系統(tǒng)不通過個體之間的直接通信，而通過非直接通信方式進(jìn)行信息的傳輸與合作，這樣的系統(tǒng)具有更好的可擴(kuò)充性，由于系統(tǒng)中個體的增加而增加的信息開銷也較??；

（4）簡單性：系統(tǒng)中每個個體的能力十分簡單，每個個體的執(zhí)行時間也比較短，且實現(xiàn)較為方便；

（5）自組織性：群體表現(xiàn)出來的復(fù)雜行為，是通過簡單個體的交互過程突顯出來的性能。

群智能為在沒有集中控制且不提供全局模型的前提下尋找復(fù)雜的分布式問題求解方案提供了思路。群智能方法在大多數(shù)的優(yōu)化問題的應(yīng)用領(lǐng)域都表現(xiàn)出較好的性能。如多目標(biāo)優(yōu)化、數(shù)據(jù)分類和聚類、模式識別、電信管理、生物系統(tǒng)建模、信號處理、機(jī)器人控制、決策支持等領(lǐng)域。蟻群優(yōu)化算法和粒子群優(yōu)化算法是在計算智能領(lǐng)域已經(jīng)取得成功的兩種優(yōu)化算法。

1.2 蟻群優(yōu)化算法（ACO）

受到螞蟻覓食時的通信機(jī)制的啟發(fā)，1991年意大利學(xué)者Dorigo等人提出了蟻群優(yōu)化算法(ant colony optimization，ACO)，通過候選解組成的群體進(jìn)化過程來尋求最優(yōu)解，解決計算機(jī)算法學(xué)中經(jīng)典的NP困難問題“旅行商問題(traveling salesman problem,TSP)”[4]。

螞蟻在覓食過程中會留下一種隨時間逐漸消失的分泌物，即信息素。如果螞蟻從巢穴到食物源所走的路徑較短，則螞蟻在走這條路徑時，從巢穴到食物源再返回到巢穴所經(jīng)歷的時間就短，從而在相同時間內(nèi)，在較短路徑上螞蟻所留下的信息素就比較多。而后面的螞蟻要根據(jù)前面走過的螞蟻所留下的信息素的多少選擇其要走的路徑。一條路徑上的信息素越多，螞蟻選擇這條路徑的概率就越大。根據(jù)“信息素較濃的路線更近”的原則，即可選擇出最佳路線。因此，螞蟻群體的集體覓食行為實際上構(gòu)成了一種學(xué)習(xí)信息的正反饋機(jī)制，螞蟻之間通過這種信息交流尋求從巢穴到食物源之間的最短路徑,使得較短的路徑能夠有較大的機(jī)會得到選擇，并且由于采用了概率算法，所以它能夠不局限于局部最優(yōu)解。蟻群優(yōu)化算法正是模擬了這樣的優(yōu)化機(jī)制，即通過個體之間的信息交流與相互協(xié)作最終找到最優(yōu)解。

由于蟻群優(yōu)化算法特有的解決方法，它已經(jīng)被成功用于傳統(tǒng)方法難以解決的非凸、非線性、非連續(xù)的優(yōu)化問題，例如圖的著色(graph coloring)以及最短超串(shortest common super-sequence)等問題[5]。

1.3 粒子群優(yōu)化算法（PSO）

PSO算法是一種基于隨機(jī)種群的優(yōu)化算法[6-7]。該算法模擬鳥集群飛行覓食的行為，鳥之間通過集體的協(xié)作使群體達(dá)到最優(yōu)目的，是一種基于群智能（swarm intelligence,SI）的優(yōu)化方法。

PSO算法有兩個變型，一種是具有全局鄰域，另外一種是具有局部鄰域。在全局模式中，每個粒子向它最好的先前位置和向整個種群中最好的粒子所在位置移動。而在局部模式中，每個粒子向它最好的先前位置并且向在指定鄰域（拓?fù)湎噜徎蛘呖臻g相鄰）中最好的粒子所在位置移動。

假設(shè)在N維的搜索空間中，群中的第i個粒子可以用一個N維向量Xi=（xi1，xi2，…，xiN）表示。體現(xiàn)粒子位置變化的粒子速度，可以由另一個N維向量Vi=（vi1，vi2，…，viN）表示。第i個粒子的最好的先前訪問位置表示為Pi=（pi1，pi2，…，piN）。對于全局變量種群的最好的先前訪問位置可表示為Gi=（gi1，gi2，…，giN），并用上標(biāo)表示迭代的次數(shù)，依照下列的兩個公式操作每一個粒子[8]：

這里j=1,2,…,N；i=1,2,…,M，M是種群的大?。沪胤Q為慣性權(quán)重，用來控制歷史上先前的速度對現(xiàn)在速度的影響，從而影響粒子在平衡全局和局部探測的能力；c1，c2是兩個正常量，分別稱為認(rèn)知參數(shù)和社會參數(shù)；r1，r2是均勻分布在[0,1]上的隨機(jī)數(shù)；t=1,2,…,用來決定迭代次數(shù)。公式(1)用來通過粒子的先前速度和它現(xiàn)在的位置與它歷史最佳訪問位置以及全局歷史最佳訪問位置的距離來計算粒子的新速度。然后依據(jù)公式(2)粒子飛向一個新的位置。

1.4 兩種群智能優(yōu)化算法比較

ACO與PSO的共同點：

（1）都是不確定的概率型全局優(yōu)化算法；

（2）都不依賴于優(yōu)化問題本身的嚴(yán)格數(shù)學(xué)性質(zhì)（如連續(xù)性、可導(dǎo)性等），穩(wěn)健性強(qiáng)；

（3）都具有本質(zhì)并行性，容易并行實現(xiàn)，并且都容易與多種啟發(fā)式算法進(jìn)行結(jié)合，適當(dāng)改善算法的性能；

（4）都具有自組織性和進(jìn)化性；

（5）都對初始值不作要求，可以從各個點開始朝最佳值的方向搜索。

ACO與PSO的區(qū)別點：

（1）優(yōu)化方式不同：PSO是每個個體通過關(guān)注自身迭代過程中的最佳值，整個種群的最優(yōu)值，再結(jié)合自身狀態(tài)來控制其收斂方向；ACO是通過判斷信息素的大小以及同伴間的信息交流、傳遞來達(dá)到最優(yōu);

（2）算法機(jī)理不同：PSO是啟發(fā)式算法，由迭代進(jìn)行；ACO則是采用正反饋機(jī)制;

（3）主要應(yīng)用范疇不同。

兩種算法都有很大的改進(jìn)空間。粒子群優(yōu)化算法的權(quán)值和學(xué)習(xí)因子可以進(jìn)行適應(yīng)性改進(jìn)，可以再考慮一個個體周圍粒子的最佳值；蟻群優(yōu)化算法的參數(shù)也可以進(jìn)行適應(yīng)性改進(jìn)，對收斂性進(jìn)行改進(jìn)以及在離散域和連續(xù)域應(yīng)用的改進(jìn)。這些改進(jìn)的主要目的是避免算法陷入局部最優(yōu)，加快算法的全局收斂[9]。

2 群智能優(yōu)化算法在生物信息學(xué)問題中的應(yīng)用

2.1 應(yīng)用群智能優(yōu)化算法的若干研究問題描述

群智能優(yōu)化算法的一些最新研究表明，群智能優(yōu)化算法已應(yīng)用到不同的生物信息學(xué)問題領(lǐng)域。我們相信在不久的將來群智能優(yōu)化算法將超越傳統(tǒng)的進(jìn)化算法，成為在生物信息學(xué)領(lǐng)域不可缺少的計算方法。

（1）基因表達(dá)數(shù)據(jù)的聚類[10]?；虮磉_(dá)就是指細(xì)胞在生命過程中將存儲在DNA序列中的遺傳信息轉(zhuǎn)錄成mRNA再由mRNA翻譯成具有生命活性的蛋白質(zhì)分子的過程。隨著基因芯片技術(shù)和先進(jìn)生物技術(shù)的快速發(fā)展,基因芯片可以同時對大量的基因表達(dá)譜進(jìn)行快速的測量分析,這就更加速了基因表達(dá)數(shù)據(jù)的產(chǎn)生。以SOM-PSO為例，此算法源于大腦皮層中的信息有序映射。通過此算法，高位數(shù)據(jù)投影到一維或者二維空間。通常，建立一個關(guān)于神經(jīng)元的二維網(wǎng)格，每一個神經(jīng)元代表一類。學(xué)習(xí)過程是無監(jiān)督的。所有的神經(jīng)元對輸入模式競爭，當(dāng)輸入模式贏了的時候選擇此神經(jīng)元。PSO用來改進(jìn)SOM的權(quán)重，使其避免產(chǎn)生不均衡的分類。（SOM-PSO，QPSO）

（2）分子對接問題（molecular docking）[11-12]。分子對接是依據(jù)“鎖-鑰原理”(lock and key principle)，模擬受體生物大分子與配體小分子相互作用。受體與配體相互作用是兩個或多個分子之間的識別過程，這個過程涉及分子之間的空間匹配及能量匹配（靜電作用力、氫鍵作用力、疏水作用力、范德華作用力等）。通過計算，可以預(yù)測受體與配體之間的結(jié)合模式和親和力，是藥物發(fā)現(xiàn)和設(shè)計中一種非常重要的方法，也是國內(nèi)外前沿研究課題。使用PSO對接技術(shù)，可以獲得更好的魯棒性、準(zhǔn)確性和收斂速度。主要優(yōu)化的是分子間的能量（范德華力、氫鍵作用力和電勢能）和分子的內(nèi)部能量。有四個階段：速度更新，粒子移動，本地搜索，更新本地和全局的最優(yōu)位置。本地搜索可能通過一個預(yù)先定義的概率P1s應(yīng)用于粒子。最后，如果粒子能量增加則本地和全局的最優(yōu)位置更新。這些粒子有著符合靈活的對接問題的解的最小的能量。（PSO）

（3）多序列比對問題（MSA）[13]。多序列比對是指按一定的規(guī)律排列基本的DNA、RNA或蛋白質(zhì)序列，找出它們之間結(jié)構(gòu)、功能、進(jìn)化的相似性以至于同源性。最常見的算法有FASTA和BLAST，它們都是基于序列兩兩比對的。解決多序列比對問題的方法有：Pileup算法、Clustalw算法、Carrillo-Lipman算法以及DCA算法。這些算法是通過漸進(jìn)的比對思想，或者是采用迭代比對算法。兩兩比對的局部結(jié)果在多序列比對中往往并不最優(yōu)，這樣會給多序列比對帶來錯誤信息，并且這些錯誤信息不能在后期階段被糾正。而蟻群優(yōu)化算法的信息素的正反饋作用可以有效解決多序列比對問題，并且提高多序列比對的正確性。（ACO）

（4）系統(tǒng)發(fā)育樹的構(gòu)造[14]。系統(tǒng)發(fā)育樹構(gòu)建問題近似于標(biāo)準(zhǔn)的TSP問題?？梢詫⒚總€分支群和一個虛擬城市簡單的聯(lián)系起來，并定義兩個城市之間的距離為生物數(shù)據(jù)矩陣中一對相應(yīng)的分類群的數(shù)據(jù)。這方面已經(jīng)有很成熟的軟件，如MEGA、PAUP、PHYLIP、MOLPHY、PAML等，MATLAB中的Bioinformatics Toolbox也有建立系統(tǒng)發(fā)育樹的功能。（ACO）

（5）RNA二級結(jié)構(gòu)的預(yù)測[15]。RNA二級結(jié)構(gòu)是指由小內(nèi)環(huán)中斷的長莖環(huán)結(jié)構(gòu)（發(fā)夾結(jié)構(gòu)、凸起和內(nèi)環(huán)）。RNA分子的二級機(jī)構(gòu)可以通過計算所有不同氫鍵和域的組合的最小自由能（MFE）結(jié)構(gòu)來計算的預(yù)測?？梢杂酶倪M(jìn)的粒子群優(yōu)化算法來優(yōu)化RNA分子結(jié)構(gòu)（SetPSO，由Neethling和Engelbrecht提出）。一個有效的RNA二級結(jié)構(gòu)（重疊或莖）需要滿足一些約束，比如每個殘基只能與一個標(biāo)準(zhǔn)基配對、不允許有假結(jié)等。收集所有滿足條件的莖組成集合U。SetPSO中的每一個粒子初始化為從U中隨機(jī)選擇的子集。這些粒子的位置和速度，根據(jù)改進(jìn)的加減算子以RNA結(jié)構(gòu)定義下的熱力學(xué)自由能函數(shù)極小化的原理進(jìn)行更新。此算法可以得到一個在多重基準(zhǔn)下的RNA分子近似最優(yōu)的結(jié)構(gòu)。（PSO）

（6）蛋白質(zhì)二級結(jié)構(gòu)的預(yù)測[16-17]。蛋白質(zhì)二級結(jié)構(gòu)指蛋白質(zhì)多肽鏈本身通過氫鍵沿一定方向進(jìn)行折疊和盤繞的方式。二級結(jié)構(gòu)主要有α-螺旋、β-折疊、β-轉(zhuǎn)角。由于所涉及的蛋白質(zhì)折疊過程非常復(fù)雜，并且只有部分理解的簡化模型（如親-疏水格點模型（HP））成為研究蛋白質(zhì)的主要手段之一。但是其優(yōu)化問題是一個非確定型的多項式問題，難以計算。螞蟻在給定蛋白質(zhì)序列隨機(jī)選擇一個起點，從這個起點出發(fā)，蛋白質(zhì)序列每一次像兩個方向折疊并增加一個氨基酸記號，這樣就構(gòu)成一個給定蛋白質(zhì)序列的候選構(gòu)型，可以用于本地搜索以實現(xiàn)進(jìn)一步的改進(jìn)，并且最終在更新信息素的基礎(chǔ)上找到優(yōu)質(zhì)的解。蟻群系統(tǒng)集成為一個意味著由傳遞局部最小和防止過早收斂組成的本地搜索元素。還可以采用多蟻群優(yōu)化（MACOS）算法，多個人工螞蟻群落并行解決HP蛋白質(zhì)折疊問題。（ACO）

（7）序列拼接問題（FAP）[18]。FAP基本上是一個置換問題，類似于TSP問題，不同之處在于噪音、個體之間的特殊關(guān)系等等。在本質(zhì)上FAP也是一個典型的NP完全問題。在單重疊群等問題中蟻群優(yōu)化算法優(yōu)于考慮多重疊群問題的最近鄰啟發(fā)式算法。（ACO）

2.2 群智能優(yōu)化算法的進(jìn)一步研究方向

還有許多可以應(yīng)用群智能優(yōu)化算法進(jìn)行研究的方向，現(xiàn)在幾乎還沒有什么研究進(jìn)展。在這些方面發(fā)表的論文數(shù)量很少，但是對未來的生物信息學(xué)研究有著重大的意義。我們注意到，群智能優(yōu)化算法尚未應(yīng)用到計算生物學(xué)的NP困難問題中去，這些問題迄今都沒有得到普遍可接受的解。這些問題有：

（1）識別基因調(diào)控網(wǎng)絡(luò)[19]。生物信息學(xué)研究領(lǐng)域中最具有挑戰(zhàn)性的問題之一就是從基于DNA微陣列技術(shù)得到的基因表達(dá)數(shù)據(jù)中推斷基因調(diào)控網(wǎng)絡(luò)?？梢杂肞SO非常有效地解決基因調(diào)控網(wǎng)絡(luò)的識別問題。每個粒子代表所有基因表達(dá)水平的實際價值。每個基因相對于另一個基因都有不同的特定表達(dá)水平。因此N個基因相當(dāng)于有N2個表達(dá)水平。粒子的適應(yīng)性可以從生成表達(dá)模式（表達(dá)模式的和）與目標(biāo)表達(dá)模式的絕對誤差計算出來。（PSO）

（2）蛋白質(zhì)三級結(jié)構(gòu)的預(yù)測和折疊[17,20]。一旦蛋白質(zhì)序列已經(jīng)確定，推斷其獨特的三維天然結(jié)構(gòu)是一項艱巨的任務(wù)。它需要完整的用從頭的方法接近蛋白質(zhì)三維結(jié)構(gòu)預(yù)測。從頭折疊的過程可分為兩部分：設(shè)計一個計分函數(shù)來從錯誤的（非天然的）結(jié)構(gòu)中區(qū)分出正確的/好的（天然的或者接近天然的）結(jié)構(gòu)；設(shè)計一個搜索方法探索構(gòu)象空間。（PSO）

（3）不同基因之間的代謝途徑的描述[21]。描述代謝途徑的目標(biāo)是估計一組“最佳”的參數(shù)值，最大限度地減少過程數(shù)據(jù)和代謝網(wǎng)絡(luò)模型之間的錯誤。這個參數(shù)估計問題可以歸為一個非凸的非線性的優(yōu)化問題，因此可以使用全局優(yōu)化技術(shù)解決。（PSO）

（4）計算機(jī)輔助分子設(shè)計（CAMD）[22-24]。如藥物設(shè)計開發(fā)——群智能優(yōu)化算法可以幫助設(shè)計一個配體分子，這個配體分子可以結(jié)合到目標(biāo)蛋白的活性位點上。（ACO）

3 總結(jié)與展望

隨著對基因組序列的注釋形成的數(shù)據(jù)爆炸性的增長，生物信息學(xué)已成為一門具有挑戰(zhàn)性和令人著迷的科學(xué)領(lǐng)域。它提出完美和諧的統(tǒng)計、生物學(xué)和計算智能方法來分析和處理在基因、DNA、RNA和蛋白質(zhì)形式存儲的生物信息。此外群智能優(yōu)化算法可以為研究人員對一些NP困難的問題在現(xiàn)實世界中尋找近似的最佳解決方案提供有力的幫助，獲得了廣泛的普及。生物信息學(xué)的問題很少需要精確的最佳解決方案，只需要強(qiáng)大的、快速的、近似的最佳解決方案。生物信息學(xué)的文獻(xiàn)調(diào)查顯示，這個領(lǐng)域需要有快速而強(qiáng)大的搜索機(jī)制來解決大量的問題。屬于這一類的問題包括多序列比對（MSA），蛋白質(zhì)二級和三級結(jié)構(gòu)的預(yù)測，蛋白配體對接，啟動子識別和進(jìn)化樹重構(gòu)等。古典確定性搜索算法和衍生為基礎(chǔ)的優(yōu)化技術(shù)對這些問題是沒有用的，因為它們的搜索空間可能會非常巨大并且是斷點不連續(xù)的。群智能優(yōu)化算法提供了一批多Agent并行搜索技術(shù)來非常有效的解決這類生物信息學(xué)相關(guān)問題。

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

[2]BONABEAU E,DORIGO M,THERAULAZ G.Swarm intelligence：from natural to artificial systems[M].New York：Oxford University Press,1999.

[3]張青，康立山，李大農(nóng).群智能算法及應(yīng)用[J].黃岡師范學(xué)院學(xué)報,2008,28(6)：44-48.

[4]CLOLRNI A,DORIGO M,MANIEZZO V.Distributed optimization by ant colonies[C]//Proceedings of the First European Conference on Artificial Life.London：MIT Press,1991：134–142.

[5]武飛周,薛源.智能算法綜述[J].工程地質(zhì)計算機(jī)應(yīng)用,2005(2)：9-15.

[6]KENNEDY J,EBERHART R.Particle swarm optimization[C]//IEEE Intl Conf on Neural Networks.Australia：Perth, 1995：1942–1948,

[7]EBERHART R,KENNEDY J.A new optimizer using particle swarm theory[C]//Proc of the Sixth International Symposium on Micro Machine and Human Science,Nagoya,Japan：1995：39–43,

[8]SHI Y,EBERHART R.Parameter selection in particle swarm optimization[C]//Proceedings of the Seventh Annual Conference on Evolutionary Programming.USA：New York,1998：591–600.

[9]尤曉清,邱矩平,林苗,等.仿生智能算法的比較分析[J].福建電腦,2009,25(1)：13-14.

[10]高倩倩.基因表達(dá)數(shù)據(jù)的聚類算法研究及其實現(xiàn)[D].無錫：江南大學(xué),2009.

[11]何書萍,李凡長.一個基于量子群的分子對接藥物設(shè)計算法[J].南京大學(xué)學(xué)報：自然科學(xué)版,2008,44(5)：512-519.

[12]段愛霞,陳晶,劉宏德,等.分子對接方法的應(yīng)用與發(fā)展[J].分析科學(xué)學(xué)報,2009,25(4)：473-477

[13]寧正元.計算機(jī)在生物科學(xué)研究中的應(yīng)用[M].廈門：廈門大學(xué)出版社,2006.

[14]寧靜,鐘一文,寧正元,等.基于rbcL蛋白質(zhì)序列的石斛屬植物系統(tǒng)發(fā)育研究[J].漳州師范學(xué)院學(xué)報：自然科學(xué)版, 2011(4)：34-39.

[15]寧正元,林世強(qiáng).RNA二級結(jié)構(gòu)預(yù)測方法[J].福建農(nóng)林大學(xué)學(xué)報：自然科學(xué)版,2007,36(1)：60-63.

[16]寧正元,林世強(qiáng).蛋白質(zhì)結(jié)構(gòu)的預(yù)測及其應(yīng)用[J].福建農(nóng)林大學(xué)學(xué)報：自然科學(xué)版,2006,：309-310.

[17]殷志祥.蛋白質(zhì)結(jié)構(gòu)預(yù)測方法的研究進(jìn)展[J].計算機(jī)工程與應(yīng)用,2004,40(20)：54-57.

[18]涂俐蘭,王能超,陳瑩,等.生物序列拼接及其算法[J].生命科學(xué)研究,2003,7(2)：79-82.

[19]蔣煒,彭新一,周育人.基于改進(jìn)PSO的基因調(diào)控網(wǎng)絡(luò)重構(gòu)方法[J].計算機(jī)工程,2009,35(20)：181-183.

[20]寧靜.蛋白質(zhì)結(jié)構(gòu)預(yù)測的多agent模擬退火算法研究[D].福州：福建農(nóng)林大學(xué),2012.

[21]呂麗麗,余永紅,孫俊,等.代謝途徑智能優(yōu)化的研究[J].計算機(jī)仿真,2011,28(11)：205-209.

[22]徐筱杰,侯廷軍,喬學(xué)斌,等.計算機(jī)輔助藥物分子設(shè)計[M]．北京：化學(xué)工業(yè)出版社,2004.

[23]李洪林,沈建華,王希誠,等.虛擬篩選與新藥發(fā)現(xiàn)[J].生命科學(xué),2005,17(2)：125-131.

[24]馮毅.生物信息學(xué)在藥物研發(fā)中的應(yīng)用與展望[J].西部醫(yī)學(xué),2007,19(5)：971-973.

[25]王翼飛,史定華.生物信息學(xué)—智能化算法及其應(yīng)用[M].北京：化學(xué)工業(yè)出版社,2005.

[26]寧正元,黃偉奇.生物數(shù)據(jù)標(biāo)準(zhǔn)化，從HTML到RDF[J].福建農(nóng)林大學(xué)學(xué)報：自然科學(xué)版,2007,36(2)：208-214.

[27]寧正元,王愛榮,王宗華,等.擬南芥DNA-J結(jié)構(gòu)域蛋白的生物信息學(xué)分析及其亞細(xì)胞定位驗證[J].福建農(nóng)林大學(xué)學(xué)報：自然科學(xué)版，2007,36(4)：427-434.

[28]鐘一文,楊建剛,寧正元.求解TSP問題的離散粒子群優(yōu)化算法[J].系統(tǒng)工程理論與實踐，2006，26(6)：88-94.

[29]鐘一文,蔡榮英,寧正元,等.一種改進(jìn)的離散粒子群優(yōu)化算法[J].小型微型計算機(jī)系統(tǒng)，2006，7(10)：1893-1896.

[30]王秀麗,寧正元.基于動態(tài)適應(yīng)度的獨立任務(wù)調(diào)度算法[J].計算機(jī)應(yīng)用,2006,26(12)：3001-3003

[31]寧正元,黃健,鐘一文,等.異構(gòu)環(huán)境獨立任務(wù)分配的導(dǎo)引式局部搜索算法[J].集美大學(xué)學(xué)報：自然科學(xué)版,2006,11 (2)：177-181.

An Overview of Swarm Intelligence Algorithms and Their Applications in Bioinformatics

NING Jing,ZHONG Yi-wen,LIN Juan,NING Zheng-yuan
(Computer and Information College,Fujian Agriculture and Forestry University,Fuzhou 350002,China)

Bioinformatics research requires the use of advanced computational tools to deal with a large number of biological vague and uncertain data.With the advantages of low cost,solving complex search problems fast,accurately and reasonably,swarm intelligence optimization algorithms become a group of heuristic algorithms which can be used to get a better solution to the bioinformatics problems.An overview of swarm intelligence optimization algorithms and their applications in bioinformatics are provided in this paper.

swarm intelligence;optimization algorithm;bioinformatics

TP301.6

A

1673-4343（2013）04-0013-06

2013-05-09

福建省自然科學(xué)基金（2008J0316）

寧靜，女，陜西咸陽人，助理實驗師。研究方向：智能計算、計算生物。通訊作者:寧正元，男，陜西武功人，教授。