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

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

English | 正體中文 | 简体中文 | Post-Print筆數 : 27 | 全文笔数/总笔数 : 113318/144297 (79%)
造访人次 : 51034580 在线人数 : 909

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

搜寻范围

查询小技巧：

您可在西文检索词汇前后加上"双引号"，以获取较精准的检索结果

若欲以作者姓名搜寻，建议至进阶搜寻限定作者字段，可获得较完整数据

进阶搜寻

主页 ‧ 登入 ‧ 上传 ‧ 说明 ‧ 关于政大典藏 ‧ 管理

到手机版

政大機構典藏 > 理學院 > 應用數學系 > 學位論文 > Item 140.119/141181

请使用永久网址来引用或连结此文件: https://nccur.lib.nccu.edu.tw/handle/140.119/141181

题名:	樹子網路及其變體的計數和分布結果 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
上传时间:	2022-08-01 18:12:54 (UTC+8)
摘要:	近年來，作為演化網路的眾多分類中最著名的子類之一，樹子網路吸引了許多數學家與生物學家的注意。然而直到幾年前，樹子網路的精確和漸進計數仍然很困難，遑論其它問題。在本碩論中，我們將回顧以往樹子網路及其變體的一些重要結果，並添加幾個新的結果。藉由組合學和概率論中的工具，我們實現的主要貢獻有：在單組分樹子網路下證明了最近的一個對於樹子網絡精確計數的猜想；此外，得到了第一個在均勻隨機選取樹子網路時的隨機結果；同時，還擴展了樹子網路的定義並將前人的和我們的結果推廣到這一新類；另外，也使先前對於有序樹子網路中圖案極限規律的研究更進一步，且提供了首個對一類演化網路中一般圖形的研究。該碩論的簡短概述如下：首先在第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.
參考文獻:	[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.
描述:	碩士國立政治大學應用數學系 108751020
資料來源:	http://thesis.lib.nccu.edu.tw/record/#G0108751020
数据类型:	thesis
DOI:	10.6814/NCCU202201049
显示于类别:	[應用數學系] 學位論文

文件中的档案:

档案	描述	大小	格式	浏览次数
102001.pdf		1956Kb	Adobe PDF2	96	检视/开启

在政大典藏中所有的数据项都受到原著作权保护.

社群 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 © - 回馈