請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/10642
完整後設資料紀錄
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.advisor | 趙坤茂(Kun-Mao Chao) | |
dc.contributor.author | Cheng-Wei Luo | en |
dc.contributor.author | 羅正偉 | zh_TW |
dc.date.accessioned | 2021-05-20T21:46:12Z | - |
dc.date.available | 2013-08-10 | |
dc.date.available | 2021-05-20T21:46:12Z | - |
dc.date.copyright | 2010-08-10 | |
dc.date.issued | 2010 | |
dc.date.submitted | 2010-08-05 | |
dc.identifier.citation | [1] B.L. Allen and M. Steel. Subtree Transfer Operations and Their Induced Metrics on Evolutionary Trees. Annals of Combinatorics, vol. 5, pp. 1-15, 2001.
[2] L. Arvestad, A.-C. Berglund, J. Lagergren, and B. Sennblad. Bayesian Gene/Species Tree Reconciliation and Orthology Analysis Using MCMC. ISMB (Supplement of Bioinformatics), pp. 7-15, 2003. [3] L. Arvestad, A.-C. Berglund, J. Lagergren, and B. Sennblad. Gene Tree Reconstruction and Orthology Analysis Based on an Integrated Model for Duplications and Sequence Evolution. In Proceedings of the 8th Annual International Conference on Research in Computational Molecular Biology, pp. 326-335, 2004. [4] M.S. Bansal, J.G. Burleigh, and O. Eulenstein. Efficient Genome-Scale Phylogenetic Analysis under the Duplication-Loss and Deep Coalescence Cost Models. BMC Bioinformatics, 11(Suppl 1):S42, 2010. [5] M.S. Bansal, J.G. Burleigh, O. Eulenstein, and A. Wehe. Heuristics for the Gene-Duplication Problem: A Theta(n) Speed-Up for the Local Search. In Proceedings of the 11th Annual International Conference on Research in Computational Molecular Biology, pp. 238-252, 2007. [6] M.S. Bansal and O. Eulenstein. An Omega(n^2/ log n) Speed-Up of TBR Heuristics for the Gene-Duplication Problem. IEEE/ACM Trans. on Computational Biology and Bioinformatics, vol. 5, no. 4, pp. 514-524, 2008. [7] M.S. Bansal and O. Eulenstein, The Multiple Gene Duplication Problem Revisited,' Bioinformatics, vol. 24, no. 13, pp. i132-i138, 2008. [8] M.S. Bansal, O. Eulenstein, and A. Wehe. The Gene-Duplication Problem: Near-Linear Time Algorithms for NNI-Based Local Searches. IEEE/ACM Trans. on Computational Biology and Bioinformatics, vol. 6, no. 2, pp. 221-231, 2009. [9] M.S. Bansal. Algorithms for Efficient Phylogenetic Tree Construction. Ph.D. thesis, Iowa State University, 2009. [10] M.S. Bansal and R. Shamir. A Note on the Fixed Parameter Tractability of the Gene-Duplication Problem. IEEE/ACM Trans. on Computational Biology and Bioinformatics, accepted, 2010. [11] M.A. Bender and M. Farach-Colton. The LCA Problem Revisited. In Proceedings of the 4th Latin American Symposium on Theoretical Informatics, pp. 88-94, 2000. [12] G. Blanc, K. Hokamp, and K.H.Wolfe. A Recent Polyploidy Superimposed on Older Large-Scale Duplications in the Arabidopsis Genome. Genome Research, vol. 13, pp. 137-144, 2003. [13] G. Blanc and K.H. Wolfe. Widespread Paleopolyploidy in Model Plant Species Inferred from Age Distributions of Duplicate Genes. Plant Cell, vol. 16, pp. 1093-1101, 2004. [14] P. Bonizzoni, G.D. Vedova, and R. Dondi. Reconciling a Gene Tree to a Species Tree under the Duplication Cost Model. Theoretical Computer Science, vol. 347, no. 1-2, pp. 36-53, 2005. [15] M. Bordewich and C. Semple. On the Computational Complexity of the Rooted Subtree Prune and Regraft Distance. Annals of Combinatorics, vol. 8, pp. 409-423, 2004. [16] J.G. Burleigh, M.S. Bansal, O. Eulenstein, and T.J. Vision. Inferring Species Trees from Gene Duplication Episodes. ACM-BCB, accepted, 2010. [17] J.G. Burleigh, M.S. Bansal, A. Wehe, and O. Eulenstein. Locating Large-Scale Gene Duplication Events through Reconciled Trees: Implications for Identifying Ancient Polyploidy Events in Plants. Journal of Computational Biology, vol. 16, no. 8, pp. 1071-1083, 2009. [18] K. Chen, D. Durand, and M. Farach-Colton. NOTUNG: A Program for Dating Gene Duplications and Optimizing Gene Family Trees. Journal of Computational Biology, vol. 7, no. 3{4, pp. 429-447, 2000. [19] D. Chen, O. Eulenstein, D. Fernandez-Baca, and J.G. Burleigh. Improved Heuristics for Minimum-Flip Supertree Construction. Evolutionary Bioinformatics, vol. 2, pp. 347-356, 2006. [20] J.A. Cotton and R.D.M. Page. Tangled Tales from Multiple Markers: Reconciling Conflict between Phylogenies to Build Molecular Supertrees. Phylogenetic Supertrees: Combing Information to Reveal the Tree of Life, Springer-Verlag, pp. 107-125, 2004. [21] J.A. Cotton and R.D.M. Page. Rates and Patterns of Gene Duplication and Loss in the Human Genome. Proceedings of the Royal Society B, vol. 272, pp. 277-283, 2005. [22] M. Fellows, M. Hallett, and U. Stege. On the Multiple Gene Duplication Problem. In Proceedings of the 9the International Symposium on Algorithms and Computation, pp. 347-357, 1998. [23] G. Ganapathy, V. Ramachandran, and T. Warnow. Better Hill-Climbing Searches for Parsimony. In Proceedings of the 3rd Workshop on Algorithms in Bioinformatics, pp. 245-258, 2003. [24] G. Ganapathy, V. Ramachandran, and T. Warnow. On Contract-and-Refine Transformations Between Phylogenetic Trees. In Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 900-909, 2004. [25] M. Goodman, J. Czelusniak, G.W. Moore, A.E. Romero-Herrera, and G. Matsuda. Fitting the Gene Lineage into Its Species Lineage, a Parsimony Strategy Illustrated by Cladograms Constructed from Globin Sequences. Systematic Zoology, vol. 28, pp. 132-163, 1979. [26] P. Gorecki and J. Tiuryn. On the Structure of Reconciliations. In Proceedings of the 2nd RECOMB Comparative Genomics Satellite Workshop, pp. 42-54, 2004. [27] R. Guigo, I. Muchnik, and T.F. Smith. Reconstruction of Ancient Molecular Phylogeny. Molecular Phylogenetics and Evolution, vol. 6, no. 2, pp. 189-213, 1996. [28] J. Guo and R. Niedermeier. Exact Algorithms and Applications for Tree-Like Weighted Set Cover. Journal of Discrete Algorithms, vol. 4, pp. 608-622, 2006. [29] R. Guyot and B. Keller. Ancestral Genome Duplication in Rice. Genome, vol. 47, pp. 610-614, 2004. [30] M.T. Hallett and J. Lagergren. New Algorithms for the Duplication-Loss Model. In Proceedings of the 4th Annual Internaional Conference on Computational Molecular Biology, pp. 138-146, 2000. [31] M. Lynch and J.S. Conery. The Evolutionary Fate and Consequences of Duplicate Genes. Science, vol. 290, pp. 1151-1155, 2000. [32] M. Lynch and J.S. Conery. Gene Duplication and Evolution. Science, vol. 293, pp. 1551, 2001. [33] M. Lynch and J.S. Conery. The Evolutionary Demography of Duplicate Genes. Journal of Structural and Functional Genomics, vol. 3, pp. 35-44, 2003. [34] B. Ma, M. Li, and L. Zhang. From Gene Trees to Species Trees. SIAM Journal on Computing, vol. 30, no. 3, pp. 729-752, 2000. [35] B. Mirkin, I. Muchnik, and T.F. Smith. A Biologically Consistent Model for Comparing Molecular Phylogenies. Journal of Computational Biology, vol. 2, no. 4, pp. 493-507, 1995. [36] J.E. Neigel and J.C. Avise. Phylogenetic Relationship of Mitochondrial DNA Under Various Demographic Models of Speciation. Evolutionary Processes and Theory, Academic Press, Orlando, FL, pp. 515-534, 1986. [37] S. Ohno. Evolution by Gene Duplication, Springer-Verlag, Berlin, 1970. [38] S. Ohno. Gene duplication and the uniqueness of vertebrate genomes circa 1970-1999. Seminars in Cell & Developmental Biology, vol. 10, no. 5, pp. 517-522, 1999. [39] R.D.M. Page. Maps Between Trees and Cladistic Analysis of Historical Associations Among Genes, Organisms, and Areas. System Biology, vol. 43, no.1, pp. 58-77, 1994. [40] R.D.M. Page. GeneTree: Comparing Gene and Species Phylogenies Using Reconciled Trees. Bioinformatics, vol. 14, no. 9, pp. 819-820, 1998. [41] R.D.M. Page. Extracting Species Trees From Complex Gene Trees: Reconciled Trees And Vertebrate Phylogeny. Molecular Phylogenetics and Evolution, vol. 14, no. 1, pp. 89-106, 2000. [42] R.D.M. Page and J.A. Cotton. Vertebrate Phylogenomics: Reconciled Trees and Gene Duplications. In Proceedings of the 7th Pacific Symposium on Biocomputing, pp. 536-547, 2002. [43] P. Pamilo and M. Nei. Relationships Between Gene Trees and Species Trees. Molecular Biology and Evolution, vol. 5, pp. 568-583, 1988. [44] A.H. Paterson, J.E. Bowers, and B.A. Chapman. Ancient Polyploidization Predating Divergence of the Cereals and its Consequences for Comparative Genomics. Proc. Natl. Acad. Sci., vol. 101, pp. 9903-9908, 2004. [45] S.A. Rensing, J. Ick, J.A. Fawcett, et al. An Ancient Genome Duplication Contributed to the Abundance of Metabolic Genes in the Moss Physcomitrella patens. BMC Evolutionary Biology, vol. 7, pp. 130, 2007. [46] M.J. Sanderson and M.M. McMahon. Inferring Angiosperm Phylogeny from EST Data with Widespread Gene Duplication. BMC Evolutionary Biology, 7(Suppl 1):S3, 2007 [47] J. Schlueter, P. Dixon, C. Granger, D. Grant, L. Clark, J. Doyle, and R. Shoemaker. Mining EST Databases to Resolve Evolutionary Events in Major Crop Species. Genome, vol. 47, no. 5, pp. 868-876, 2004. [48] M.E. Schranz and T. Mitchell-Olds. Independent Ancient Polyploidy Events in Sister Families Brassicaceae and Cleomaceae. Plant Cell, vol. 18, pp. 1152-1165, 2006. [49] J.B. Slowinski, A. Knight, and A.P. Rooney. Inferring Species Trees from Gene Trees: A Phylogenetic Analysis of the Elapidae (Serpentes) Based on the Amino Acid Sequences of Venom Proteins. Molecular Phylogenetics and Evolution, vol. 8, no. 3, pp. 349-362, 1997. [50] U. Stege. Gene Trees and Species Trees: The Gene-Duplication Problem is Fixed-Parameter Tractable. In Proceedings of the 6th Workshop on Algorithms and Data Structures, pp. 288-293, 1999. [51] L. Sterck, S. Rombauts, S. Jansson, et al. EST Data Suggest that Poplar Is an Ancient Polyploidy. New Phytol., vol. 167, pp. 165-170, 2005. [52] D.L. Swofford, G.J. Olsen, P.J. Waddel, and D.M. Hillis. Phylogenetic Inference. Molecular Systematics, chapter 11, pp. 407-509, Sinauer Associates, 1996. [53] N. Takahata. Gene Genealogy in Three Related Populations: Consistency Probability Between Gene and Population Trees. Genetics, vol. 122, no. 4, pp. 957-966, 1989. [54] A. Wehe, M.B. Bansal, J.G. Burleigh, and O. Eulenstein. DupTree: a Program for Large-Scale Phylogenetic Analyses Using Gene Tree Parsimony. Bioinformatics, vol. 24, no. 13, pp. 1540-1541, 2008. [55] A. Wehe, W.-C. Chang, O. Eulenstein, and S. Aluru. A Scalable Parallelization of the Gene Duplication Problem. Journal of Parallel and Distributed Computing, vol. 70, no. 3, pp. 237-244, 2010. [56] C.I. Wu. Inferences of Species Phylogeny in Relation to Segregation of Ancient Polymorphisms. Genetics, vol. 127, no. 2, pp. 429-435, 1991. [57] L. Zhang. On a Mirkin-Muchnik-Smith Conjecture for Comparing Molecular Phylogenies. Journal of Computational Biology, vol. 4, no. 2, pp. 177-187, 1997. [58] L. Zhang. Inferring a Species Tree from Gene Trees under the Deep Coalescence Cost. In Posters of the 4th Annual International Conference on Computational Molecular Biology, pp. 192-192, 2000. | |
dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/10642 | - |
dc.description.abstract | 本論文探討在基因演化模型下之多重基因複製與親緣樹建立相關的最佳化問題。針對多重基因複製,我們探討了事件叢集問題 (Episode-Clustering Problem)與最小事件問題 (Minimum Episodes Problem)。對於事件叢集問題,我們將Burleigh等人的結果改進到最佳的線性時間演算法;而對於最小事件問題,以Bansal與Eulenstein所提出的演算法為基礎下,我們也提出了最佳的線性時間演算法。針對親緣樹的建立,我們探討了複製–遺失問題 (Duplication-Loss Problem)。由於複製–遺失問題是NP困難,因此在實際應用上都使用啟發式方法來解此問題。標準的啟發式方法是在樹狀空間上反覆執行局部搜尋直到局部最小值被算出。以最近鄰居交換 (NNI) 的局部搜尋為基礎下,本論文探討了複製–遺失問題的啟發式方法,同時也對相應的局部搜尋問題提出了一個線性演算法。 | zh_TW |
dc.description.abstract | This dissertation studies several optimization problems related to multiple gene duplications and phylogenetic tree construction under the Gene Duplication model. For multiple gene duplications, we study the Episode-Clustering (EC) problem and the Minimum Episodes (ME) problem. For the EC problem, we improve the results of Burleigh et al. with an optimal linear-time algorithm. For the ME problem, on the basis of the algorithm presented by Bansal and Eulenstein, we propose an optimal linear-time algorithm. For the phylogenetic tree construction, we study the Duplication-Loss problem. Since the Duplication-Loss
problem is NP-hard, heuristics are developed to solve it in practice. A standard heuristic is to perform the stepwise local search on the tree space until a local minimum is reached. In this dissertation, we study the heuristic for the Duplication-Loss problem based on NNI local searches and propose a linear-time algorithm for the corresponding Local Search problem. | en |
dc.description.provenance | Made available in DSpace on 2021-05-20T21:46:12Z (GMT). No. of bitstreams: 1 ntu-99-F93922003-1.pdf: 599022 bytes, checksum: b6371086473f2852730c8b05a98ff99a (MD5) Previous issue date: 2010 | en |
dc.description.tableofcontents | 1 Introduction 1
1.1 Biological Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1.1 Multiple Gene Duplication Problems . . . . . . . . . . . . . . . . . . . . 2 1.1.2 Phylogenetic Tree Construction Problems . . . . . . . . . . . . . . . . . 3 1.2 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.2.1 Basic De‾nitions and Notations . . . . . . . . . . . . . . . . . . . . . . . 5 1.2.2 The Gene Duplication Model . . . . . . . . . . . . . . . . . . . . . . . . 6 1.3 Problem De‾nition and Results . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.4 Organization of the Dissertation . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2 The Episode-Clustering Problem 13 2.1 A Linear-Time Algorithm for the Episode-Clustering Problem . . . . . . . . . . 13 2.1.1 A Linear-Time Algorithm for the Tree Interval Cover Problem . . . . . . 13 2.1.2 Correctness and Complexity . . . . . . . . . . . . . . . . . . . . . . . . . 16 3 The Minimum Episodes Problem 19 3.1 Algorithm ME by Bansal and Eulenstein . . . . . . . . . . . . . . . . . . . . . . 20 3.2 A Linear-Time Algorithm for the Minimum Episodes Problem . . . . . . . . . . 20 3.2.1 Computing the LCA-Mapping . . . . . . . . . . . . . . . . . . . . . . . . 21 3.2.2 Finding All Leading Nodes . . . . . . . . . . . . . . . . . . . . . . . . . . 21 3.2.3 Checking If All Leading Nodes Are Free . . . . . . . . . . . . . . . . . . 24 3.2.4 Updating the Mapping from the Gene Trees to the Species Tree . . . . . 26 3.3 Correctness and Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 4 The DL-NNI Local Search Problem 30 4.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 4.2 Initializing the LCA-mapping and the Mutation Cost . . . . . . . . . . . . . . . 31 4.3 Gene Duplications in NNIS(x) . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 4.4 Losses in NNIS(x) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 4.5 A Linear-Time Algorithm for the DL-NNI Local Search Problem . . . . . . 45 5 Concluding Remarks 48 5.1 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 5.2 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 5.2.1 The Weighted Episode-Clustering Problem . . . . . . . . . . . . . . . . . 48 5.2.2 The DL-k-NNI Local Search Problem . . . . . . . . . . . . . . . . . . . . 49 5.2.3 The SPR Local Search Problem . . . . . . . . . . . . . . . . . . . . . . . 50 | |
dc.language.iso | en | |
dc.title | 在基因複製模型下之多重基因複製與親緣樹建立相關的最佳化問題 | zh_TW |
dc.title | Some Optimization Problems Related to Multiple Gene Duplications and Phylogenetic Tree Construction under the Gene Duplication Model | en |
dc.type | Thesis | |
dc.date.schoolyear | 98-2 | |
dc.description.degree | 博士 | |
dc.contributor.oralexamcommittee | 呂育道(Yuh-Dauh Lyuu),傅楸善(Chiou-Shann Fuh),呂學一(Hsueh-I Lu),曾宇鳳(Y. Jane Tseng) | |
dc.subject.keyword | 基因複製,親緣樹,基因複製模型, | zh_TW |
dc.subject.keyword | Gene duplication,phylogenetic tree,gene duplication model, | en |
dc.relation.page | 57 | |
dc.rights.note | 同意授權(全球公開) | |
dc.date.accepted | 2010-08-06 | |
dc.contributor.author-college | 電機資訊學院 | zh_TW |
dc.contributor.author-dept | 資訊工程學研究所 | zh_TW |
顯示於系所單位: | 資訊工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-99-1.pdf | 584.98 kB | Adobe PDF | 檢視/開啟 |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。