1. NCCU Academic Hub
  2. Publications
  3. College of Science
  4. Theses
  5. Item

Publications-Theses

Article View/Open

Publication Export

Google ScholarTM

NCCU Library

Citation Infomation

Related Publications in TAIR

題名 有限類與無限類的系統發育網路
Finite and Infinite Classes of Phylogenetic Networks
作者 李皓鈞
Li, Hao-Jun
貢獻者 符麥克
Fuchs, Michael
李皓鈞
Li, Hao-Jun
關鍵詞 物種演化網路
歸納
分量圖
計數
Phylogenetic networks
Inductive
Component graphs
Counting
日期 2024
上傳時間 1-Jul-2024 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
dc.contributor.advisor 符麥克zh_TW
dc.contributor.advisor Fuchs, Michaelen_US
dc.contributor.author (Authors) 李皓鈞zh_TW
dc.contributor.author (Authors) Li, Hao-Junen_US
dc.creator (作者) 李皓鈞zh_TW
dc.creator (作者) Li, Hao-Junen_US
dc.date (日期) 2024en_US
dc.date.accessioned 1-Jul-2024 12:56:18 (UTC+8)-
dc.date.available 1-Jul-2024 12:56:18 (UTC+8)-
dc.date.issued (上傳時間) 1-Jul-2024 12:56:18 (UTC+8)-
dc.identifier (Other Identifiers) G0110751009en_US
dc.identifier.uri (URI) https://nccur.lib.nccu.edu.tw/handle/140.119/152099-
dc.description (描述) 碩士zh_TW
dc.description (描述) 國立政治大學zh_TW
dc.description (描述) 應用數學系zh_TW
dc.description (描述) 110751009zh_TW
dc.description.abstract (摘要) 物種演化網絡代表了一種網狀方法，用於研究物種之間的演化關聯，利用網絡結構來描述超越傳統樹狀結構的錯綜多變的基因連接。這一新興領域的目標是處理樹狀結構無法完全捕捉的演化事件，如水平基因轉移、雜交和網狀事件。 許多不同的系統發育網絡已被引入且有系統地研究；參考最近的調查 [21]。然而 [21] 中的作者未對每類系統發育網路的計數問題進行詳細地總結。在本文中，我們旨在討論這一點。更準確地來講，我們將把系統發育網絡分成有限類或無限類，如果有限類，我們給出其大小的最佳上限。 第一章介紹了基本概念、符號，隨後闡述了本文的研究目的。接下來，在第二章中，我們回顧了 [25] 中 Semple 的工作。在第三章中，我們研究了新舊方法來證明有限類的最佳上限。第四章使用第二章的結果來舉例證明無限類。最後，在第五章中，我們對全文進行了總結。zh_TW
dc.description.abstract (摘要) 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.en_US
dc.description.tableofcontents 前言 I Praface II Contents III 1 Introduction 1 1.1 Phylogenetic Trees 1 1.2 Phylogenetic Networks 4 1.3 Purpose of this Work 15 1.4 Timeline of previous Research 18 2 Minimal Restrictions for Finiteness 20 3 Finite Classes of Phylogenetic Networks 29 3.1 Mathematical Induction 29 3.2 Zhang’s First Method 42 3.3 Zhang’s Second Method 49 3.4 Optimal Upper Bounds for Finite Classes 56 4 Infinite Classes of Phylogenetic Networks 60 5 Conclusion 63 Bibliography 66zh_TW
dc.format.extent 1518335 bytes-
dc.format.mimetype application/pdf-
dc.source.uri (資料來源) http://thesis.lib.nccu.edu.tw/record/#G0110751009en_US
dc.subject (關鍵詞) 物種演化網路zh_TW
dc.subject (關鍵詞) 歸納zh_TW
dc.subject (關鍵詞) 分量圖zh_TW
dc.subject (關鍵詞) 計數zh_TW
dc.subject (關鍵詞) Phylogenetic networksen_US
dc.subject (關鍵詞) Inductiveen_US
dc.subject (關鍵詞) Component graphsen_US
dc.subject (關鍵詞) Countingen_US
dc.title (題名) 有限類與無限類的系統發育網路zh_TW
dc.title (題名) Finite and Infinite Classes of Phylogenetic Networksen_US
dc.type (資料類型) thesisen_US
dc.relation.reference (參考文獻) [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.zh_TW