跳到主要內容

臺灣博碩士論文加值系統

(34.226.244.254) 您好!臺灣時間:2021/08/01 05:47
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:沈家本
研究生(外文):Chia-Ben Shen
論文名稱:利用支配尋找二元樹上的最大共同子樹
論文名稱(外文):Using Domination to Find the Maximum Agreement Subtree on Binary Trees
指導教授:唐傳義
指導教授(外文):Chuan-Yi Tang
學位類別:碩士
校院名稱:國立清華大學
系所名稱:資訊工程學系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2004
畢業學年度:92
語文別:英文
論文頁數:19
中文關鍵詞:最大共同子樹支配範圍搜尋樹
外文關鍵詞:maximum agreement subtreedominationdominaterange search treetree
相關次數:
  • 被引用被引用:0
  • 點閱點閱:121
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
演化樹是種有根的且葉子有標號的樹,而對於這樹中的每一個內部節點,它有兩個以上的孩子。在計算生物學上,對於給定的一群物種建構一棵演化樹是基本而實在的工作。很不幸地,不同的演算法往往產生不同的演化樹,而即使對於相同的一群物種,不同的研究也有不同的演化結果。因此,如何在這些不同的演化樹上去找到它們的一致性變得非常重要且迫切了。在本篇論文中,我們把焦點放在一系列的一致性問題中最讓人感興趣的一個:尋找最大共同子樹問題(the maximum agreement subtree problem)。
尋找二元樹中最大共同子樹問題定義如下:給定一群其葉子標號在集合L的樹的集合T = { T1, T2, T3, …, Tk } 而其中 T1 是棵二元樹,在L集合上尋找一個最大的卡內基子集使得對於T1, T2, T3, …, Tk 在拓樸學上的限制是同形的。首先,我們會先介紹Bryant的演算法[3];接著利用支配來改進Bryant的演算法並利用多維的橋式範圍搜尋樹(bridged range search tree)來實作。儘管時間複雜度和最新發表的論文中一樣是O( n2logkn )[15],但實作上卻比以往的快了許多。
An evolutionary tree is a rooted, leaf-labeled tree. Each internal node of the tree has at least two children. Constructing evolutionary trees for the given species is a fundamental work in computational biology. Unfortunately, different algorithms usually produce different evolutionary trees and different research may have different evolutionary trees even on the same set of the species. It becomes more necessary to know the consensus between those trees recently. We focus on one of the consensus problems and agreement problems: the maximum agreement subtree (MAST) problem.
The MAST problem is as follow : given a set a set T = { T1, T2, T3, …, Tk } of leaf-labeled trees on leaf-labeled set L where T1 is a binary tree, find a maximum cardinality subset X of L such that the topological restrictions of T1, T2, T3, …, Tk are isomorphic. In this paper, we introduce Bryant’s algorithm first and use domination to improve Bryant’s algorithm and implement by bridged range search tree method. Although the time cost is O( (n^2)(logn)^k ), the same to original paper, but the implementation is quicker than before.
[1] C.R. Finden and A.D. Gordon, ”Obtaining common pruned trees”, J. Classification, Vol. 2, 1985, pp. 255-276.

[2] A. Amir and D. Keselman, “Maximum agreement subtree in a set of evolutionary trees: metrics and efficient algorithms,” SIAM J. Comput. , Vol. 26, 1997, pp.1656-1669

[3] D. Bryant, “Hunting for trees, building trees and comparing trees: theory and methods in phylogenetic analysis”, Ph. D. thesis, Dept. Math., University of Canterbury, 1997, pp.117-182

[4] R. Cole, M. Farach, R. Hariharan, T. Przytycka, and M. Thorup, “An algorithm for the maximum agreement subtree problem for binary trees,” SIAM J. Comput, Vol.30, 2000, PP. 1385-1404

[5] M. Farach, T. Przytycka, and M. Thorup, “The maximum agreement subtree problem for binary trees,” in Proceedings of the 2nd European Symposium on Algorithms, Corfu, Greece, 1995, Lecture Notes in Comput. Sci. 979, SpringerVerlag, New York, 1995, pp.381-393.

[6] M. Farach, T. Przytycka, and M. Thorup, “On the agreement of many trees,” Information Processing Letters, Vol.55, 1995, pp.297-301

[7] M. Farach and M. Thorup, “Fast comparison of evolutionary trees,” Inform. and Comput., Vol.123, 1995, pp.29-37.

[8] M. Farach and M. Thorup, “Sparse dynamic programming for evolutionary tree comarison,” SIAM J. Comput., Vol.26, 1997, pp.210-230.

[9] M.L. Fredaman, “Two applications of a probabilistic search technique: Sorting X+Y and building balanced search trees,” in Proceedings of the 7th ACM Symposium on the Theory of Computing, ACM, New York, 1975, pp.240-244.

[10] M. Mehlhorn, “A best possible bound for the weighted path length of binary search trees,” SIAM J. Comput., Vol.6, 1977, pp.235-239.

[11] E. Kubicka, G. Kubicki, and F.R. McMorris, “An algorithm to find agreement subtrees,” J. Classification, Vol.12, 1995, pp.91-100.

[12] M. Steel and T. Warnow, “Kaikoura tree theorems: Computing the maximum agreement subtree,” Information Processing Letters, Vol.48, 1993, pp.77-82.

[13] G. S. Lueker, “A data structure for Orthogonal Range Queries,” Proceedings of the 19th Annual IEEE Symposium on Foundations of Computer Science, 1978, pp. 28-34.

[14] K. Mehlhorn, Data structures and Algorithms 3. Multi-dimensional Searching and Computational Geometry, Springer, Berline, Heidelberg, New York, 1984

[15] Maw-Shang Chang, Ling-Ju Hung, “Range Search Trees and the Maximum Agreement Subtree Problem on Binary Trees,” Chung Cheng University, Taiwan, 2003
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
1. 于富雲(2001)。從理論基礎探究合作學習的教學效益。教育資料與研究,38,22-28。
2. 王千倖(1999)。「合作學習」和「問題導向學習」﹘培養教師及學生的科學創作力。教育資料與研究,28,31-39。
3. 王永昌、張永宗(2002)。創造雙贏的教學策略:合作學習。生活科技教育,35(3),1-11。
4. 王智玄(2000)。新的學習策略﹘網路合作式學習之探討。資訊與教育,78,42-50。
5. 王曉璿(1998)。網路環境與教學應用。教師之友,39(1),7-13。
6. 朱湘吉(1992)。新觀念、新挑戰﹘建構主義的教學系統。教學科技與媒體,2,15-20。
7. 吳明隆(1998)。以網路為主的教學環境(Web-Based Instruction)內涵及規劃原則。教育部電子計算機中心簡訊,8712,22-38。
8. 李進寶(1991)。日本中小學校使用電腦的概況介紹。載於資訊與教育雜誌(主編),資訊教育與教學(頁93-99)。台中:資訊與教育雜誌社。
9. 林奇賢(1997)。網住改革---電腦網路與教育改革。國教之友,49(1),5-12。
10. 張惠博(1993):邁向科技探究的實驗教學。教師天地,62。
11. 郭文耀(2000)。英文網路教學初探。國立空中大學共同科學報,2,093-106。
12. 郭重吉(1992)。從建構主義的觀點中探討中小學數理教學的改進。科學發展月刊,20(5),548-570。
13. 郭重吉(1987)。評介學習風格之有關研究。資優教育季刊,23,7-16。
14. 戴建耘(1991)。中美兩國國民中學實施資訊教育之現況。載於資訊與教育雜誌社(主編),資訊教育與教學(70-88頁)。台中:資訊與教育雜誌社。
15. 蘇蘅、吳淑俊(1999)。電腦網路問卷調查可行性及回覆者特質的研究。新聞學研究,(53),75-100。