結構尋優演算法

『壹』 什麼是禁忌搜索演算法

禁忌搜索演算法（Tabu Search或Taboo Search，簡稱TS演算法）是一種全局性鄰域搜索演算法，模擬人類具有記憶功能的尋優特徵。它通過局部鄰域搜索機制和相應的禁忌准則來避免迂迴搜索，並通過破禁水平來釋放一些被禁忌的優良狀態，進而保證多樣化的有效探索，以最終實現全局優化。
禁忌搜索演算法簡介
禁忌搜索（Tabu Search或Taboo Search，簡稱TS）的思想最早由Fred Glover(美國工程院院士，科羅拉多大學教授)提出，它是對局部領域搜索的一種擴展，是一種全局逐步尋優演算法，是對人類智力過程的一種模擬。TS演算法通過引入一個靈活的存儲結構和相應的禁忌准則來避免迂迴搜索，並通過藐視准則來赦免一些被禁忌的優良狀態，進而保證多樣化的有效探索以最終實現全局優化。相對於模擬退火和遺傳演算法，TS是又一種搜索特點不同的 meta-heuristic演算法。迄今為止，TS演算法在組合優化、生產調度、機器學習、電路設計和神經網路等領域取得了很大的成功，近年來又在函數全局優化方面得到較多的研究，並大有發展的趨勢。本章將主要介紹禁忌搜索的優化流程、原理、演算法收斂理論與實現技術等內容。

禁忌搜索演算法的基本思想
考慮最優化問題，對於X中每一個解x，定義一個鄰域N(x)，禁忌搜索演算法首先確定一個初始可行解x，初始可行解x可以從一個啟發式演算法獲得或者在可行解集合X中任意選擇，確定完初始可行解後，定義可行解x的鄰域移動集s(x)，然後從鄰域移動中挑選一個能改進當前解x的移動，s(x)，再從新解x』開始，重復搜索。如果鄰域移動中只接受比當前解x好的解，搜索就可能陷入循環的危險。為避免陷入循環和局部最優，構造一個短期循環記憶表——禁忌表(TabuList)，禁忌表中存放剛剛進行過的(稱為禁忌表長度)個鄰域移動，這些移動稱作為禁忌移動(Tabu Move)。對於當前的移動，在以後的T次循環內是禁止的，以避免回到原先的解，次以後釋放該移動。禁忌表是一個循環表，搜索過程中被循環的修改，使禁忌表始終保存著個移動。即使引入了一個禁忌表，禁忌搜索演算法仍有可能出現循環。因此必須給定停止准則以避免演算法出現循環。當迭代內所發現的最好解無法改進或無法離開它時，則演算法停止。
禁忌搜索示例
組合優化是TS演算法應用最多的領域。置換問題，如TSP、調度問題等，是一大批組合優化問題的典型代表，在此用它來解釋簡單的禁忌搜索演算法的思想和操作。對於 n元素的置換問題，其所有排列狀態數為n!，當n較大時搜索空間的大小將是天文數字，而禁忌搜索則希望僅通過探索少數解來得到滿意的優化解。
首先，我們對置換問題定義一種鄰域搜索結構，如互換操作（SWAP），即隨機交換兩個點的位置，則每個狀態的鄰域解有Cn2=n（n一1）/2個。稱從一個狀態轉移到其鄰域中的另一個狀態為一次移動（move），顯然每次移動將導致適配值（反比於目標函數值）的變化。其次，我們採用一個存儲結構來區分移動的屬性，即是否為禁忌「對象」在以下示例中：考慮7元素的置換問題，並用每一狀態的相應21個鄰域解中最優的5次移動（對應最佳的5個適配值）作為候選解；為一定程度上防止迂迴搜索，每個被採納的移動在禁忌表中將滯留3步（即禁忌長度），即將移動在以下連續3步搜索中將被視為禁忌對象；需要指出的是，由於當前的禁忌對象對應狀態的適配值可能很好，因此在演算法中設置判斷，若禁忌對象對應的適配值優於「 best so far」狀態，則無視其禁忌屬性而仍採納其為當前選擇，也就是通常所說的藐視准則（或稱特赦准則）。
可見，簡單的禁忌搜索是在領域搜索的基礎上，通過設置禁忌表來禁忌一些已經歷的操作，並利用藐視准則來獎勵一些優良狀態，其中領域結構、候選解、禁忌長度、禁忌對象、藐視准則、終止准則等是影響禁忌搜索演算法性能的關鍵。需要指出的是：
（1）首先，由於TS是局部領域搜索的一種擴充，因此領域結構的設計很關鍵，它決定了當前解的領域解的產生形式和數目，以及各個解之間的關系。
（2）其次，出於改善演算法的優化時間性能的考慮，若領域結構決定了大量的領域解（尤其對大規模問題，如TSP的SWAP操作將產生Cn2個領域解），則可以僅嘗試部分互換的結果，而候選解也僅取其中的少量最佳狀態。
（3）禁忌長度是一個很重要的關鍵參數，它決定禁忌對象的任期，其大小直接進而影響整個演算法的搜索進程和行為。同時，以上示例中，禁忌表中禁忌對象的替換是採用FIFO方式（不考慮藐視准則的作用），當然也可以採用其他方式，甚至是動態自適應的方式。
（4）藐視准則的設置是演算法避免遺失優良狀態，激勵對優良狀態的局部搜索，進而實現全局優化的關鍵步驟。
（5）對於非禁忌候選狀態，演算法無視它與當前狀態的適配值的優劣關系，僅考慮它們中間的最佳狀態為下一步決策，如此可實現對局部極小的突跳（是一種確定性策略）。
（6）為了使演算法具有優良的優化性能或時間性能，必須設置一個合理的終止准則來結束整個搜索過程。
此外，在許多場合禁忌對象的被禁次數（frequency）也被用於指導搜索，以取得更大的搜索空間。禁忌次數越高，通常可認為出現循環搜索的概率越大。
禁忌搜索演算法的流程
通過上述示例的介紹，基本上了解了禁忌搜索的機制和步驟。簡單TS演算法的基本思想是：給定一個當前解（初始解）和一種鄰域，然後在當前解的鄰域中確定若干候選解；若最佳候選解對應的目標值優於「best so far」狀態，則忽視其禁忌特性，用其替代當前解和「best so far」狀態，並將相應的對象加入禁忌表，同時修改禁忌表中各對象的任期；若不存在上述候選解，則選擇在候選解中選擇非禁忌的最佳狀態為新的當前解，而無視它與當前解的優劣，同時將相應的對象加入禁忌表，並修改禁忌表中各對象的任期；如此重復上述迭代搜索過程，直至滿足停止准則。
條理化些，則簡單禁忌搜索的演算法步驟可描述如下：
（1）給定演算法參數，隨機產生初始解x，置禁忌表為空。
（2）判斷演算法終止條件是否滿足？若是，則結束演算法並輸出優化結果；否則，繼續以下步驟。
（3）利用當前解工的鄰域函數產生其所有（或若干）鄰域解，並從中確定若干候選解。

（4）對候選解判斷藐視准則是否滿足？若成立，則用滿足藐視准則的最佳狀態y替代x成為新的當前解，即x=y，並用與y對應的禁忌對象替換最早進入禁忌表的禁忌對象，同時用y替換「best so far」狀態，然後轉步驟6；否則，繼續以下步驟。
（5）判斷候選解對應的各對象的禁忌屬性，選擇候選解集中非禁忌對象對應的最佳狀態為新的當前解，同時用與之對應的禁忌對象替換最早進入禁忌表的禁忌對象元素。
（6）轉步驟（2）。
禁忌搜索演算法流程的特點
與傳統的優化演算法相比，TS演算法的主要特點是：
（1）在搜索過程中可以接受劣解，因此具有較強的「爬山」能力；
（2）新解不是在當前解的鄰域中隨機產生，而或是優於「best so far」的解，或是非禁忌的最佳解，因此選取優良解的概率遠遠大於其他解。由於TS演算法具有靈活的記憶功能和藐視准則，並且在搜索過程中可以接受劣解，所以具有較強的「爬山」能力，搜索時能夠跳出局部最優解，轉向解空間的其他區域，從而增強獲得更好的全局最優解的概率，所以TS演算法是一種局部搜索能力很強的全局迭代尋優演算法。
禁忌搜索演算法的構成
禁忌搜索演算法是一種由多種策略組成的混合啟發式演算法。每種策略均是一個啟發式過程，它們對整個禁忌搜索起著關鍵的作用。禁忌搜索演算法一般由以下幾種策略組成:
(1)鄰域移動:鄰域移動是從一個解產生另一個解的途徑。它是保證產生好的解和演算法搜索速度的最重要因素之一。鄰域移動定義的方法很多，對於不同的問題應採用不同的定義方法。通過移動，目標函數值將產生變化，移動前後的目標函數值之差，稱之為移動值。如果移動值是非負的，則稱此移動為改進移動;否則稱作非改進移動。最好的移動不一定是改進移動，也可能是非改進移動，這一點就保證搜索陷入局部最優時，禁忌搜索演算法能自動把它跳出局部最優。
(2)禁忌表:不允許恢復即被禁止的性質稱作Tabu。禁忌表的主要目的是阻止搜索過程中出現循環和避免陷入局部最優，它通常記錄前若干次的移動，禁止這些移動在近期內返回。在迭代固定次數後，禁忌表釋放這些移動，重新參加運算，因此它是一個循環表，每迭代一次，將最近的一次移動放在禁忌表的末端，而它的最早的一個移動就從禁忌表中釋放出來。為了節省記憶時間，禁忌表並不記錄所有的移動，只記錄那些有特殊性質的移動，如記載能引起目標函數發生變化的移動。禁忌表記載移動的方式主要有三種:*記錄目標值；*移動前的狀態；*移禁忌搜索演算法在冷藏供應鏈配送網路中的應用研究動本身。
禁忌表是禁忌搜索演算法的核心，禁忌表的大小在很大程度上影響著搜素速度和解的質量。如果選擇的好，可有助於識別出曾搜索過的區域。實驗表明，如果禁忌表長度過小，那麼搜索過程就可能進入死循環，整個搜索將圍繞著相同的幾個解徘徊;相反，如果禁忌表長度過大，那它將在相當大的程度上限制了搜索區域，好的解就有可能被跳過，同時，不會改進解的效果而增加演算法運算時間。因此一個好的禁忌表長度應該是盡可能小卻又能避免演算法進入循環。禁忌表的這種特性非常類似於「短期記憶」，因而人們把禁忌表稱作短期記憶函數。
禁忌表另一個作用是通過調整禁忌表的大小使搜索發散或收斂。初始搜索時，為提高解的分散性，擴大搜索區域，使搜索路徑多樣化，經常希望禁忌表長度小。
相反當搜索過程接近最優解時，為提離解的集中性，減少分散，縮小搜索區域，這時通常希望禁忌表長度大。為達到這樣的目的，最近越來越多的人們允許禁忌表的大小和結構隨搜索過程發生改變，即使用動態禁忌表，實驗結果表明了動態禁忌表往往比固定禁忌表獲得更好的解。
(3)選擇策略:選擇策略即擇優規則，是對當前的鄰域移動選擇一個移動而採用的准則。擇優規則可以採用多種策略，不同的策略對演算法的性能影響不同。一個好的選擇策略應該是既保證解的質量又保證計算速度。當前採用最廣泛的兩類策略是最好解優先策略(Bestlmprovedstrategy)和第一個改進解優先策略(FirstImProvedstrategy)。最好改進解優先策略就是對當前鄰域中選擇移動值最好的移動產生的解，作為下一次迭代的開始。而第一個改進解優先策略是搜索鄰域移動時選擇第一改進當前解的鄰域移動產生的解作為下一次迭代的開始。最好改進解優先策略相當於尋找最陡的下降，這種擇優規則效果比較好，但是它需要更多的計算時間;而最快的下降對應尋找第一個改進解的移動，由於它無需搜索整個一次鄰域移動，所以它所花計算時間較少，對於比較大的鄰域，往往比較適合。
(4)破禁策略:破禁策略通常指渴望水平(Aspiration)函數選擇，當一個禁忌移動在隨後}T}次的迭代內再度出現時，如果它能把搜索帶到一個從未搜索過的區域，則應該接受該移動即破禁，不受禁忌表的限制。衡量標准就是定義一個渴望水平函數，渴望水平函數通常選取當前迭代之前所獲得的最好解的目標值或此移動禁忌時的目標值作為渴望水平函數。
(5)停止規則:在禁忌搜索中停止規則通常有兩種，一種是把最大迭代數作為停止演算法的標准，而不以局優為停止規則;另一種是在給定數目的迭代內所發現的最好解無法改進或無法離開它時，演算法停止。
(6)長期表:短期記憶用來避免最近所作的一些移動被重復，但是在很多的情況下短期記憶並不足以把演算法搜索帶到能夠改進解的區域。因此在實際應用中常常短期記憶與長期記憶相結合使用，以保持局部的強化和全局多樣化之間的平衡，即在加強與好解有關性質的同時還能把搜索帶到未搜索過的區域。
(7)在長期記憶中，頻率起著非常重要的作用，使用頻率的目的就是通過了解同樣的選擇在過去做了多少次來重新指導局部選擇。當在非禁忌移動中找不到可以改進的解時用長期記憶更有效。

目前長期記憶函數主要有兩種形式，一種通過懲罰的形式，即用一些評價函數來懲罰在過去的搜索中用得最多或最少的那些選擇，並用一些啟發方法來產生新的初始點。用這種方式獲得的多樣性可以通過保持懲罰一段時間來得到加強，然後取消懲罰，禁忌搜索繼續按照正常的評價規則進行。另一種形式採用頻率矩陣，使用兩種長期記憶，一種是基於最小頻率的長期記憶，另一種是基於最大頻率的長期記憶。通過使用基於最小頻率的長期記憶，可以在未搜索的區域產生新的序列;而使用基於最大頻率的長期記憶，可以在過去的搜索中認為是好的可行區域內產生不同的序列。在整個搜索過程中頻率矩陣被不斷的修改。
參考文獻
1.0 1.1 1.2 1.3 陳天絕.禁忌搜索演算法簡介
2.0 2.1 楊博.禁忌搜索演算法在冷藏供應鏈配送網路中的應用研究.2005.
許傳玉.系統可靠性優化研究及禁忌演算法在其中的應用.哈爾濱:哈爾濱理工大學.2000

『貳』 禁忌搜索局部領域搜索

局部領域搜索，基於貪婪策略，簡單易行，易於理解，但它在搜索性能上受限於初始解和領域結構。它容易陷入局部最優，而非全局最優。為了克服這個問題，可以採取多種策略：如模擬退火演算法，通過可控概率接受較差解來逃離局部極小；TSP的2opt方法可以擴展到k-opt，擴大搜索范圍；進化計算則提倡多點並行搜索；變結構領域搜索（Mladenovic等人，1997）也提供了一種創新方法。禁忌策略在TS中起著關鍵作用，它通過標記已探索的局部最優，避免重復搜索，採用確定性的策略來跳出局部極小，這是一種對不同有效搜索路徑的積極探索。

禁忌搜索作為人工智慧的一個分支，是對局部領域搜索的擴展。其核心理念是記錄已搜索過的局部最優解，並在後續搜索中避開它們，而非徹底禁止。這個過程涉及到臨域（neighborhood）、禁忌表（tabu list）、禁忌長度（tabu length）、候選解（candidate）以及藐視准則（aspiration criterion）等關鍵概念，它們共同作用於提升搜索的全局優化性能。

禁忌搜索（Tabu Search或Taboo Search，簡稱TS）的思想最早由Glover(1986)提出，它是對局部領域搜索的一種擴展，是一種全局逐步尋優演算法，是對人類智力過程的一種模擬。TS演算法通過引入一個靈活的存儲結構和相應的禁忌准則來避免迂迴搜索，並通過藐視准則來赦免一些被禁忌的優良狀態，進而保證多樣化的有效探索以最終實現全局優化。相對於模擬退火和遺傳演算法，TS是又一種搜索特點不同的 meta-heuristic演算法。

『叄』 詳細介紹雙序列比對、blast 以及多序列比對的區別,以及均適用於哪些場 景

序列比對是將兩個或多個序列排列在一起，標明其相似之處。使用間隔表示未比對上，比對上的相同或相似的符號排列在同一列上。序列比對是生物信息學以及基因組學與進化的基礎之一，其基本思想是：在生物學中普遍存在的序列決定結構、結構決定功能的規律，通過將核酸序列或者蛋白質序列的一級結構看成由基本字元構成的字元串，通過序列比對我們可以找到相似的序列並由此發現生物序列中的功能、結構和進化信息。
全局比對：全局比對是指將參與比對的兩條序列裡面的所有字元進行比對。全局比對在全局范圍內對兩條序列進行比對打分，找出最佳比對，主要被用來尋找關系密切的序列。其可以用來鑒別或證明新序列與已知序列家族的同源性，是進行分子進化分析的重要前提。其代表是Needleman-Wunsch演算法。
局部比對：與全局比對不同，局部比對不必對兩個完整的序列進行比對，而是在每個序列中使用某些局部區域片段進行比對。其產生的需求在於、人們發現有的蛋白序列雖然在序列整體上表現出較大的差異性，但是在某些局部區域能獨立的發揮相同的功能，序列相當保守。這時候依靠全局比對明顯不能得到這些局部相似序列的。其次，在真核生物的基因中，內含子片段表現出了極大變異性，外顯子區域卻較為保守，這時候全局比對表現出了其局限性，無法找出這些局部相似性序列。其代表是Smith-Waterman局部比對演算法。
雙重序列比對：雙序列比對是指對兩條序列M和N進行比對，找到其相似性關系，這種尋找生物序列相似性關系的過程被稱為雙序列比對。其演算法可以主要分成基於全局比對的Needleman-Wunsch演算法和基於局部比對的Smith-Waterman局部比對演算法
多重序列比對：多序列比對是雙序列比對推廣，即把兩個以上字元序列對齊，逐列比較其字元的異同，使得每一列字元盡可能一致，以發現其共同的結構特徵的方法稱為多序列比對。多序列比對演算法可以分成漸進法和同步法。其可以發現不同的序列之間的相似部分，從而推斷它們在結構和功能上的相似關系，主要用於分子進化關系，預測蛋白質的二級結構和三級結構、估計蛋白質折疊類型的總數，基因組序列分析等。
基因組比對：是多序列比對的一種特例，指對基因組范圍內的序列信息進行比對的過程。通過對不同親緣關系物種的基因組序列進行比較，能夠鑒定出編碼序列、非編碼調控序列及給定物種獨有的序列。而基因組范圍之內的序列比對，可以了解不同物在核苷酸組成、同線性關系和基因順序方面的異同，進而得到基因分析預測與定位、生物系統發生進化關系等方面的信息。
BLAST：BLAST[1]（Basic Local Alignment Search Tool）是在在1990年由Altschul等人提出的雙序列局部比對演算法，是一套在蛋白質資料庫或DNA資料庫中進行相似性比較的分析工具。BLAST是一種啟發式演算法，用於在大型資料庫中尋找比對序列，是一種在局部比對基礎上的近似比對演算法，可以在保持較高精度的情況下大大減少程序運行的時間。
演算法思想描述：
雙重序列比對主要分成以Needleman-Wunsch演算法為代表的全局比對和以Smith-Waterman局部比對演算法為代表的局部比對，BLAST是局部比對的一種推廣。多重比對演算法可以主要分成動態規劃演算法、隨機演算法、迭代法和漸進比對演算法。
（1）雙重序列比對：
Needleman-Wunsch演算法：該演算法是基於動態規劃思想的全局比對的基本演算法，動態規劃的比對演算法的比對過程可以用一個以序列S為列，T為行的(m+1)×(n+1)的二維矩陣來表示，用
sigma表示置換矩陣。
在計算完矩陣後，從矩陣的右下角單元到左上單元回溯最佳路徑（用箭頭表示），根據最佳路徑給出兩序列的比對結果。其中，斜箭頭表示2個殘基匹配，水平箭頭表示在序列S的相應位置插入一個空位，垂直方向的箭頭表示在序列T的相應位置插入一個空位。

Smith-Waterman演算法：該演算法是一種用來尋找並比較具有局部相似性區域的動態規劃演算法，這種演算法適用於親緣關系較遠、整體上不具有相似性而在一些較小的區域上存在局部相似性的兩個序列。該演算法的基本思想是：使用迭代方法計算出兩個序列的相似分值，存在一個得分矩陣M中，然後根據這個得分矩陣，通過動態規劃的方法回溯找到最優的比對序列。與全局比對相比，這種演算法的改變是把矩陣單元值為負者一律取為0，這是因為分值為負的比對喪失了比對的生物學意義，因此把得分為負值的子序列丟棄。

BLAST: BLAST演算法的基本思想是通過產生數量更少的但質量更好的增強點來提高比對的速度。演算法的原理主要分為以下五步：（1）過濾：首先過濾掉低復雜度區域，即含有大量重復的序列；（2）Seeding：將Query序列中每k個字組合成一個表，即將一個序列拆分成多個連續的『seed words』（通常蛋白質k=3，核酸k=11）；（3）比對：列出我們所關心的所有可能的字組，再配合置換矩陣給出高分值的字組並組織成快速搜索樹結構或者哈希索引，因此此步驟可以快速搜索出大數據集中的所有匹配序列，找到每個seed words在參考序列中的位置；（4）延伸：當找到seed words的位置後，接下來需要將seed word延伸成長片段，延伸過程中，得分值也在變化，當得分值小於閾值時即停止延伸，最後得到的片段成為高分片段對，HSP（High-scoring segment pair）；（5）顯著性分析，最後我們使用如下公式計算E值，E值衡量了在隨機情況下，資料庫存在的比當前匹配分數更好的比對的數目，因此可以用該值作為指標評價HSP比對序列的可信度。
其中，m是資料庫長度，n是query的長度，S是HSP分數，其他兩個參數是修正系數。

（2）多重序列比對

動態規劃演算法：其基本思想是將一個二維的動態規劃矩陣擴展到三維或者多維，多序列比對的積分是n個序列中兩兩進行比對所得積分之和。矩陣的維度反映了參與比對的序列數。這種方法對計算資源要求比較高[6]。
隨機演算法：主要包括遺傳演算法和模擬退火演算法，遺傳演算法是一類借鑒生物界進化規律演化來的全局意義上的自適應隨機搜索方法。當用遺傳演算法進行生物序列分析時，每一代包含固定數量的個體，這些個體用他們的適應度來評價。變異則模擬了生物進化過程中的偶然殘基突變現象。對產生的新一代群體進行重新評價、選擇、交叉、變異，如此循環往復，使群體中最優個體的適應度不斷提高，直到達到一個閾值，演算法結束。模擬退火的基本思想是用一物質系統的退火過程來模擬優化問題的尋優方法，當物質系統達到最小能量狀態時，優化問題的目標函數也相應地達到了全局最優解。這兩種方法都是對構造好的目標函數進行最優解搜索，但實際比對效果並不好[6,7]。
迭代法：迭代法的代表是Muscle[8], Muscle是一個新的漸進比對和迭代比對的綜合演算法，主要由兩部分構成，第一部分是迭代漸進比對：第一次漸進比對的目的是快速產生一個多序列比對而不強調准確率，以此為基礎再對漸進比對進行改良。經過兩次漸進比對，形成一個相對准確的多序列比對；第二部分是迭代比對：該過程類似於Prrp演算法[9]，即通過不斷的迭代，逐步優化最終比對結果。其主要特點包括：使用kmer counting進行快速的距離測量，使用一個新的圖譜比對打分函數進行漸進比對，使用依賴於數的有限分隔進行細化。
漸進比對演算法：該演算法以Feng和Doolittle提出的最為經典[10]。漸進比對演算法的基本思想是迭代地利用兩序列動態規劃比對演算法,先由兩個序列的比對開始，逐漸添加新序列，直到所有序列都加入為止。但是不同的添加順序會產生不同的比對結果。確定合適的比對順序是漸進比對演算法的一個關鍵問題。通常，整個序列的比對應該從最相似的兩個序列開始，由近至遠逐步完成。作為全局多序列比對的漸進比對演算法有個基本的前提假設:所有要比對的序列是同源的，即由共同的祖先序列經過一系列的突變積累，並經自然選擇遺傳下來的，分化越晚的序列之間相似程度就越高。因此，在漸進比對過程中，應該對近期的進化事件比遠期的進化事件給予更大的關注。由於同源序列是進化相關的，因此可以按著序列的進化順序，即沿著系統發育樹(指導樹)的分支，由近至遠將序列或已比對序列按雙序列比對演算法逐步進行比對，重復這一過程直到所有序列都己添加到這個比對中為止[10]。其三個步驟為：（1）利用雙序列比對方法對所有的序列進行兩兩比對，得到相似性分值；（2）利用相似性矩陣（或距離矩陣）產生輔助導向樹；（3）根據導向樹進行漸進比對。漸進比對演算法是最常用、簡單又有效的啟發式多序列比對方法，它所需時間較短、所佔內存較小，其演算法很多，主要有CLUSTAL W, T-Coffee和DiAlign等，其中 CLUSTAL W應用最廣泛。
應用：
類型+應用
雙重序列對比：判斷兩個序列的同源性和一致性。（1）全局多序列比對可以鑒別或證明新序列與己有序列家族的同源性;幫助預測新蛋白質序列的二級和二級結構，是進行分子進化分析的重要前提。適合序列相似性較高，序列長度近似時的比對；（2）局部比對考慮序列部分區域的相似性。局部多序列比對可以用來刻畫蛋白質家族和超家族。適合於未知兩個序列相似程度的，可能存在一些片段極其相似而另一些片段相異的序列比對情況。
多重序列比對：多重比對經常用來研究序列間的進化關系，構建進化樹；探究序列間的保守性。主要用於分子進化關系，預測蛋白質的二級結構和三級結構、估計蛋白質折疊類型的總數，基因組序列分析等。
基因組比對：通過對不同親緣關系物種的基因組序列進行比較，能夠鑒定出編碼序列、非編碼調控序列及給定物種獨有的序列。而基因組范圍之內的序列比對，可以了解不同物在核苷酸組成、同線性關系和基因順序方面的異同，進而得到基因分析預測與定位、生物系統發生進化關系等方面的信息。
其中，BLAST作為最重要的比對工具，意義特殊，拿出來單獨討論。BLAST可以分成Basic BLAST和 Specialized BLAST, BLAST包括常規的nucleotide blast, Protein blast和Translating blast；Specialize blast可以對特殊生物或特殊研究領域的序列資料庫進行檢索。

『肆』 人工魚群演算法有哪些

具體演算法如下：

1、起源人工魚群演算法是李曉磊等人於2002年在動物群體智能行為研究的基礎上提出的一種新型方盛優化演算法，該演算法根據水域中魚生存數目最多的地方就是本水域中富含營養物質最多的地方這一特點來模擬魚群的覓食行為而實現尋優。

2、演算法主要利用魚的三大基本行為：覓食、聚群和追尾行為，採用自上而下的尋優模式從構造個體的底層行為開始，通過魚群中各個體的局部尋優，達到全局最優值在群體中凸顯出來的目的。

3該方法採用自下而上的尋優思路，首先設計單個個體的感知、行為機制，然後將一個或一群實體放置在環境中，讓他們在環境的交互作用中解決問題。

4、生態學基礎在一片水域中，魚存在的數目最多的地方就是本水域富含營養物質最多的地方，依據這一特點來模仿魚群的覓食、聚群、追尾等行為，從而實現全局最優，這就是魚群演算法的基本思想。魚類活動中，覓食行為、群聚行為、追尾行為和隨機行為與尋優命題的解決有較為密切的關系，如何利用簡單有效的方式來構造和實現這些行為將是演算法實現的主要為題。

5、人工魚的結構模型人工魚是真實魚抽象化、虛擬化的一個實體，其中封裝了自身數據和一系列行為，可以接受環境的刺激信息，做出相應的活動。其所在的環境由問題的解空間和其他人工魚的狀態，它在下一時刻的行為取決於自身的狀態和環境的狀態，並且它還通過自身的活動來影響環境，進而影響其他人工魚的活動。