[[alternative]]Analysis and comparison of the construction methods for phylogenetic trees

碩士[[abstract]]在過去，生物分類學家以生物的形態及生理特徵做為物種分類的依據，再佐以解剖學或化石來驗證物種之間的關係，並依照物種的相互關係畫出演化樹。在發現生物分子序列後，科學家嘗試利用這些分子序列來分析物種間的相互關係，並陸續發展出各種不同的方法來建立演化樹。而利用演化樹分析基因間的關係，在生物科技研究方面也扮演重要的角色。本論文將研究5種演化樹建立方法：無權重群組算數平均法 (UPGMA) 、Fitch-Margoliash (FM) 法、鄰點加入法 (NJ) 、最大吝嗇度法 (MP) 及最大可能性法 (ML) ，以及一些評估方法的基本理論﹔然後再利用現有之軟體，對不同的分子序列資料來推導演化樹，比較各種建立演化樹方法所需之執行時間，以bootstrapping統計方法來評估所建立演化樹可能出現的機率。另外再依據模型樹模擬操作分類單元 (OTU，operational taxonomic unit) 的序列資料，用各種方法推導出演化樹後再與模型樹比較正確度，以此比較各種建立演化樹方法之差異。實際的實驗利用seqgen程式及PHYLIP現有之軟體進行，在改變OTU數目比較執行時間的實驗後發現，徹底搜尋法dnaml (ML) 、dnapars (MP) 、fitch (FM) 三者以MP的執行速度較快，FM法在OTU個數少時較ML快，但超過30個OTU後就比ML慢。逐步群集法NJ與UPGMA二者中以UPGMA較快。在準確度分析方面發現5種演化樹建立方法各有優缺點，整體而言在OTU序列長度越小時，ML表現比其他方法好，OTU序列長度越長時，FM與NJ表現較好。[[abstract]]In the past, the biological taxonomist classified the organisms according to the morphological and physiological characters, and confirmed the relationship of species by anatomy or fossils. Then, an evolutionary tree was drawn to show the relationship of species. After discovering the biological molecular sequences, the scientists have attempted to analyze the relationship between taxa by their molecular sequences, and continually developed different methods for constructing phylogenetic trees. And using the phylogenetic trees to analyze the relationship between genes plays an important role in the biotechnology area. This thesis studies the elementary theories of five construction methods (ML, MP, FM, NJ and UPGMA) and evaluation methods for phylogenetic trees. Then, the software on the Web is used to construct the phylogenetic trees with different molecular sequence data. The execution time of different methods is compared. Bootstrapping is used to estimate the appearance probability of inferred trees from the construction methods. Moreover, a model tree is used to simulate the sequence data of operational taxonomic units (OTUs). Phylogenetic trees are reconstructed with the generated data by the five construction methods, and are compared with the model (correct) tree. The correctness of the phylogenetic tree by the five methods is then analyzed. The ‘seqgen’ program and the software on the PHYLIP are used to perform the experiments. From the results of the experiment of execution time with different OTU numbers, the MP method is the fastest one in the three exhaustive methods. The FM method is faster than ML with smaller OTU numbers but slower than ML when the OTU number is over thirty. The UPGMA method is faster than NJ in the two stepwise clustering methods. In the aspect of accuracy analysis, the five methods have respective advantages and disadvantages. In general, the ML method is better than others with shorter OTU sequence lengths, the FM and NJ methods are better than others with longer OTU sequence lengths.[[tableofcontents]]第一章 簡介 1 1-1 研究動機與目的 1 1-2 相關術語及名詞 3 1-3 分子序列之距離 14 1-4 演化樹建立方法之分類 17 第二章 演化樹建立方法 21 2-1 無權重群組算數平均法 21 2-2 FM (Fitch and Margoliash) 法 24 2-3 鄰點加入法 29 2-4 最大吝嗇度 37 2-5 最大可能性 40 第三章 網路資源 45 3-1 演化樹相關軟體 45 3-2 國家衛生研究院 46 3-3 線上資料庫 47 3-4 Seq-Gen：序列產生軟體 49 第四章 演化樹之評估方法 52 4-1 樹的距離 (tree distance) 52 4-2 統計方法bootstrapping 56 第五章 實驗及結果 60 5-1 執行時間之比較 60 5-1-1 不同分子序列長度 61 5-1-2 不同OTU數目 66 5-2 統計分析 68 5-3 準確度分析 72 第六章 結論與未來研究方向 78 6-1 結論 78 6-2 未來研究方向 79 參考文獻 80 附錄 英文論文86 表目錄 表1.1 N個OTU可建立的無根樹與有根樹數目 7 表1.2 序列1至序列4間之距離矩陣 16 表1.3 Parsimony之演化樹軟體 17 表1.4 距離矩陣之演化樹軟體 18 表1.5 ML與貝氏定理之演化樹軟體 18 表1.6 Quartet之演化樹軟體 19 表1.7 Compatibility之演化樹軟體 19 表1.8 AI及GA之演化樹軟體 19 表2.1 A、B、C及D之距離矩陣 22 表2.2 (AC)、B及D之距離矩陣 23 表2.3 A、B、C、D之距離矩陣 25 表2.4 A、B與CD之距離矩陣 25 表2.5 AB群組與C、D之距離矩陣 26 表2.6 A、C、BD之距離矩陣 27 表2.7 AC群組後與B、D之距離矩陣 28 表2.8 A、B、C、D、E之距離矩陣 33 表2.9 A、B與 (CDE) 之距離矩陣 34 表2.10 AB互為鄰點與C、D、E之距離矩陣 34 表2.11 (AB)、C、(DE)之距離矩陣 35 表2.12 (AB)、C為鄰點與D、E之距離矩陣 36 表2.13 4個OTU之分子序列 37 表5.1 TreeBASE之M884原始名稱與修改後名稱對照表 62 表5.2 ML法與MP法在不同序列長度之執行時間 65 表5.3 不同方法在不同OTU數之執行時間 67 表5.4 NJ法與 UPGMA法在不同OTU數之執行時間 68 表5.5 5種方法其一致樹之距離關係 72 表5.6 各演化樹建立方法在高演化速率之準確度分析(%) 76 表5.7 各演化樹建立方法在低演化速率之準確度分析(%) 77 圖目錄 圖1.1 有根演化樹 4 圖1.2 無根演化樹 5 圖1.3 刻度樹與非刻度樹 5 圖1.4 3 OTUs 之無根演化樹與有根演化樹 7 圖1.5 基因樹與物種樹之關係 9 圖1.6 Jukes與 Cantor所提出之核苷酸置換模型 10 圖1.7 Kimura之兩參數核苷酸置換模型 13 圖1.8 含3個邊長為a,b,c之演化樹 16 圖2.1 以UPGMA所建立之演化樹 23 圖2.2 A、B與 (CD) 之關係 25 圖2.3 (AB) 與C、D之關係 26 圖2.4 (AB) 與C、D所構成之演化樹 27 圖2.5 A、C與 (BD) 之關係 27 圖2.6 (AC) 與B、D之關係 28 圖2.7 (AC) 與B、D所構成之演化樹 29 圖2.8 A、B互為鄰點，C、D互為鄰點 30 圖2.9 星狀樹 31 圖2.10 挑出兩點互為鄰點 31 圖2.11 A、B、C、D、E之星狀樹 33 圖2.12 A、B為鄰點與其他點之關係 34 圖2.13 (AB) 群組與C為鄰點與其他點之關係 35 圖2.14 (ABC) 群組與其他點之關係 36 圖2.15 4個OTU可決定3棵演化樹 37 圖2.16 3棵演化樹在位置1核苷酸變化情形 38 圖2.17 3棵演化樹在位置2核苷酸變化情形 38 圖2.18 3棵演化樹在位置3核苷酸變化情形 38 圖2.19 3棵演化樹在位置4核苷酸變化情形 39 圖2.20 3棵演化樹在位置5核苷酸變化情形 39 圖2.21 3棵演化樹在位置6核苷酸變化情形 39 圖2.22 3個OTU之演化樹及演化路徑 41 圖2.23 由z演化至Xu1 、Xu2的演化樹 42 圖4.1 有3個內部邊的演化樹 53 圖4.2 兩棵由5個OTU所組成的演化樹 54 圖4.3 比較兩棵樹之子樹集合 55 圖4.4 原始資料、取樣資料與推導樹 57 圖4.5 統計次數最高的演化樹 58 圖4.6 執行 consense程式輸出檔之部份資料 59 圖5.1 在Dos下執行Seqgen部份畫面 64 圖5.2 比較ML與MP法在不同序列長度之執行時間 66 圖5.3 各演化樹建立方法在不同OTU個數之執行時間 68 圖5.4 ML法之一致樹 69 圖5.5 MP法之一致樹 70 圖5.6 FM法之一致樹 70 圖5.7 NJ法之一致樹 71 圖5.8 UPGMA法之一致樹 71 圖5.9 A、B、C、D模型樹 73[[note]]學號: 792190091, 學年度: 9