學術產出-學位論文
文章檢視/開啟
書目匯出
-
題名 樹子網路及其變體的計數和分布結果
Enumerative and Distributional Results for Tree-Child Networks and Their Variants作者 劉赫煊
Liu, Hexuan貢獻者 符麥克
Michael Fuchs
劉赫煊
Liu, Hexuan關鍵詞 演化網路
樹子網路
解析計數
極限法則
雙射法
拉普拉斯方法
動差估計
Phylogenetic network
Tree-child network
Analytic counting
Limit laws
Bijective proof,
Laplace method
Method of moments. II日期 2022 上傳時間 1-八月-2022 18:12:54 (UTC+8) 摘要 近年來，作為演化網路的眾多分類中最著名的子類之一，樹子網路吸引了許多數學家與生物學家的注意。然而直到幾年前，樹子網路的精確和漸進計數仍然很困難，遑論其它問題。在本碩論中，我們將回顧以往樹子網路及其變體的一些重要結果，並添加幾個新的結果。\n\n藉由組合學和概率論中的工具，我們實現的主要貢獻有：在單組分樹子網路下證明了最近的一個對於樹子網絡精確計數的猜想；此外，得到了第一個在均勻隨機選取樹子網路時的隨機結果；同時，還擴展了樹子網路的定義並將前人的和我們的結果推廣到這一新類；另外，也使先前對於有序樹子網路中圖案極限規律的研究更進一步，且提供了首個對一類演化網路中一般圖形的研究。\n\n該碩論的簡短概述如下：首先在第1章中，我們給出了樹子網路、樹子網路的擴展以及有序樹子網路的定義和基本性質；然後在第2章中，我們介紹了所用的工具。其次在第3和第4章，我們分別對樹子網路及其擴展進行研究。接著在第5章，我們將以往對於有序樹子網路的研究推廣到所有高度為1和2的圖案，再給出對於任意高度圖案的推論。最後在第6章，我們總結全文。
In recent years, as one of the most prominent subclass among the many different classes of phylogenetic networks, the class of tree-child networks has attracted the attention of many mathematicians and biologists. However, until a few years ago, both exact and asymptotic counting for tree-child networks was still difficult, not to mention other problems. In this thesis, we will review the most important previous results for tree-child networks and their variants and add several new results.\n\nOur main contributions, which are mainly proved with tools from Combinatorics and Probability Theory, are as follows. For a recent conjecture on the exact counting of tree-child\nnetworks, we give a proof for the special case when the tree-child network is a one-component network. In addition, we prove the first stochastic results for tree-child networks which are picked uniformly at random. Also, we can extend the definition of tree-child networks and generalize previous and our results to the new class. Moreover, we have taken the previous research on limit laws of patterns in ranked tree-child network a step further and provided the\nfirst general patterns study for a class of phylogenetic networks.\n\nA short outline of the thesis is as follows: in Chapter 1, we give definitions and show some basic properties for tree-child networks, their extensions and ranked tree-child networks. Then, in Chapter 2, we introduce our tools. In Chapter 3 and Chapter 4, we focus on results for tree-child networks and their extensions, respectively. Next in Chapter 5, we generalize the former study on patterns of ranked tree-child networkto all patterns of height 1 and 2 and make a conjecture for patterns of any height. Finally, we finish the thesis in Chapter 6 with a conclusion.參考文獻 [1] F. Bienvenu, A. Lambert, M. Steel (2022). Combinatorial and stochastic properties of ranked tree-child networks, Random Struct. Algor., 60(4), 653–689.\n[2] P. Billingsley (1995). Probability and Measure, third edition, Wiley Series in Probability and Mathematical Statistics, John Wiley & Sons, Inc., New York, 1995.\n[3] A. Caraceni, M. Fuchs, G.-R. Yu (2022). Bijections for ranked tree-child networks, Discrete Math., 345:9, 112944, 10 pages.\n[4] G. Cardona, G. Rossello, F. Valiente (2009). Comparison of tree-child phylogenetic networks. IEEE/ACM Trans. Comput. Biol. Bioinform. 6(4), 552–569.\n[5] G. Cardona and L. Zhang (2020). Counting tree-child networks and their subclasses, J.Comput.Syst. Sci., 114, 84–104.\n[6] H. Chang and M. Fuchs (2010). Limit theorems for patterns in phylogenetic trees, J. Math.Biol., 60:4, 481–512.\n[7] Y.-S. Chang, M. Fuchs, H. Liu, M. Wallner, G.-R. Yu (2022). Enumeration of d-combining Tree-Child Networks, LIPICS, Proceedings of the 33rd International Meeting on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms,\n225.\n[8] K. P. Choi, G. Kaur, T. Wu (2021). On asymptotic joint distributions of cherries and pitchforks for random phylogenetic trees, J. Math. Biol., 83:4, Paper No. 40, 34 pp.\n[9] K. P. Choi, A. Thompson, T. Wu (2020). On cherry and pitchfork distributions of random rooted and unrooted phylogenetic trees, Theor. Popul. Biol., 132, 92–104.\n[10] F. Disanto and T. Wiehe (2013). Exact enumeration of cherries and pitchforks in ranked trees under the coalescent model, Math. Biosci., 242:2, 195–200.\n[11] A. Elvey Price, W. Fang, M. Wallner (2021). Compacted binary trees admit a stretched exponential, J. Comb. Theory Ser. A, 177, Article 105306.\n[12] M. Fuchs, B. Gittenberger, M. Mansouri (2019). Counting phylogenetic networks with few reticulation vertices: tree-child and normal networks, Australas. J. Combin., 73:2, 385–423.\n[13] M. Fuchs, B. Gittenberger, M. Mansouri (2021). Counting phylogenetic networks with few reticulation vertices: exact enumeration and corrections, Australas. J. Combin., 82:2,\n257–282.\n[14] M. Fuchs, E.-Y. Huang, G.-R. Yu, E.-Y. Huang (2022). Counting phylogenetic networks with few reticulation vertices: a second approach, Discrete Appl. Math., in press.\n[15] M. Fuchs, H. Liu, G.-R. Yu. A short note on the exact counting of tree-child networks, arXiv:2110.03842.\n[16] M. Fuchs, H. Liu, T.-C. Yu. Limit theorems for patterns in ranked tree-child networks, arXiv:2204.07676.\n[17] M. Fuchs, G.-R. Yu, L. Zhang (2021). On the asymptotic growth of the number of tree-child networks, European J. Combin., 93, 103278, 20 pages.\n[18] C. Holmgren and S. Janson (2015). Limit laws for functions of fringe trees for binary search trees and recursive trees, Electron. J. Probab., 20, 1–51.\n[19] G. Kaur, K. P. Choi, T. Wu. Distributions of cherries and pitchforks for the Ford model, arXiv:2110.02850.\n[20] C. McDiarmid, C. Semple, D. Welsh (2015). Counting Phylogenetic Networks, Ann.Comb., 19:1,205–224.\n[21] A. McKenzie and M. A. Steel (2000). Distributions of cherries for two models of trees, Math. Biosci., 164:1, 81–92.\n[22] M. Pons and J. Batle (2021). Combinatorial characterization of a certain class of words and a conjectured connection with general subclasses of phylogenetic tree-child networks, Scientific Reports, 11, Article number: 21875.\n[23] N. A. Rosenberg (2006). The mean and variance of the numbers of r-pronged nodes and rcaterpillars in Yule generated genealogical trees, Ann. Comb., 10:1, 129–146.\n[24] T. Wu and K. P. Choi (2016). On joint subtree distributions under two evolutionary models, Theor. Popul. Biol., 108, 13–23.\n[25] L. Zhang. The Sackin index of simplex networks, arXiv:2112.15379. 描述 碩士
國立政治大學
應用數學系
108751020資料來源 http://thesis.lib.nccu.edu.tw/record/#G0108751020 資料類型 thesis dc.contributor.advisor 符麥克 zh_TW dc.contributor.advisor Michael Fuchs en_US dc.contributor.author (作者) 劉赫煊 zh_TW dc.contributor.author (作者) Liu, Hexuan en_US dc.creator (作者) 劉赫煊 zh_TW dc.creator (作者) Liu, Hexuan en_US dc.date (日期) 2022 en_US dc.date.accessioned 1-八月-2022 18:12:54 (UTC+8) - dc.date.available 1-八月-2022 18:12:54 (UTC+8) - dc.date.issued (上傳時間) 1-八月-2022 18:12:54 (UTC+8) - dc.identifier (其他 識別碼) G0108751020 en_US dc.identifier.uri (URI) https://ah.lib.nccu.edu.tw/item?item_id=160541 - dc.description (描述) 碩士 zh_TW dc.description (描述) 國立政治大學 zh_TW dc.description (描述) 應用數學系 zh_TW dc.description (描述) 108751020 zh_TW dc.description.abstract (摘要) 近年來，作為演化網路的眾多分類中最著名的子類之一，樹子網路吸引了許多數學家與生物學家的注意。然而直到幾年前，樹子網路的精確和漸進計數仍然很困難，遑論其它問題。在本碩論中，我們將回顧以往樹子網路及其變體的一些重要結果，並添加幾個新的結果。\n\n藉由組合學和概率論中的工具，我們實現的主要貢獻有：在單組分樹子網路下證明了最近的一個對於樹子網絡精確計數的猜想；此外，得到了第一個在均勻隨機選取樹子網路時的隨機結果；同時，還擴展了樹子網路的定義並將前人的和我們的結果推廣到這一新類；另外，也使先前對於有序樹子網路中圖案極限規律的研究更進一步，且提供了首個對一類演化網路中一般圖形的研究。\n\n該碩論的簡短概述如下：首先在第1章中，我們給出了樹子網路、樹子網路的擴展以及有序樹子網路的定義和基本性質；然後在第2章中，我們介紹了所用的工具。其次在第3和第4章，我們分別對樹子網路及其擴展進行研究。接著在第5章，我們將以往對於有序樹子網路的研究推廣到所有高度為1和2的圖案，再給出對於任意高度圖案的推論。最後在第6章，我們總結全文。 zh_TW dc.description.abstract (摘要) In recent years, as one of the most prominent subclass among the many different classes of phylogenetic networks, the class of tree-child networks has attracted the attention of many mathematicians and biologists. However, until a few years ago, both exact and asymptotic counting for tree-child networks was still difficult, not to mention other problems. In this thesis, we will review the most important previous results for tree-child networks and their variants and add several new results.\n\nOur main contributions, which are mainly proved with tools from Combinatorics and Probability Theory, are as follows. For a recent conjecture on the exact counting of tree-child\nnetworks, we give a proof for the special case when the tree-child network is a one-component network. In addition, we prove the first stochastic results for tree-child networks which are picked uniformly at random. Also, we can extend the definition of tree-child networks and generalize previous and our results to the new class. Moreover, we have taken the previous research on limit laws of patterns in ranked tree-child network a step further and provided the\nfirst general patterns study for a class of phylogenetic networks.\n\nA short outline of the thesis is as follows: in Chapter 1, we give definitions and show some basic properties for tree-child networks, their extensions and ranked tree-child networks. Then, in Chapter 2, we introduce our tools. In Chapter 3 and Chapter 4, we focus on results for tree-child networks and their extensions, respectively. Next in Chapter 5, we generalize the former study on patterns of ranked tree-child networkto all patterns of height 1 and 2 and make a conjecture for patterns of any height. Finally, we finish the thesis in Chapter 6 with a conclusion. en_US dc.description.tableofcontents 1 Introduction 1\n1.1 Phylogenetic trees and networks 1\n1.1.1 Phylogenetic trees 1\n1.1.2 Phylogenetic networks 3\n1.2 Tree-child networks 4\n1.3 Previous research and purpose of this work 8\n2 Tools 12\n2.1 Tools from Combinatorics 12\n2.2 Tools from Probability Theory 19\n3 Enumeration of bi-combining tree-child networks 24\n3.1 Results for $\\mathrm{OTC}_{n,k}$ 24\n3.2 Results for $\\mathrm{TC}_{n,k}$ 28\n3.3 Pons and Batle`s conjecture 32\n3.4 Bijection for $\\mathrm{OTC}_{n,k}$ 33\n4 Enumeration of d-combining tree-child networks 37\n4.1 Exact formula for $\\mathrm{OTC}_{n,k}^{[d]}$ 37\n4.2 Counting $\\mathrm{TC}_{n,k}^{[d]}$ by modified words 38\n4.3 Distributional and asymptotic results for $\\mathrm{OTC}_{n,k}^{[d]}$ and $\\mathrm{TC}_{n,k}^{[d]}$ 43\n4.3.1 Results for $\\mathrm{OTC}_{n,k}^{[d]}$ 44\n4.3.2 Results for $\\mathrm{TC}_{n,k}^{[d]}$ 45\n4.4 Some open problems 49\n5 Ranked tree-child networks 50\n5.1 Previous results 50\n5.2 Patterns of height1 51\n5.3 Patterns of height2 55\n5.4 A conjecture for patterns of any height 77\n6 Conclusion 78\nBibliography 80 zh_TW dc.format.extent 2003520 bytes - dc.format.mimetype application/pdf - dc.source.uri (資料來源) http://thesis.lib.nccu.edu.tw/record/#G0108751020 en_US dc.subject (關鍵詞) 演化網路 zh_TW dc.subject (關鍵詞) 樹子網路 zh_TW dc.subject (關鍵詞) 解析計數 zh_TW dc.subject (關鍵詞) 極限法則 zh_TW dc.subject (關鍵詞) 雙射法 zh_TW dc.subject (關鍵詞) 拉普拉斯方法 zh_TW dc.subject (關鍵詞) 動差估計 zh_TW dc.subject (關鍵詞) Phylogenetic network en_US dc.subject (關鍵詞) Tree-child network en_US dc.subject (關鍵詞) Analytic counting en_US dc.subject (關鍵詞) Limit laws en_US dc.subject (關鍵詞) Bijective proof, en_US dc.subject (關鍵詞) Laplace method en_US dc.subject (關鍵詞) Method of moments. II en_US dc.title (題名) 樹子網路及其變體的計數和分布結果 zh_TW dc.title (題名) Enumerative and Distributional Results for Tree-Child Networks and Their Variants en_US dc.type (資料類型) thesis en_US dc.relation.reference (參考文獻) [1] F. Bienvenu, A. Lambert, M. Steel (2022). Combinatorial and stochastic properties of ranked tree-child networks, Random Struct. Algor., 60(4), 653–689.\n[2] P. Billingsley (1995). Probability and Measure, third edition, Wiley Series in Probability and Mathematical Statistics, John Wiley & Sons, Inc., New York, 1995.\n[3] A. Caraceni, M. Fuchs, G.-R. Yu (2022). Bijections for ranked tree-child networks, Discrete Math., 345:9, 112944, 10 pages.\n[4] G. Cardona, G. Rossello, F. Valiente (2009). Comparison of tree-child phylogenetic networks. IEEE/ACM Trans. Comput. Biol. Bioinform. 6(4), 552–569.\n[5] G. Cardona and L. Zhang (2020). Counting tree-child networks and their subclasses, J.Comput.Syst. Sci., 114, 84–104.\n[6] H. Chang and M. Fuchs (2010). Limit theorems for patterns in phylogenetic trees, J. Math.Biol., 60:4, 481–512.\n[7] Y.-S. Chang, M. Fuchs, H. Liu, M. Wallner, G.-R. Yu (2022). Enumeration of d-combining Tree-Child Networks, LIPICS, Proceedings of the 33rd International Meeting on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms,\n225.\n[8] K. P. Choi, G. Kaur, T. Wu (2021). On asymptotic joint distributions of cherries and pitchforks for random phylogenetic trees, J. Math. Biol., 83:4, Paper No. 40, 34 pp.\n[9] K. P. Choi, A. Thompson, T. Wu (2020). On cherry and pitchfork distributions of random rooted and unrooted phylogenetic trees, Theor. Popul. Biol., 132, 92–104.\n[10] F. Disanto and T. Wiehe (2013). Exact enumeration of cherries and pitchforks in ranked trees under the coalescent model, Math. Biosci., 242:2, 195–200.\n[11] A. Elvey Price, W. Fang, M. Wallner (2021). Compacted binary trees admit a stretched exponential, J. Comb. Theory Ser. A, 177, Article 105306.\n[12] M. Fuchs, B. Gittenberger, M. Mansouri (2019). Counting phylogenetic networks with few reticulation vertices: tree-child and normal networks, Australas. J. Combin., 73:2, 385–423.\n[13] M. Fuchs, B. Gittenberger, M. Mansouri (2021). Counting phylogenetic networks with few reticulation vertices: exact enumeration and corrections, Australas. J. Combin., 82:2,\n257–282.\n[14] M. Fuchs, E.-Y. Huang, G.-R. Yu, E.-Y. Huang (2022). Counting phylogenetic networks with few reticulation vertices: a second approach, Discrete Appl. Math., in press.\n[15] M. Fuchs, H. Liu, G.-R. Yu. A short note on the exact counting of tree-child networks, arXiv:2110.03842.\n[16] M. Fuchs, H. Liu, T.-C. Yu. Limit theorems for patterns in ranked tree-child networks, arXiv:2204.07676.\n[17] M. Fuchs, G.-R. Yu, L. Zhang (2021). On the asymptotic growth of the number of tree-child networks, European J. Combin., 93, 103278, 20 pages.\n[18] C. Holmgren and S. Janson (2015). Limit laws for functions of fringe trees for binary search trees and recursive trees, Electron. J. Probab., 20, 1–51.\n[19] G. Kaur, K. P. Choi, T. Wu. Distributions of cherries and pitchforks for the Ford model, arXiv:2110.02850.\n[20] C. McDiarmid, C. Semple, D. Welsh (2015). Counting Phylogenetic Networks, Ann.Comb., 19:1,205–224.\n[21] A. McKenzie and M. A. Steel (2000). Distributions of cherries for two models of trees, Math. Biosci., 164:1, 81–92.\n[22] M. Pons and J. Batle (2021). Combinatorial characterization of a certain class of words and a conjectured connection with general subclasses of phylogenetic tree-child networks, Scientific Reports, 11, Article number: 21875.\n[23] N. A. Rosenberg (2006). The mean and variance of the numbers of r-pronged nodes and rcaterpillars in Yule generated genealogical trees, Ann. Comb., 10:1, 129–146.\n[24] T. Wu and K. P. Choi (2016). On joint subtree distributions under two evolutionary models, Theor. Popul. Biol., 108, 13–23.\n[25] L. Zhang. The Sackin index of simplex networks, arXiv:2112.15379. zh_TW dc.identifier.doi (DOI) 10.6814/NCCU202201049 en_US
