跳到主要內容

臺灣博碩士論文加值系統

(44.213.60.33) 您好!臺灣時間:2024/07/22 16:16
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:林陳輝
研究生(外文):Chen-Hui Lin
論文名稱:測量混合樹之間的距離之研究
論文名稱(外文):A Study on Measuring Distance between Two Mixture Trees
指導教授:阮夙姿
指導教授(外文):Justie Su-Tzu Juan
學位類別:碩士
校院名稱:國立暨南國際大學
系所名稱:資訊工程學系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2008
畢業學年度:96
語文別:英文
論文頁數:42
中文關鍵詞:演化樹混合樹距離樹的比較配對距離
外文關鍵詞:phylogenetic treeevolutionary treemixture treedistancetree comparisonmatching distance
相關次數:
  • 被引用被引用:0
  • 點閱點閱:271
  • 評分評分:
  • 下載下載:7
  • 收藏至我的研究室書目清單書目收藏:0
演化樹是一種描述物種演化關係的樹狀圖,在圖上我們可以看出老虎跟貓的祖先是同一種生物。這樣的樹可以經由物種資訊計算得到,藉由電腦的高速計算我們可以得到大量計算出來的演化樹,在統計學上二棵樹之間的相似程度是值得被討論的。樹狀圖的比較是測量兩樹狀圖的相似程度,這是在生物資訊上重要的議題。
混合樹是在2006年由Chen和Lindsay提出的重要演化樹。混合樹帶有比傳統的演化樹更多的資訊,例如突變點的時間、突變的方式。我們感興趣的是混合樹之間的相似程度。雖然已經有很多測量二個樹狀圖之間距離的方法被提出,但是至今仍沒有一個適合用以比較兩棵混合樹。在本篇論文中,我們首先定義了一個新的測量混合樹之間距離的方式 - 混合距離,並且發展了一個$O(n^2)$的演算法。接著改進這個演算法使其時間複雜度縮減為$O(nlog n)$。其次本論文修改了前人所定義的配對距離,這是用以測量二個樹狀圖之間的距離方法。改進後的混合-配對距離,將可用以測量兩棵混合樹之間的距離。同樣地,我們也給了一計算兩棵混合樹之混合-配對距離的演算法並且維持其時間複雜度仍是$O(n)$。
Phylogenetic tree is a tree to describe the relationship of species. For example, we can know that the tiger and the cat belong to the same family from the phylogenetic tree. It can be constructed by species information. There are many methods to building phylogenetic trees. How to know two trees are similar or not and how can one describe the amount of difference between two trees? That is why we need tree comparison metric. Tree comparison metric is to measure similarity for the phylogenetic trees, and it is an important topic in bioinformation. Mixture trees is held in 2006 by Chen and Lindsay. It has more information than traditional phylogenetic tree, for example, it shows time parameter in the point of species mutation occurs. There are many proposed metrics for the trees comparison, but no one fits to solve the tree comparison between two mixture trees up to now. We are interesting how similar between two mixture trees is. In this thesis, we define a new metric, mixture distance, to measure similarity between two mixture trees at first. Then, we develop an algorithm in time O(n2) for mixture distance and improve the algorithm to time O(n log n). Secondly, we also modify the matching distance, that is a metric for traditional phylogenetic trees, and get another new metric, mixture-matching distance, that will more fit to measure the distance between two mixture trees. Also we give an algorithm in time O(n) for calculating the mixture-matching distance between two mixture trees.
Abstract in Chinese . . . . . . . . . . . . . . . . . . . . . . . . . I
Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . II
Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . IV
List of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . VI
List of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . .VII
1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 Preview This Thesis . . . . . . . . . . . . . . . . . . . . . . 6
2 Preliminary . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.1 Some Definitions of Graph . . . . . . . . . . . . . . . . . . . 7
2.2 Useful Algorithms . . . . . . . . . . . . . . . . . . . . . . . 9
3 Mixture Distance . . . . . . . . . . . . . . . . . . . . . . . . 12
3.1 The Definition of Mixture Distance . . . . . . . . . . . . . . . 12
3.2 An Algorithm for Mixture Distance . . . . . . . . . . . . . . . 13
3.2.1 The Basic Algorithm for Mixture Distance . . . . . . . . . . . . 13
3.2.2 An Example . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.2.3 Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.3 The Modified Algorithm for Mixture Distance . . . . . . . . . . 23
3.3.1 The Modified Algorithm . . . . . . . . . . . . . . . . . . . . . 23
3.3.2 An Example of the Modified Algorithm . . . . . . . . . . . . . . 26
3.3.3 Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
4 Mixture-Matching Distance . . . . . . . . . . . . . . . . . . . 31
4.1 The definition and algorithm for Mixture-Matching Distance . . . 31
4.2 An Example of Mixture-Matching Distance . . . . . . . . . . . . 33
4.3 Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
5 Conclusions and Future Work . . . . . . . . . . . . . . . . . . 38
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
[1] M. A. Bender and M. Farach-Colton, "The lca problem revisited," Latin
American Theoretical Informatics, pp. 88{94, 2000.
[2] L. Billera, S. Holmes, and K. Vogtman, "Geometry of the space of phyloge-
netic trees," Advances in Applied Mathematics, Vol. 27, No. 4, pp. 733{767,
1999.
[3] J. Bluis, J. Bluis, and D. Shin, Nodal distance algorithm: calculating a
phylogenetic tree comparison metric," Proceedings of the Third IEEE Sym-
posium on BioInformatics and BioEngineering, pp. 87{94, 2003.
[4] G. S. Brodal, R. Fagerberg, and C. N. S. Pedersen, "Computing the quar-
tet distance between evolutionary trees in time O(n log n)," Algorithmica,
Vol. 38, No. 2, pp. 377{395, 2003.
[5] S.-C. Chen and B. G. Lindsay, "Building mixture trees from binary sequence
data," Biometrika, Vol. 93, No. 4, pp. 843{860, 2006.
[6] B. Dasgupta, X. He, T. Jiang, M. Li, J. Tromp, and L. Zhang, "On comput-
ing the nearest neighbor interchange distance," Proceedings of the DIMACS
Workshop on Discrete Problems with Medical Applications, DIMACS Se-
ries in Discrete Mathematics and Theoretical Computer Science, American
Mathematical Society, Vol. 55, pp. 125{143, 2000.
[7] P. W. Diaconis and S. P. Holmes, "Matchings and phylogenetic trees.," Proc
National Academy of Sciences U S A, Vol. 95, No. 25, pp. 14600{14602, Dec
1998.
[8] G. F. Estabrook, F. R. McMorris, and C. A. Meacham, "Comparison of
undirected phylogenetic trees based on subtrees of four evolutionary units,"
Systematic Zoology, Vol. 34, No. 2, pp. 193{200, 1985.
40
[9] J. Felsenstein, Inferring phylogenies. Sunderland, MA: Sinauer Associates,
2004.
[10] R. P. Grimaldi, Discrete and Combinatorial Mathematics, Fifth Edition. Ad-
dison Wesley, July 2003.
[11] R. C. T. Lee, R. C. Chang, S. S. Tseng, and Y. T. Tsai, Introduction to the
Design and Analysis of Algorithms. McGraw-Hill Education, 2005.
[12] M. L. Lesperance and J. D. Kalb
eisch, An algorithm for computing the
nonparametric MLE of a mixing distribution," Journal of the American Sta-
tistical Association, Vol. 87, No. 417, pp. 120{126, Mar. 1992.
[13] D. F. Robinson and L. R. Foulds, "Comparison of phylogenetic trees," Math-
ematical Biosciences, Vol. 53, No. 1-2, pp. 131{147, February 1981.
[14] N. Saitou and M. Nei, "The neighbor-joining method: a new method for
reconstructing phylogenetic trees," Molecular Biology and Evolution, Vol. 4,
No. 4, pp. 406{425, Jul 1987.
[15] M. A. Steel, "The maximum likelihood point for a phylogenetic tree is not
unique," Systematic Biology, Vol. 43, pp. 560{564, 1994.
[16] M. A. Steel and D. Penny, "Distributions of tree comparison metrics-some
new results," Systematic Biology, Vol. 42, No. 2, pp. 126{141, 1993.
[17] G. Valiente, Algorithms on Trees and Graphs. Secaucus, NJ, USA: Springer-
Verlag New York, Inc., 2002.
[18] G. Valiente, "A fast algorithmic technique for comparing large phylogenetic
trees," SPIRE, pp. 370{375, 2005.
[19] D. B. West, Introduction to Graph Theory 2/e. Prentice Hall, 2001.
41
[20] W. T. Williams and H. T. Cliford, "On the comparison of two classifications
of the same set of elements," Taxon, Vol. 20, No. 4, pp. 519{522, Aug. 1971.
[21] J. Xu, Theory and Application of Graphs (Network Theory and Applications).
Springer, 2003.
4
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top