臺灣博碩士論文加值系統

(34.226.244.254) 您好！臺灣時間：2021/08/01 05:47

:::

詳目顯示

:

• 被引用: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
 國圖紙本論文
 推文當script無法執行時可按︰推文 網路書籤當script無法執行時可按︰網路書籤 推薦當script無法執行時可按︰推薦 評分當script無法執行時可按︰評分 引用網址當script無法執行時可按︰引用網址 轉寄當script無法執行時可按︰轉寄

 1 圖上電力支配問題的研究 2 圖的無k點子樹支配問題

 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。

 1 具限制條件的序列比對：考慮範圍與順序資訊 2 廣播支配問題之研究 3 排列圖上的羅馬支配問題 4 圖的k多重支配問題 5 基因體重排的組合演算法和應用 6 節省空間之三序列比對平行演算法 7 某類擬似樹狀圖上的MAD樹 8 利用Blosum62計分矩陣為基礎的交叉參考投票機制,識別蛋白質關鍵性的胺基酸候選者 9 尋找所有在RNA上的莖幹及其應用 10 個人化工作流程限制與服務品質之研究 11 網路學習非同步討論板文章內容自動化重點整理機制 12 樹和樹幹之振動特性研究 13 加權有效支配之研究 14 樹自動機與樹形辨認 15 台灣檫樹根部及莖部化學成分與生物活性研究

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