การประยุกต์การหาสภาวะเหมาะสมโดยการใช้อาณาจักรมดจำลองในการสร้างแผนภูมิวิวัฒนาการ

Application of Ant Colony Optimization toEvolutionary Tree Construction

Name: พิศิษฐ์ คำหน่อแก้ว

Organization : มหาวิทยาลัยเทคโนโลยีพระจอมเกล้าธนบุรี

keyword: Evolutionary Tree

; Phylogeny

; Ant Colony Optimization

Abstract: Evolutionary tree (also called phylogenetic tree) is an interesting topic in theevolutionary study. This thesis proposes a new evolutionary tree construction algorithmthat constructs a tree with minimum total branch lengths for a given pairwise distance ofinput species. The problem of evolutionary tree, which is NP-complete, is transformedinto the Steiner's tree problem, i.e., to find the minimum length tree connecting all leafnodes. Ant Colony Optimization (ACO), a heuristic method, is applied to this problemwhich differs from the exact method of dynamic programming. To deal with thisproblem, a new procedure of tree construction, branch length calculation, and branchpoint selection are developed. ACO is used in the branch point selection. A new ACOparameter called distance-weighting parameter, K, is implemented to deal with distancecalculation between two branch points. The outputs of this algorithm are branch labelsand their length that are sufficient to construct an evolutionary tree.The developed algorithm can reduce the search space of the problem to polynomialcalculation time with complexity at the order of o(Nc.n4) ,where n is the number ofinput species and Nc is the number of iterations. When compared to the popularNeighbor Joining (NJ) method, the results from the new developed algorithm are better(shorter total distances) than NJ methods for 18 from 19 of the test cases.

มหาวิทยาลัยเทคโนโลยีพระจอมเกล้าธนบุรี

Address: กรุงเทพมหานคร (Bangkok)

Email: info.lib@mail.kmutt.ac.th

Name: Lect. Hong Ming Ku

Role: Supervisor

Created: 2545

Issued: 2005-10-28

Modified: 2006-05-10

วิทยานิพนธ์/Thesis

ISBN: 9749605438

CallNumber: CHE1265

tha

DegreeName: วิศวกรรมศาสตรมหาบัณฑิต

Level: ปริญญาโท

Descipline: วิศวกรรมเคมี

Grantor: มหาวิทยาลัยเทคโนโลยีพระจอมเกล้าธนบุรี

©copyrights มหาวิทยาลัยเทคโนโลยีพระจอมเกล้าธนบุรี

ลำดับที่.	ชื่อแฟ้มข้อมูล	ขนาดแฟ้มข้อมูล	จำนวนเข้าถึง	วัน-เวลาเข้าถึงล่าสุด
1	CHE1265.pdf	3.89 MB	123	2021-11-07 12:15:31
2	CHE1265ab.pdf	69.64 KB	37	2020-04-23 23:57:27
3	CHE1265ab.txt	1.7 KB	42	2020-04-23 23:58:07

ใช้เวลา

0.025065 วินาที