Loading...
|
Please use this identifier to cite or link to this item:
https://nccur.lib.nccu.edu.tw/handle/140.119/141181
|
| Title: | 樹子網路及其變體的計數和分布結果
Enumerative and Distributional Results for Tree-Child Networks and Their Variants |
| Authors: | 劉赫煊
Liu, Hexuan |
| Contributors: | 符麥克
Michael Fuchs
劉赫煊
Liu, Hexuan |
| Keywords: | 演化網路
樹子網路
解析計數
極限法則
雙射法
拉普拉斯方法
動差估計
Phylogenetic network
Tree-child network
Analytic counting
Limit laws
Bijective proof,
Laplace method
Method of moments. II |
| Date: | 2022 |
| Issue Date: | 2022-08-01 18:12:54 (UTC+8) |
| Abstract: | 近年來，作為演化網路的眾多分類中最著名的子類之一，樹子網路吸引了許多數學家與生物學家的注意。然而直到幾年前，樹子網路的精確和漸進計數仍然很困難，遑論其它問題。在本碩論中，我們將回顧以往樹子網路及其變體的一些重要結果，並添加幾個新的結果。
藉由組合學和概率論中的工具，我們實現的主要貢獻有：在單組分樹子網路下證明了最近的一個對於樹子網絡精確計數的猜想；此外，得到了第一個在均勻隨機選取樹子網路時的隨機結果；同時，還擴展了樹子網路的定義並將前人的和我們的結果推廣到這一新類；另外，也使先前對於有序樹子網路中圖案極限規律的研究更進一步，且提供了首個對一類演化網路中一般圖形的研究。
該碩論的簡短概述如下：首先在第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.
Our 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
networks, 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
first general patterns study for a class of phylogenetic networks.
A 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. |
| 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.
[2] P. Billingsley (1995). Probability and Measure, third edition, Wiley Series in Probability and Mathematical Statistics, John Wiley & Sons, Inc., New York, 1995.
[3] A. Caraceni, M. Fuchs, G.-R. Yu (2022). Bijections for ranked tree-child networks, Discrete Math., 345:9, 112944, 10 pages.
[4] G. Cardona, G. Rossello, F. Valiente (2009). Comparison of tree-child phylogenetic networks. IEEE/ACM Trans. Comput. Biol. Bioinform. 6(4), 552–569.
[5] G. Cardona and L. Zhang (2020). Counting tree-child networks and their subclasses, J.Comput.Syst. Sci., 114, 84–104.
[6] H. Chang and M. Fuchs (2010). Limit theorems for patterns in phylogenetic trees, J. Math.Biol., 60:4, 481–512.
[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,
225.
[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.
[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.
[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.
[11] A. Elvey Price, W. Fang, M. Wallner (2021). Compacted binary trees admit a stretched exponential, J. Comb. Theory Ser. A, 177, Article 105306.
[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.
[13] M. Fuchs, B. Gittenberger, M. Mansouri (2021). Counting phylogenetic networks with few reticulation vertices: exact enumeration and corrections, Australas. J. Combin., 82:2,
257–282.
[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.
[15] M. Fuchs, H. Liu, G.-R. Yu. A short note on the exact counting of tree-child networks, arXiv:2110.03842.
[16] M. Fuchs, H. Liu, T.-C. Yu. Limit theorems for patterns in ranked tree-child networks, arXiv:2204.07676.
[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.
[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.
[19] G. Kaur, K. P. Choi, T. Wu. Distributions of cherries and pitchforks for the Ford model, arXiv:2110.02850.
[20] C. McDiarmid, C. Semple, D. Welsh (2015). Counting Phylogenetic Networks, Ann.Comb., 19:1,205–224.
[21] A. McKenzie and M. A. Steel (2000). Distributions of cherries for two models of trees, Math. Biosci., 164:1, 81–92.
[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.
[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.
[24] T. Wu and K. P. Choi (2016). On joint subtree distributions under two evolutionary models, Theor. Popul. Biol., 108, 13–23.
[25] L. Zhang. The Sackin index of simplex networks, arXiv:2112.15379. |
| Description: | 碩士
國立政治大學
應用數學系
108751020 |
| Source URI: | http://thesis.lib.nccu.edu.tw/record/#G0108751020 |
| Data Type: | thesis |
| DOI: | 10.6814/NCCU202201049 |
| Appears in Collections: | [應用數學系] 學位論文
|
Files in This Item:
| File |
Description |
Size | Format | |
|---|
| 102001.pdf | | 1956Kb | Adobe PDF2 | 109 | View/Open |
|
All items in 政大典藏 are protected by copyright, with all rights reserved.
|
