請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/44187完整後設資料紀錄
| DC 欄位 | 值 | 語言 |
|---|---|---|
| dc.contributor.advisor | 趙坤茂(Kun-Mao Chao) | |
| dc.contributor.author | Meng-Han Li | en |
| dc.contributor.author | 李孟韓 | zh_TW |
| dc.date.accessioned | 2021-06-15T02:43:58Z | - |
| dc.date.available | 2009-12-31 | |
| dc.date.copyright | 2009-08-11 | |
| dc.date.issued | 2009 | |
| dc.date.submitted | 2009-08-10 | |
| dc.identifier.citation | [1] Allen, B.L. and Steel, M., “Subtree Transfer Operations and Their Induced Metrics on
Evolutionary Trees,” Annals of Combinatorics, vol. 5, pp. 1-13, 2001. [2] Bansal, M.S., Eulenstein, O., andWehe, A., “The Gene-Duplication Problem: Near-Linear Time Algorithms for NNI Based Local Searches,” ISBRA, LNCS 4983: 14-25, 2008. [3] Bansal, M.S. and Eulenstein, O., “An (n2/ log n) Speed-up of TBR Heuristics for The Gene-Duplication Problem,” WABI, LNCS/LNBI 4645: 124-135, 2007. [4] Bansal, M.S., Burleigh, J.G., Eulenstein, O., and Wehe, A., “Heuristics for The Gene- Duplication Problem: A (n) Speed-up for The Local Search,” RECOMB, Lecture Notes in Bioinformatics (LNBI) , 4453: 238-252 , 2007. [5] Bonizzoni, P., Vedova, G.D., and Dondi, R., “Reconciling a Gene Tree to a Species Tree Under The Duplication Cost Model,” Theor. Comput. Sci., vol. 347, no. 1-2, pp. 36-53, 2005. [6] Chen, K., Durand, D., and Farach-Colton, M., “Notung: A Program for Dating Gene Duplications and Optimizing Gene Family Trees,” Journal of Computational Biology, vol. 7, pp. 429-447, 2000. [7] Eulenstein, O., “Predictions of Gene-Duplications and Their Phylogenetic development,” Ph.D. dissertation, University of Bonn, Germany, 1998, GMD Research Series No. 20 / 1998. [8] Forterre, P., Benachenbou-Lafha, N., and Labeden, B, “Universal Tree of Live,” Nature, 362: 29, 1993. [9] G′orecki, P. and Tiuryn, J., “On the structure of reconciliations,” in RECOMB Comparative Genomics Workshop, 2004. [10] Guig′o, R., Muchnik, I., and Smith, T.F., “Reconstruction of Ancient Molecular Phy- logeny,” Molecular Phylogenetics and Evolution, vol. 6, no. 2, pp. 189-213, 1996 [11] Goodman, M., Czelusniak, J., Moore, G.W., Romero-Herrera, A.E., and Matsuda, G., “Fitting the Gene Lineage into Its Species Lineage. A Parsimony Stratergy Illustrated by Cladograms Constructed from Globin Sequences,” Systematic Zoology, vol. 28, pp. 132-163, 1979 [12] Ma, B., Li, M., and Zhang, L., “From Gene Trees to Species Trees.” SIAM J. Comput., vol. 30, no. 3, pp. 729-752, 2000. [13] Ohno, S., “Evolution by Gene Duplication,” Springer-Verlag, 1970. [14] Page, R.D.M., “Maps between trees and cladistic analysis of historical associations among genes, organisms, and areas,” Systematics Biology, 43:58-77, 1994. [15] Page, R.D.M. and Holmes, E.C., “Molecular evolution: a phylogenetic approach,” Blackwell Science, 1998. [16] Page, R.D.M. and Charleston, M.A., “From gene to organismal phylogeny: reconciled trees and the gene tree/species tree problem,” Molec. Phyl. and Evol., vol. 7, pp. 231-240, 1997. [17] Swofford, D.L. and Olsen, G.J., “Phylogeny Reconstruction,” Molecular Systematics, chap- ter 11, pp. 411-501, 1990. [18] Waterman, M.S. and Smith, T.F., “On The Similarity of Dendrograms,” J. Theor. Biol., 73: 789-800, 1987. [19] Zhang, L., “On a Mirkin-Muchnik-Smith Conjecture for Comparing Molecular Phyloge- nies,” Journal of Computational Biology 4(2), 177-187, 1997. | |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/44187 | - |
| dc.description.abstract | 在種系發生學(Phylogeny)上，我們發現基因樹(Gene Tree)和演化樹
(Phylogenetic Tree)上的不一致，是可能起源於基因流失(Gene Loss)、基因重組(Gene Recombination)、或基因複製(Gene Duplication)。在此情況下，我們希望利用基因複製架構(Gene Duplication Model)，從一群基因樹和一棵演化樹中找出一棵超級樹(Supertree)來表示最有可能演化樹的真正構造。主要計算此超級樹的難處在於基因樹的資料量太大，電腦在計算能力上無法更有效率的找到最適合的超級樹。因此在此篇研究中，我們提出了一個利用最近鄰居交換(Nearest Neighbor Interchange)區域搜尋方法的線性時間啟發式演算法，在現性時間中找到這棵能表現基因樹和演化樹一致性的超級樹。 | zh_TW |
| dc.description.abstract | Contradictory phylogenies may result from several effects, such as gene loss, recombination, and duplication. The gene duplication problem is to deduce a most likely phylogenetic supertree from a large set of gene trees with gene duplication information. This problem has been
proved to be NP-complete, and more efficient heuristics are required to deal with large-scale phylogenetic analysis. A naive heuristic which performs a step-by-step search on the tree and recalculate the reconciliation cost on each node is extremely time consuming and requiring enormous computational power. The k-NNI search problem, based on at most k times nearest neighbor interchange operations, has been largely put into use for solving the gene duplication problem. In this work, we provide a linear-time solution for the 1-NNI local search problem and an O(p(r + log n))-time heuristic based on 1-NNI local search problem, where p denotes the number of iterations. The result of this work provides a feasible approach for the vast phylogenetic data analysis. | en |
| dc.description.provenance | Made available in DSpace on 2021-06-15T02:43:58Z (GMT). No. of bitstreams: 1 ntu-98-R95922036-1.pdf: 548449 bytes, checksum: 2062f94bfafc24b1433ab3a3ad406281 (MD5) Previous issue date: 2009 | en |
| dc.description.tableofcontents | 1 Introduction 1
1.1 Gene Tree and Species Tree 3 1.2 Contribution of This Research 4 2 Preliminaries 6 2.1 Basic Definitions and Notation 6 2.2 The Gene Duplication Problem 7 2.3 The Local Search Problem 8 3 Structure Properties 10 4 The Main Algorithm 15 4.1 Solving the 1-NNI Local Search Problem in Linear Time 15 4.2 Heuristic Based on 1-NNI 20 5 Concluding Remarks 24 Bibliography 25 | |
| dc.language.iso | en | |
| dc.subject | 基因樹 | zh_TW |
| dc.subject | 演化樹 | zh_TW |
| dc.subject | 最近鄰居交換 | zh_TW |
| dc.subject | 基因複製架構 | zh_TW |
| dc.subject | 基因流失 | zh_TW |
| dc.subject | Gene Tree | en |
| dc.subject | Phylogenetic Tree | en |
| dc.subject | Gene Loss | en |
| dc.subject | Gene Duplication Model | en |
| dc.subject | Nearest Neighbor Interchange | en |
| dc.title | 一個解決基因複製問題的線性時間啟發式演算法 | zh_TW |
| dc.title | A Linear-time Heuristic for The Gene Duplication Problem Based on NNI Local Searches | en |
| dc.type | Thesis | |
| dc.date.schoolyear | 97-2 | |
| dc.description.degree | 碩士 | |
| dc.contributor.oralexamcommittee | 徐熊健,張雅惠 | |
| dc.subject.keyword | 演化樹,基因樹,最近鄰居交換,基因複製架構,基因流失, | zh_TW |
| dc.subject.keyword | Phylogenetic Tree,Gene Tree,Nearest Neighbor Interchange,Gene Duplication Model,Gene Loss, | en |
| dc.relation.page | 26 | |
| dc.rights.note | 有償授權 | |
| dc.date.accepted | 2009-08-10 | |
| dc.contributor.author-college | 電機資訊學院 | zh_TW |
| dc.contributor.author-dept | 資訊工程學研究所 | zh_TW |
| 顯示於系所單位： | 資訊工程學系 | |
文件中的檔案：
| 檔案 | 大小 | 格式 | |
|---|---|---|---|
| ntu-98-1.pdf 未授權公開取用 | 535.59 kB | Adobe PDF |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。