政大機構典藏-National Chengchi University Institutional Repository(NCCUR):Item 140.119/141181

政大機構典藏-National Chengchi University Institutional Repository(NCCUR):Item 140.119/141181

English | 正體中文 | 简体中文 | Post-Print筆數 : 27 | Items with full text/Total items : 113325/144300 (79%)
Visitors : 51187159 Online Users : 863

RC Version 6.0 © Powered By DSPACE, MIT. Enhanced by NTU Library IR team.

Scope

please add "double quotation mark" for query phrases to get precise results

please goto advance search for comprehansive author search

Adv. Search

Home ‧ Login ‧ Upload ‧ Help ‧ About ‧ Administer

Goto mobile version

政大典藏 > College of Science > Department of Mathematical Sciences > Theses > Item 140.119/141181

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:	[Department of Mathematical Sciences] Theses

Files in This Item:

File	Description	Size	Format
102001.pdf		1956Kb	Adobe PDF2	99	View/Open

All items in 政大典藏 are protected by copyright, with all rights reserved.

社群 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 © - Feedback