Loading...
|
Please use this identifier to cite or link to this item:
https://nccur.lib.nccu.edu.tw/handle/140.119/152099
|
| Title: | 有限類與無限類的系統發育網路
Finite and Infinite Classes of Phylogenetic Networks |
| Authors: | 李皓鈞
Li, Hao-Jun |
| Contributors: | 符麥克
Fuchs, Michael
李皓鈞
Li, Hao-Jun |
| Keywords: | 物種演化網路
歸納
分量圖
計數
Phylogenetic networks
Inductive
Component graphs
Counting |
| Date: | 2024 |
| Issue Date: | 2024-07-01 12:56:18 (UTC+8) |
| Abstract: | 物種演化網絡代表了一種網狀方法，用於研究物種之間的演化關聯，利用網絡結構來描述超越傳統樹狀結構的錯綜多變的基因連接。這一新興領域的目標是處理樹狀結構無法完全捕捉的演化事件，如水平基因轉移、雜交和網狀事件。
許多不同的系統發育網絡已被引入且有系統地研究；參考最近的調查 [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. |
| 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. |
| Description: | 碩士
國立政治大學
應用數學系
110751009 |
| Source URI: | http://thesis.lib.nccu.edu.tw/record/#G0110751009 |
| Data Type: | thesis |
| Appears in Collections: | [應用數學系] 學位論文
|
Files in This Item:
| File |
Description |
Size | Format | |
|---|
| 100901.pdf | | 1482Kb | Adobe PDF | 1 | View/Open |
|
All items in 政大典藏 are protected by copyright, with all rights reserved.
|
