隨機最佳化方法於生物資訊科技之應用--以螞蟻演算法應用於最短超字串問題為例

遺傳基因對後代的疾病遺傳與對抗病毒等問題有著十分密切的關係。而於對抗病毒方面，噬菌體扮演著不可或缺的重要角色。然而生命體在細胞分裂時，由於基因的複製(replication)及轉錄(transcription)過程，會使得新一代的噬菌體產生突變現象。突變的噬菌體會喪失原本功能，而無法殺死細菌，這並不是我們所欲見的，且這個現象涉及了基因的重組和迴路問題。而基因重組問題已廣泛被視為是superstring（超字串）的問題。　　在遺傳工程學中，遺傳基因關係著後代的疾病遺傳與對抗病毒等問題。1950年代左右，噬菌體的基因組會在繁衍下一代的過程中突變，遺失基因組者，無法殺死細菌；重疊的兩基因組沒有迴路(overlap)，也無法對寄生的細菌產生致命的危險。而對於如何使重要基因組不會遺失且兩重疊基因組需產生迴路的問題，其形同演算法中的最短超字串問題(The Shortest Superstring problem, SSP)。　　最短超字串問題的目的在找出一個長度最短的超字串(superstring)，這個超字串包含了所給予的字串集合中的所有子字串(substring)。最短超字串問題多被應用在資料壓縮問題上，後來更被應用在DNA排序的問題上[23]，在演算法中，其屬於NP-hard的問題[23,27,28]。　　在解決NP-hard的問題上，近代有許多最佳化方法被探討，包括了：螞蟻演算法、基因演算法、模擬退火法、或一些啟發式演算法等等。其中，螞蟻演算法(Ant colony optimization, ACO)約於1990年代被提出，對於複雜難解的組合性最佳化問題，其所求出的最佳解被驗證可以非常地近似實際最佳解，尤其應用在TSP問題上最具成效。而最短超字串問題可視為一個漢米爾頓迴路[27]，TSP問題又為漢米爾頓迴路中的一個特例，因此，本研究試圖利用螞蟻演算法來解最短超字串問題，並實驗及探討其對此問題的影響，以及其所求之最佳解的品質。

關鍵字

最短超字串問題；螞蟻演算法

並列摘要

Bioinformatics has received wide attention in recent years. It is interesting to see how stochastic optimization methodologies such as genetic algorithm, simulated annealing and ant colony optimization, that can be applied to solve problems in bioinformatics. Among many research problems in bioinformatics, the shortest superstring problem has wide applications in many research areas, such as DNA sequencing and data compression. However, the problem is NP-hard and difficult to solve efficiently. In the literature, the ant colony optimization algorithm has been reported to be successfully applied to many combinatorial problems, such as the traveling salesperson problem and the assignment problem. In this paper, we describe the use of the ant colony optimization algorithm to solve the shortest superstring problem, which highlights a way for applying stochastic optimization methodologies to solve problem in bioinformatics.

並列關鍵字

Ant Colony Optimization ； Ant System ； the Shortest Superstring Problem

參考文獻

[6] 陳永展，建構缺損型供應鏈生產規劃架構，碩士論文，國立台北科技大學工業工程與管理系碩士班，2006

[21] Hung-Wei Huang, “Solving the Traveling Salesman Problem by Ant Colony Optimization Algorithms with DNA Computing”, 碩士論文，國立中山大學資訊工程學系碩士班，2004

[13] Adil B., Turkay D., and Ibrahim S., “An ant colony algorithm for solving budget constrained and unconstrained dynamic facility layout problems”, Omega, 34, 2006, pp.385-396.

[17] Dorigo, M. and Blum, C., “Ant colony optimization theory”, A survey. Theoretical Computer Science, 344, 2005, pp. 243-278.

[18] Dorigo, M. and Gambardella, L. M., “Ant colonies for the traveling salesman problem”, BioSystems, 43, 1997, pp. 73-81.

國際替代計量

隨機最佳化方法於生物資訊科技之應用--以螞蟻演算法應用於最短超字串問題為例

全文下載

主題瀏覽