การประยุกต์ใช้ Cluster Analysis ในการแก้ปัญหาเกี่ยวกับการสร้าง Evolutionary Tree

Application of Cluster Analysis for Evolutionary Tree Construction

Name: จุฑากานต์ พรหมวิชิต

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

keyword: Evolutionary Tree Construction

; NP-Hard Problem

; Clustering Analysis

Abstract: Evolutionary tree construction is classified as an NP-hard problem since the size of problem will grow exponentially with the number of species and it cannot be solved exactly in polynomial time. Therefore, divide and conquer strategies are introduced in this work in order to reduce the complexity of this problem to polynomial time. One method that can be applied for dividing the size of this problem is clustering analysis. In this work, clustering analysis is used to classify all species into k subclusters. Tree configurations of each subcluster are calculated before regrouping these subclusters into one group. Finally an evolutionary tree of all species is obtained. The proposed algorithm for solving evolutionary tree is developed using MATLAB software. There are 2 main parts of the proposed algorithm. The first is the clustering algorithm. Pairwise distance, which is obtained from CLUSTAL X software, initial number of cluster (K), and maximum species of subcluster are input data of this algorithm. The clustering results, k subclusters, are then used to calculate branch length and grouped into closer groups in the regrouping step. In the case of group(s) containing too many subclusters, a recursive method is introduced in order to subdivide the large group to small subgroups. In addition, the order for regrouping each subgroup is obtained from the recursive method. The proposed algorithm is tested with 9 sets of sequences. Comparing the results of proposed algorithm with the results of Neighbor Joining method shows that the proposed algorithm provides longer evolutionary trees than the Neighbor Joining method by about 4 -12 percent. Even though an optimum solution is not obtained, the proposed algorithm can solve evolutionary tree problems with many species (for instance; 40 species) in polynomial time. Also, the complexity of this algorithm is O (n2).Therefore, it can be concluded that an optimum solution is traded off with the computation requirment for evolutionary tree construction.

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

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

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

Name: Lect. Wiwat Ruenglertpanyakul

Role: Supervisor

Created: 2546

Issued: 2005-09-19

Modified: 2006-05-09

ISBN: 9741383458

CallNumber: CHE1427

tha

DegreeName: Master of Engineering

Level: Master's Degree

Descipline: Chemical Engineering

Grantor: King Mongkut's University of Technology Thonburi

©copyrights

ลำดับที่.	ชื่อแฟ้มข้อมูล	ขนาดแฟ้มข้อมูล	จำนวนเข้าถึง	วัน-เวลาเข้าถึงล่าสุด
1	CHE1427.pdf	1.25 MB	160	2025-03-18 12:18:41
2	CHE1427ab.pdf	50.51 KB	55	2020-08-09 04:38:20
3	CHE1427ab.txt	2.33 KB	58	2018-10-27 15:10:07

ใช้เวลา

0.043222 วินาที