臺灣博碩士論文加值系統

建構演化樹是分析物種間演化過程，最基本及重要的工具。現今的演化樹建構工具相當豐富，但是不同工具得到的演化樹也不盡相同。
本篇論文首先選出十個當前大家常用的演化樹建構工具，及十個不同的物種群。利用演化樹RF距離演算法，評估出PHYLIP及ClustalW為最佳的兩個演化樹建構工具。
接著設計演化樹合併演算法，合併上述兩個工具所得到的演化樹，並証明所得到的新演化樹，評估RF(Robinson-Foulds)距離為最佳。最後利用實驗的結果，驗證我們的演化樹建構工具，為當今評估RF距離之最佳演化樹建構工具。

Construction of phylogenetic tree is the most basic and important tool to analyze the evaluated process among objects. There are many tools of phylogenetic tree construction, each tool does not construct the same phylogenetic tree.
In this paper, we first select 10 popular tools of phylogenetic tree construction and 10 groups of objects, measure their RF(Robinson-Foulds) distances to decide the first two optimal tools are PHYLIP and ClustalW.
And then we derive algorithm to combine the above two phylogenetic trees, and prove the combined tree is the optimal of measuring RF distance. The experimental results finally show that our tool is the optimal.

目 錄

中文摘要.............................Ⅰ
英文摘要.............................Ⅱ
誌謝.................................Ⅲ
目錄.................................Ⅳ
圖示列表.............................Ⅵ


第一章 導論 ........................1
1.1 何謂演化樹 ...........1
1.2 演化樹的分類 ..........4
1.3 研究目的 .............8
1.4 研究流程 .............9
第二章 演化樹建構工具 ..................11
2.1 Phylip (PHYLogeny Inference Package) ............12
2.2 ClustalW ............................................14
2.3 MEGA (Molecular Evolutionary Genetic Analysis) ...16
2.4 Spectrum ..............................................18
2.5 PTP (Phylogenetic Tree Project) ...................20
2.6 START2 (Sequence Type Analysis and Recombinational Tests Version 2) .......................21
2.7 Splitstree ..................................22
2.8 Swaap ....................................23
2.9 T-REX (Tree Reconstruction) .......................24
2.10 Wet (Windows Easy Tree) .....................25
2.11 十組演化樹工具之歸納與整理 ....................26
第三章 演化樹之評估與合併 ....................28
3.1 RF距離的計算方法 ............................28
3.2 演化樹的合併 ......................................33
3.3 合併演算法之定理與證明 .............................38
第四章 最佳演化樹建構工具 ...............................41
4.1 利用RF距離評估最佳演化樹 .........................41
4.2 最佳演化樹建構工具評估演算法 ........................47
4.3 實驗結果:演化樹建構工具之現況分析 ..............49
4.4 利用RF距離評估之最佳演化樹建構工具 .................57
第五章 結論 ......................................61
5.1 研究成果 ...........................61
5.2 未來研究方向 ..........................62
參考文獻 .............................63

[1]T. Jiang, E. Lawler, and L. Wang, “Aligning sequences via an evolutionary tree: complexity and approximation”, In Proceedings of the Twenty-Sixth Annual ACM Symposium on the Theory of Computing ACM, pp. 760-769,1994.
[2]S. Kannan, and T. Warnow, “Inferring evolutionary history from DNA sequences”, SIAM Journal on Computing, pp. 713-737, 1994.
[3]L. Klotz, and R. Blanken, “A practical method for calculating evolutionary trees from sequence data”, Journal of Theoretical Biology, pp. 261-272, 1981.
[4]W. Day, “Computational complexity of inferring phylogenies by dissimilarity matrices”, Bulletin of Mathematical Biology, Vol. 49, No. 4, pp. 461-467, 1987.
[5]W. Day, and D. Sankoff, “Computational complexity of inferring phylogenies by compatibility”, Systematic Zoology, vol. 35, No. 2, pp. 224-229, 1986.
[6]D. Robinson, and L. Foulds, “Mathematical Biosciences”, vol. 53, pp. 131–147, 1981.
[7]D. Sankoff, “Minimal mutation trees of sequences”, SIAM Journal on Applied Mathematics, vol. 28, pp. 35-42, 1975.
[8]R. Agarwala, and D. Fernandez-Baca, “A polynomial- time algorithm for the perfect phylogeny problem when the number of character states is fixed”, SIAM Journal on Computing, pp. 1216-1224, 1994.
[9]J. Hein, “An optimal algorithm to reconstruct trees from additive distance data”, Bulletin of Mathematical Biology, pp. 597-603, 1989.
[10]S. Altschul, and D. Lipman, “Trees, stars, and multiple biological sequence alignment”, SIAM Journal of Applied Mathematics, vol. 49, pp. 197-209, 1989.
[11]L. Cavalli-Sforza, and A. Edwards, “Phylogenetic analysis: models and estimation procedures”, Evolution, vol. 32, pp. 233 –257, 1967.
[12]L. Joseph, Thorley, and D. Roderic, “RadCon：Phylogenetic tree comparison and consensus”, Bioinformatics, vol. 16, pp. 486-487, 2000.
[13]C. Korostensky, and G. H. Gonnet, “Using traveling salesman problem algorithms for evolutionary tree construction”, Bioinformatics, vol. 16, pp. 619-627, 2000.
[14]A. Meade, D. Corne, M. Pagel, and R. Sibly, “Using Evolutionary Algorithms to Estimate Transition Rates of Discrete Characteristics in Phylogenetic Trees”, Congress of Evolutionary Computation, pp. 1170-1176, IEEE 2001.
[15]K. Ming-Yang, “Tree Contractions and Evolutionary Trees”, SIAM Journal on Computing, pp. 1592-1616, December 1998.
[16]D. Sankoff, “Minimal mutation trees of sequences”, SIAM Journal on Applied Mathematics, vol. 28, pp. 35-42, 1975.
[17]D. Robinson, and L. Foulds, “Mathematical Biosciences”, vol. 53, pp. 131–147, 1981.
[18]朱廷翰，利用RF距離評估演化樹及合併演化樹演算法，中華大學資訊工程研究所，2005.