政大機構典藏-National Chengchi University Institutional Repository(NCCUR):Item 140.119/152099
English  |  正體中文  |  简体中文  |  Post-Print筆數 : 27 |  全文笔数/总笔数 : 114105/145137 (79%)
造访人次 : 52142202      在线人数 : 552
RC Version 6.0 © Powered By DSPACE, MIT. Enhanced by NTU Library IR team.
搜寻范围 查询小技巧：
  • 您可在西文检索词汇前后加上"双引号"，以获取较精准的检索结果
  • 若欲以作者姓名搜寻，建议至进阶搜寻限定作者字段，可获得较完整数据
    •  进阶搜寻
    政大機構典藏 > 理學院 > 應用數學系 > 學位論文 >  Item 140.119/152099


    请使用永久网址来引用或连结此文件: https://nccur.lib.nccu.edu.tw/handle/140.119/152099


    题名: 有限類與無限類的系統發育網路
    Finite and Infinite Classes of Phylogenetic Networks
    作者: 李皓鈞
    Li, Hao-Jun
    贡献者: 符麥克
    Fuchs, Michael
    李皓鈞
    Li, Hao-Jun
    关键词: 物種演化網路
    歸納
    分量圖
    計數
    Phylogenetic networks
    Inductive
    Component graphs
    Counting
    日期: 2024
    上传时间: 2024-07-01 12:56:18 (UTC+8)
    摘要: 物種演化網絡代表了一種網狀方法，用於研究物種之間的演化關聯，利用網絡結構來描述超越傳統樹狀結構的錯綜多變的基因連接。這一新興領域的目標是處理樹狀結構無法完全捕捉的演化事件，如水平基因轉移、雜交和網狀事件。

    許多不同的系統發育網絡已被引入且有系統地研究；參考最近的調查 [21]。然而 [21] 中的作者未對每類系統發育網路的計數問題進行詳細地總結。在本文中，我們旨在討論這一點。更準確地來講，我們將把系統發育網絡分成有限類或無限類，如果有限類，我們給出其大小的最佳上限。

    第一章介紹了基本概念、符號，隨後闡述了本文的研究目的。接下來，在第二章中，我們回顧了 [25] 中 Semple 的工作。在第三章中，我們研究了新舊方法來證明有限類的最佳上限。第四章使用第二章的結果來舉例證明無限類。最後，在第五章中，我們對全文進行了總結。
    Phylogenetic networks provide a reticulated approach to studying the evolutionary relationships among species, utilizing network structures to depict complex and diverse
    genetic connections beyond the confines of traditional tree structures. This emerging field aims to address evolutionary events that cannot be fully captured by tree-like struc-
    tures, such as horizontal gene transfer, hybridization, and reticulation events.

    Many different classes of phylogenetic networks have been introduced and systematically studied; see the recent survey [21]. However, the authors in [21] do not provide a comprehensive summary of the counting problem for each class of phylogenetic network. In this thesis, we aim to discuss this. More precisely, we are going to classify the classes of phylogenetic networks into finite or infinite classes, and if finite, we give optimal upper bounds for their size.

    In Chapter 1, we introduce basic concepts, symbols, and state the purpose of this thesis. Next, in Chapter 2, we review the work of Semple in [25]. In Chapter 3, we survey
    old and new methods to prove optimal upper bounds of the size of classes. Chapter 4 uses the definitions from Chapter 2 to prove and exemplify infinite classes. Finally, in Chapter 5, we summarize the entire thesis.
    參考文獻: [1] L. Agranat-Tamir, M. Fuchs, B. Gittenberger, and N. R. Rosenberg. Enumeration of rooted binary unlabeled galled trees. In 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of
    Algorithms, volume 302 of LIPIcs. Leibniz Int. Proc. Inform., page Art. No. 2. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2024.
    [2] M. Bordewich and C. Semple. Reticulation-visible networks. Advances in Applied Mathematics, 78:114–141, 2016.
    [3] M. Bouvel, P. Gambette, and M. Mansouri. Counting phylogenetic networks of level 1 and level 2. Journal of Mathematical Biology, 81:1357–1395, 2020.
    [4] G. Cardona, F. Rosselló, and G. Valiente. Comparison of tree-child phylogenetic networks. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 6(4):552–569, 2008.
    [5] G. Cardona and L. Zhang. Counting and enumerating tree-child networks and their subclasses. Journal of Computer and System Sciences, 114:84–104, 2020.
    [6] Y.-S. Chang and M. Fuchs. Counting phylogenetic networks with few reticulation vertices: galled and reticulation-visible networks. Bull. Math. Biol., 86(7):Paper No. 76, 2024.
    [7] Y.-S. Chang, M. Fuchs, H. Liu, M. Wallner, and G.-R. Yu. Enumerative and distributional results for d-combining tree-child networks. Adv. in Appl. Math., 157:Paper No. 102704, 58, 2024.
    [8] Y.-S. Chang, M. Fuchs, H. Liu, and M. Wallner G.-R. Yu. Enumeration of d-combining tree-child networks. In 33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms, volume
    225 of LIPIcs. Leibniz Int. Proc. Inform., pages Art. No. 5, 13. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2022.
    [9] M. Fuchs, B. Gittenberger, and M. Mansouri. Counting phylogenetic networks with few reticulation vertices: exact enumeration and corrections. Australasian Journal of Combinatorics, 81:257–282, 2021.
    [10] M. Fuchs, B. Gittenberger, and M. Mansouri. Counting phylogenetic networks with few reticulation vertices: tree-child and normal networks. Discrete Applied Mathematics, 320:140–149, 2022.
    [11] M. Fuchs, E.-Y. Huang, and G.-R. Yu. Counting phylogenetic networks with few reticulation vertices: a second approach. Discrete Applied Mathematics, 320:140– 149, 2022.
    [12] M. Fuchs, H. Liu, and G.-R. Yu. A short note on the exact counting of tree-child networks. ArXiv preprint arXiv:2110.03842, 2021.
    [13] M. Fuchs, G.-R. Yu, and L. Zhang. On the asymptotic growth of the number of tree-child networks. European Journal of Combinatorics, 93:103278, 2021.
    [14] M. Fuchs, G.-R. Yu, and L. Zhang. Asymptotic enumeration and distributional properties of galled networks. Journal of Combinatorial Theory, Series A,
    189:105599, 2022.
    [15] P. Gambette, A. D. M. Gunawan, S. Vialette A. Labarre, and L. Zhang. Solving the tree containment problem in linear time for nearly stable phylogenetic networks. Discrete Applied Mathematics, 246:62–79, 2018.
    [16] P. Gambette, A. D. M. Gunawan, A. Labarre, S. Vialette, and L. Zhang. Locating a tree in a phylogenetic network in quadratic time. In Research in Computational Molecular Biology: 19th Annual International Conference, RECOMB 2015, Warsaw, Poland, April 12-15, 2015, Proceedings 19, pages 96–107. Springer, 2015.
    [17] A. D. M. Gunawan, J. Rathin, and L. Zhang. Counting and enumerating galled networks. Discrete Applied Mathematics, 283:644–654, 2020.
    [18] A. D. M. Gunawan and L. Zhang. Bounding the size of a network defined by visibility property. ArXiv preprint arXiv:1510.00115, 2015.
    [19] D. H. Huson and T.H. Kloepper. Beyond galled trees-decomposition and computation of galled networks. In Annual international conference on research in computational molecular biology, pages 211–225. Springer, 2007.
    [20] L. Jetten and L. Van Iersel. Nonbinary tree-based phylogenetic networks. IEEE/ACM transactions on Computational Biology and Bioinformatics, 15(1):205–217, 2016.
    [21] S. Kong, J. C. Pons, L. Kubatko, and K. Wicke. Classes of explicit phylogenetic networks and their biological and mathematical significance. Journal of Mathematical Biology, 84(6):47, 2022.
    [22] M. Mansouri. Counting general phylogenetic networks. Australasian Journal of Combinatorics, 83:40–86, 2022.
    [23] C. McDiarmid, C. Semple, and D. Welsh. Counting phylogenetic networks. Annals of Combinatorics, 19:205–224, 2015.
    [24] M. Pons and J. Batle. Combinatorial characterization of a certain class of words and a conjectured connection with general subclasses of phylogenetic tree-child networks. Scientific reports, 11(1):21875, 2021.
    [25] C. Semple. Size of a phylogenetic network. Discrete Applied Mathematics,217:362–367, 2017.
    [26] B. Stufler. A branching process approach to level-k phylogenetic networks. Random Structures & Algorithms, 61(2):397–421, 2022.
    [27] S. J. Willson. Properties of normal phylogenetic networks. Bulletin of Mathematical Biology, 72:340–358, 2010.
    描述: 碩士
    國立政治大學
    應用數學系
    110751009
    資料來源: http://thesis.lib.nccu.edu.tw/record/#G0110751009
    数据类型: thesis
    显示于类别:[應用數學系] 學位論文

    文件中的档案:

    档案 描述 大小格式浏览次数
    100901.pdf1482KbAdobe PDF1检视/开启


    在政大典藏中所有的数据项都受到原著作权保护.


    社群 sharing

    著作權政策宣告 Copyright Announcement
    1.本網站之數位內容為國立政治大學所收錄之機構典藏，無償提供學術研究與公眾教育等公益性使用，惟仍請適度，合理使用本網站之內容，以尊重著作權人之權益。商業上之利用，則請先取得著作權人之授權。
    The digital content of this website is part of National Chengchi University Institutional Repository. It provides free access to academic research and public education for non-commercial use. Please utilize it in a proper and reasonable manner and respect the rights of copyright owners. For commercial use, please obtain authorization from the copyright owner in advance.

    2.本網站之製作，已盡力防止侵害著作權人之權益，如仍發現本網站之數位內容有侵害著作權人權益情事者，請權利人通知本網站維護人員(nccur@nccu.edu.tw)，維護人員將立即採取移除該數位著作等補救措施。
    NCCU Institutional Repository is made to protect the interests of copyright owners. If you believe that any material on the website infringes copyright, please contact our staff(nccur@nccu.edu.tw). We will remove the work from the repository and investigate your claim.
    DSpace Software Copyright © 2002-2004  MIT &  Hewlett-Packard  /   Enhanced by   NTU Library IR team Copyright ©   - 回馈