請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/39552
完整後設資料紀錄
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.advisor | 趙坤茂(Kun-Mao Chao) | |
dc.contributor.author | Chun-Wei Kao | en |
dc.contributor.author | 高峻偉 | zh_TW |
dc.date.accessioned | 2021-06-13T17:31:39Z | - |
dc.date.available | 2012-07-29 | |
dc.date.copyright | 2011-07-29 | |
dc.date.issued | 2011 | |
dc.date.submitted | 2011-07-08 | |
dc.identifier.citation | [1] The international HapMap project. Nature, 426(6968):789–796, 2003.
[2] H. J. Bandelt and Andreas W. M. Dress. A canonical decomposition theory for metrics on a finite set. Advances in Mathematics, 92(1):47 – 105, 1992. [3] H. J. Bandelt, P. Forster, B. C. Sykes, and M. B. Richards. Mitochondrial portraits of human populations using median networks. Genetics, 141(2):743–753, 1995. [4] Severine Berard, Anne Bergeron, Cedric Chauve, and Christophe Paul. Perfect sorting by reversals is not always difficult. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 4(1):4–16, 2007. [5] Anne Bergeron, Mathieu Blanchette, Annie Chateau, and Cedric Chauve. Reconstructing ancestral gene orders using conserved intervals. In Algorithms in Bioinformatics, 4th International Workshop, WABI ’04, Proceedings, volume 3240, pages 14–25. Springer, 2004. [6] Anne Bergeron, Cedric Chauve, Fabien de Montgolfier, and Mathieu Raffinot. Computing common intervals of K permutations, with applications to modular decomposition of graphs. 22(3):1022–1039, 2008. [7] Matthias Bernt. Gene Order Rearrangement Methods for the Reconstruction of Phylogeny. PhD thesis, Institut fur Informatik, Universitat Leipzig, 2010. [8] Guillaume Bourque and Pavel A. Pevzner. Genome-Scale evolution: Reconstructing gene orders in the ancestral species. Genome Research, 12(1):26–36, 2002. [9] Alberto Caprara. The reversal median problem. INFORMS Journal on Computing, 15(1):93–113, 2003. [10] J. A. Eisen, J. F. Heidelberg, O. White, and S. L. Salzberg. Evidence for symmetric chromosomal inversions around the replication origin in bacteria. Genome Biol, 1(6), 2000. [11] James S. Farris. Phylogenetic analysis under dollo’s law. Systematic Zoology, 26(1):77–88, 1977. [12] Joseph Felsenstein. Inferring Phylogenies. Sinauer Associates, 2004. [13] Martin Figeac and Jean-Stephane Varre. Sorting by reversals with common intervals. In Algorithms in Bioinformatics, 4th International Workshop, WABI ’04, Proceedings, volume 3240, pages 26–37. Springer, 2004. [14] Walter M. Fitch. Toward defining the course of evolution: Minimum change for a specific tree topology. Systematic Zoology, 20(4):406–416, 1971. [15] Olivier Gascuel. Mathematics of Evolution and Phylogeny. Oxford University Press, Inc., 2007. [16] Alain Guenoche. Graphical representation of a boolean array. Computers and the Humanities, 20:277–281, 1986. [17] Sridhar Hannenhalli and Pavel Pevzner. Transforming cabbage into turnip: polynomial algorithm for sorting signed permutations by reversals. In Proceedings of the 27th Annual ACM Symposium on Theory of Computing, STOC ’95, pages 178–189. ACM Press, 1995. [18] Corinna Herrnstadt, Joanna L. Elson, Eoin Fahy, Gwen Preston, Douglass M. Turnbull, Christen Anderson, Soumitra S. Ghosh, Jerrold M. Olefsky, M. Flint Beal, Robert E. Davis, and Neil Howell. Reduced-median-network analysis of complete mitochondrial dna coding-region sequences for the major african, asian, and european haplogroups. The American Journal of Human Genetics, 70(5):1152 – 1171, 2002. [19] K. T. Huber, E. E. Watson, and M. D. Hendy. An algorithm for constructing local regions in a phylogenetic network. Molecular Phylogenetics and Evolution, 19(1):1–8, 2001. [20] Daniel H. Huson and David Bryant. Application of phylogenetic networks in evolutionary studies. Molecular Biology and Evolution, 23(2):254–267, 2006. [21] Daniel H. Huson and Celine Scornavacca. A survey of combinatorial methods for phylogenetic networks. Genome Biology and Evolution, 3:23–35, 2010. [22] R. M. Karp. Reducibility Among Combinatorial Problems. In R. E. Miller and J. W. Thatcher, editors, Complexity of Computer Computations, pages 85–103. Plenum Press, 1972. [23] Warren C. Lathe, Berend Snel, and Peer Bork. Gene context conservation of a higher order than operons. Trends in Biochemical Sciences, 25(10):474–479, 2000. [24] David Sankoff. Edit distances for genome comparisons based on non-local operations. In Combinatorial Pattern Matching, 3th Annual Symposium, CPM ’92, Proceedings, volume 644, pages 121–135. Springer, 1992. [25] David Sankoff. Short inversions and conserved gene cluster. Bioinformatics, 18(10):1305–1308, 2002. [26] Marie Semon and Laurent Duret. Evolutionary origin and maintenance of coexpressed gene clusters in mammals. Molecular Biology and Evolution, 23(9):1715–1723, September 2006. [27] Cavalli L. L. Sforza and A. W. F. Edwards. Analysis of human evolution. In Genetics Today. Proceedings of the XI International Congress of Genetics, volume 3, pages 923–933. Springer, 1963. [28] G. Xie, N. O. Keyhani, C. A. Bonner, and R. A. Jensen. Ancient origin of the tryptophan operon and the dynamics of evolutionary change. Microbiology and Molecular Biology Reviews, 67(3):303–342, 2003. | |
dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/39552 | - |
dc.description.abstract | 在親緣關係學 (phylogeny) 裡,親緣關係樹 (phylogenetic trees) 可用以表現不同物種之間的演化關係,它是相當實用的工具。然而,近年來發現親緣關係網路 (phylogenetic networks) 在當演化過程中可能包含如非同源相似 (homoplasy)、重組 (recombination)、雜交 (hybridization) 等網狀演化機制 (reticulate evolution) 時,相較於親緣關係樹可以保存更豐富的資訊。過去,親緣關係網路或親緣關係樹多半是由核甘酸 (nucleotide)、單倍群 (halpotype) 或 DNA 等資料建構而成。隨著基因組的定序 (genome sequencing) 以及比較基因組學 (comparative genomics) 的研究漸趨完善,愈來愈多的研究以基因組間的基因重組 (genome rearrangement) 為基礎來推測物種間的親緣關係。另外,研究發現,某些固定排列在一起的基因組 (gene groups) 不斷的在演化過程中被保存下來。若能在推測物種間親緣關係的過程中,同時將這些基因組保存下來,應能獲得更貼近物種間實際演化過程的推論結果。然而,目前與基因重組理論相關的研究多半致力於建構親緣關係樹,並且未考慮將某些特定的基因組保存下來。在這個研究裡,我們以保存式反轉機制 (preserving inversion) 為基礎來建構中位數網路 (median network)。保存式反轉機制為基因重組中的一種機制,且具有保存某些特定基因組的特性,而中位數網路亦是親緣關係網路中的一種。除此之外,我們也設計一個演算法可用來決定在特定的樹的拓樸結構中,該拓樸所能包含的基因重組之最低數目。當我們針對給定的一組物種,列舉所有可能的樹的拓樸結構,這個演算法為我們尋找親緣關係樹提供了非常實用的功能。 | zh_TW |
dc.description.abstract | In the context of phylogeny, phylogenetic trees are widely used to describe the evolutionary relationships between species. In recent years, it is proven that phylogenetic networks can bring more information than phylogenetic trees when the underlying evolutionary history involves reticulate events, e.g. homoplasy, recombination and hybridization. In the past, phylogenetic trees (networks) are usually constructed from gene-scale dataset, e.g. nucleotide, haplotype or DNA. With the advance in genome sequencing and comparative genomics, more and more works on phylogeny inference are based on genome rearrangements. Moreover, it is observed that certain gene groups are preserved during evolution. That is, it is more plausible to assume that gene groups exist in both contemporary species and hypothetical ancestors. However, at present, previous works based on genome rearrangement were most dedicated to constructing phylogenetic trees without regard to conserving gene groups in the evolutionary scenarios. In this work, we construct a phylogenetic network, i.e. median network, based on genome rearrangement that conserves gene groups, i.e. preserving inversion. In addition, as far as phylogenetic tree is concerned, we provide an algorithm to decide the minimum number of rearrangement operations on a given tree topology. It is useful for finding phylogenetic trees when we enumerate all possible tree topologies for a set of species. | en |
dc.description.provenance | Made available in DSpace on 2021-06-13T17:31:39Z (GMT). No. of bitstreams: 1 ntu-100-R98922149-1.pdf: 893036 bytes, checksum: 08a0d06fc635569fee477355ea99aa92 (MD5) Previous issue date: 2011 | en |
dc.description.tableofcontents | 1 Introduction 1
1.1 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.1.1 Previous Work on Phylogeny . . . . . . . . . . . . . . . . . . . . 3 1.1.2 The Fitch Algorithm . . . . . . . . . . . . . . . . . . . . . . . . 7 1.1.3 Median Networks . . . . . . . . . . . . . . . . . . . . . . . . . . 15 1.2 Our Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2 Preliminaries 20 2.1 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.2 k-signed Strong Interval Tree . . . . . . . . . . . . . . . . . . . . . . . . 23 2.3 Properties of Preserving Inversion . . . . . . . . . . . . . . . . . . . . . 26 3 Theoretical Results 28 3.1 Revised Preserving Inversion Sorting Problem . . . . . . . . . . . . . . 28 3.2 Strong Interval Sequence . . . . . . . . . . . . . . . . . . . . . . . . . . 31 4 Algorithms 35 4.1 Algorithm PTCIP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 4.2 Algorithm MNCIP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 5 Concluding Remarks 49 5.1 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 | |
dc.language.iso | en | |
dc.title | 藉由保存式反轉機制來推測親緣關係 | zh_TW |
dc.title | The Phylogeny Inference by Preserving Inversion | en |
dc.type | Thesis | |
dc.date.schoolyear | 99-2 | |
dc.description.degree | 碩士 | |
dc.contributor.oralexamcommittee | 張雅惠(Ya-Hui Chang),王弘倫(Hung-Lung Wang) | |
dc.subject.keyword | 親緣關係學,基因序列,基因重組,中位數網路,有號排列,保存式反轉, | zh_TW |
dc.subject.keyword | Phylogeny,Gene order,Genome rearrangement,Median network,Signed permutation,Preserving inversion, | en |
dc.relation.page | 55 | |
dc.rights.note | 有償授權 | |
dc.date.accepted | 2011-07-08 | |
dc.contributor.author-college | 電機資訊學院 | zh_TW |
dc.contributor.author-dept | 資訊工程學研究所 | zh_TW |
顯示於系所單位: | 資訊工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-100-1.pdf 目前未授權公開取用 | 872.11 kB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。