演化演算法應用於演化樹之建構

Evolutionary Algorithm for Constructing Evolutionary Trees

吳智銘(Wu Ze-Ming)

指導教授 ： 邱昭彰 ； 申生元

元智大學/資訊學院/資訊管理學系/碩士(2005年)

摘要

本研究提出一個以演化演算法來建構有根演化樹。演化樹為生物資訊領域中的分支，它是根據DNA或蛋白質序列所產生的二元樹狀結構，求取演化樹最佳解是NP-hard的問題，其中啟發式演算法最常被應用於組合最佳化問題。相關的方法有禁制搜尋法、蟻行演算法等。演化樹的解空間會隨著納入演化樹的物種數量而呈指數的增加，所以無法窮舉所有的演化樹。演化演算法透過了演化的概念有系統的搜尋解空間，可採用來解決演化樹最佳化問題。由於傳統的基因操作，會破壞樹型而產生不合法的演化樹，所以必須改善產生後代的方式。本研究採用的方式是選擇母體中好的演化樹，從好的演化樹中再萃取好的子樹，最後利用好的子樹組合成有效的演化樹，這樣的方式有機會可以找到更好的樹。

關鍵字

演化演算法 ； 生物資訊 ； 組合最佳化 ； 演化樹

並列摘要

This research presents an evolutionary algorithm for constructing rooted evolutionary trees. Constructing evolutionary tree is one branch of bioinformatics, it is a binary tree generated by DNA or protein sequences. Constructing an optimal evolutionary tree is a NP-hard problem. Heuristics often are applied to combinatorial optimization problem. Related solving techniques include tabu search, ant algorithm, and so on. The searching space of an evolutionary tree usually increases exponentially by species in a tree, so it is impossible to search all evolutionary trees. Evolutionary algorithm can search for space systematically by evolutionary concept, and it can be applied to optimize the construction of evolutionary trees. However, traditional genetic operators are not appropriate for the construction of a legal evolutionary tree. Thus the design of appropriate genetic operators becomes an important research issue. We try to initialize population, and select better evolutionary in population, then extract better sub-trees from a good evolutionary tree. Finally, sub-trees in the sub-tree pool are assembled into a legal evolutionary tree. The proposed method aims to achieve a better evolutionary tree.

並列關鍵字

evolutionary algorithms ； bioinformatics ； combinatorial optimization ； evolutionary tree