# 臺灣博碩士論文加值系統

(44.213.60.33) 您好！臺灣時間：2024/07/22 16:16

:::

### 詳目顯示

:

• 被引用: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 . . . . . . . . . . . . . . . . . . . . . . . . . IAbstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . IIContents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . IVList of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . VIList of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . .VII1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . 11.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . 11.2 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . 21.3 Preview This Thesis . . . . . . . . . . . . . . . . . . . . . . 62 Preliminary . . . . . . . . . . . . . . . . . . . . . . . . . . 72.1 Some Definitions of Graph . . . . . . . . . . . . . . . . . . . 72.2 Useful Algorithms . . . . . . . . . . . . . . . . . . . . . . . 93 Mixture Distance . . . . . . . . . . . . . . . . . . . . . . . . 123.1 The Definition of Mixture Distance . . . . . . . . . . . . . . . 123.2 An Algorithm for Mixture Distance . . . . . . . . . . . . . . . 133.2.1 The Basic Algorithm for Mixture Distance . . . . . . . . . . . . 133.2.2 An Example . . . . . . . . . . . . . . . . . . . . . . . . . . . 183.2.3 Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213.3 The Modified Algorithm for Mixture Distance . . . . . . . . . . 233.3.1 The Modified Algorithm . . . . . . . . . . . . . . . . . . . . . 233.3.2 An Example of the Modified Algorithm . . . . . . . . . . . . . . 263.3.3 Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . 294 Mixture-Matching Distance . . . . . . . . . . . . . . . . . . . 314.1 The definition and algorithm for Mixture-Matching Distance . . . 314.2 An Example of Mixture-Matching Distance . . . . . . . . . . . . 334.3 Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . 355 Conclusions and Future Work . . . . . . . . . . . . . . . . . . 38References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
 [1] M. A. Bender and M. Farach-Colton, "The lca problem revisited," LatinAmerican 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 aphylogenetic 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 sequencedata," 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 DIMACSWorkshop on Discrete Problems with Medical Applications, DIMACS Se-ries in Discrete Mathematics and Theoretical Computer Science, AmericanMathematical Society, Vol. 55, pp. 125{143, 2000.[7] P. W. Diaconis and S. P. Holmes, "Matchings and phylogenetic trees.," ProcNational Academy of Sciences U S A, Vol. 95, No. 25, pp. 14600{14602, Dec1998.[8] G. F. Estabrook, F. R. McMorris, and C. A. Meacham, "Comparison ofundirected 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 theDesign and Analysis of Algorithms. McGraw-Hill Education, 2005.[12] M. L. Lesperance and J. D. Kalbeisch, An algorithm for computing thenonparametric 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 forreconstructing 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 notunique," Systematic Biology, Vol. 43, pp. 560{564, 1994.[16] M. A. Steel and D. Penny, "Distributions of tree comparison metrics-somenew 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 phylogenetictrees," 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 classificationsof 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
 電子全文
 國圖紙本論文
 推文當script無法執行時可按︰推文 網路書籤當script無法執行時可按︰網路書籤 推薦當script無法執行時可按︰推薦 評分當script無法執行時可按︰評分 引用網址當script無法執行時可按︰引用網址 轉寄當script無法執行時可按︰轉寄

 1 演化樹評估模式的建立及其應用 2 混合樹之間的複合距離之研究

 無相關期刊

 1 完美多重機密配置系統問題 2 應用於拍賣網頁分類目錄下的影像搜尋系統 3 基於搜尋引擎技術之影像搜尋系統 4 在2D離散傅立葉頻譜上開發具有抵抗print-and-photo破壞的資料隱藏技術並應用於照相行動裝置上 5 考量視覺編排設計概念之自動化超媒體圖文合成系統 6 以階層架構為基礎多層次的動態文字特效合成系統 7 以幾何圖形及色相為基礎之情境圖像版面佈置系統 8 植基於位元/格狀結構之整合式霍夫曼及迴旋循序解碼演算法 9 應用於具照相功能行動電話之強健性及高容量二維影像碼 10 第二短路徑問題之研究 11 河內圖之最小邊排列編號 12 用於非正向虹膜取像之可操控傾斜式影像感測器 13 太極拳輔助學習系統—使用加速規做師生姿態同步及比對分析 14 結合微機電系統感測器與視覺感測器追蹤三維人體姿態 15 應用特徵擷取、SVM和LSA於分析大量稀疏資料的推薦系統

 簡易查詢 | 進階查詢 | 熱門排行 | 我的研究室