Loading...
|
Please use this identifier to cite or link to this item:
https://nccur.lib.nccu.edu.tw/handle/140.119/140217
|
| Title: | 譜系網路的計算：Galled Trees 與少量網點的 Tree-child Networks
Counting Phylogenetic Networks: Galled Trees and Tree-Child Networks with Few Reticulation Nodes |
| Authors: | 黃恩宇
Huang, En-Yu |
| Contributors: | 符麥克
Fuchs, Michael
黃恩宇
Huang, En-Yu |
| Keywords: | 譜系網路
元件圖
漸近估計
Phylogenetic networks
Component graphs
Asymptotic estimate |
| Date: | 2022 |
| Issue Date: | 2022-06-01 16:33:16 (UTC+8) |
| Abstract: | 譜系網路是演化生物學當中的一個重要工具，它們提供一個操作分類單元（operational taxonomic units）間關係的圖像化表示法，特別是演化歷史。在近年的研究當中，許多組合相關的問題諸如：實際數量的計算與漸近行為的估計已經慢慢被理解，在這篇論文當中，我們將探討在應用上常見的兩大主要譜系網路： galled trees 與 tree-child networks.
首先是 galled trees 的部分，在 \\cite{bouvel2020counting} 中，Bouvel 等人對 galled trees 實際數量的計算與漸近行為的估計有詳細的討論，然而，在實務上有兩個常見子類別─有 normal 與 one-component 性質的 galled trees─在這篇研究當中沒有被探討；在另外一篇研究當中 (\\cite{CZcounting}) ，Cardona 跟 Zhang 對 galled trees 以及上述的兩個子類別在實際數量上都做了詳細的計算，惟漸近估計的部分有所缺乏。我們將會提出三個類別 galled trees 數量的計算公式並討論他們的漸近表現，對這兩篇研究做出結合與延伸，此外，我們也會多考慮網點數量，給予漸近分布的結果。
計算具少量網點的 Tree-child networks 已經在許多研究中藉由不同的方法討論過，舉例來說， tree-child networks 的漸近表現在 \\cite{fuchs2018counting} 與 \\cite{fuchs2020counting} 二篇論文中已被解出，當葉子數$n$趨近於無限大時，具$k$個網點的 tree-child networks 的數量會逼近
$$
c_k \\left(\\frac{2}{e}\\right)^{n} n^{n+2k-1}.
$$
另一方面，在 \\cite{CZcounting} 中所提出透過 component graphs 來計算 tree-child networks 的方式也是有效的，我們延伸這個計算方式來得到更多網點時的計算公式，並比較先前以不同方式計算出來的結果，此外，透過 component graph的方法也對上述漸近行為提供了更直觀的證明，更進一步的，透過這個方法可以取得常數 $c_k$ 的一般式，即 $c_k = 2^{k-1}\\sqrt{2}/k!$。
Phylogenetic networks have become an important tool in evolutionary biology; they provide a graphical representation of the relationships between the operational taxonomic units and thus can be used for visualizing the evolutionary process. In recent years, many studies on combinatorial questions such as exact enumeration and asymptotic counting problems have been published for them. In this thesis, we investigate galled trees and tree-child networks, two classes of phylogenetic networks that are important in applications.
For galled trees, exact and asymptotic enumeration has been studied in [BGM20]. However, there are two important subclasses, namely normal and one-component galled trees which frequently occur in practice and which were not treated in [BGM20]. On the other hand, in [CZ20], the authors discussed galled trees as well as normal and one-component galled trees from an enumerative perspective but provided little asymptotic information. We will combine and continue the two works by giving for all three classes of galled trees exact formulas and derive the first order asymptotics of their numbers. Moreover, distributional results of the number of reticulation nodes will also be considered.
The enumeration of tree-child networks with few reticulation nodes has been studied in many papers through different approaches. For instance, the asymptotic counting problem was solved in [FGM19] and [FGM21] where it was shown that
their number has the first order asymptotics:
$$
c_k \\left(\\frac{2}{e}\\right)^{n} n^{n+2k-1},
$$
as the number of leaves n tends to∞, where k is the number of reticulation nodes and ck > 0 is a constant. Counting tree-child networks via component graphs is an effective way which was proposed in [CZ20]. We will extend this approach to obtain formulas for the number of tree-child networks with more reticulation nodes and compare them with the results from previous papers (where such results were
derived with different methods). Moreover, the counting method via component graphs also gives a more straightforward proof of the above asymptotic result; in
addition, it yields an easy expression for ck, namely, $c_k = 2^{k-1}\\sqrt{2}/k!$. |
| Reference: | [BGM20] Mathilde Bouvel, Philippe Gambette, and Marefatollah Mansouri.
Counting phylogenetic networks of level 1 and 2.
Journal of Mathematical Biology, 81(6):1357–1395, 2020.
[CZ20] Gabriel Cardona and Louxin Zhang.
Counting and enumerating tree-child networks and their subclasses.
Journal of Computer and SystemSciences, 114:84–104, 2020.
[FGM19] Michael Fuchs, Bernhard Gittenberger, and Marefatollah Mansouri.
Counting phylogenetic networks with few reticulation vertices: tree-child and normal networks.
Australas. J. Combin., 73:385–423, 2019.
[FGM21] Michael Fuchs, Bernhard Gittenberger, and Marefatollah Mansouri.
Counting phylogenetic networks with few reticulation vertices: exact enumeration and corrections.
Australas. J. Combin., 81:257–282, 2021.
[FHY21] Michael Fuchs, EnYu Huang, and GuanRu Yu.
Counting phylogenetic networks with few reticulation vertices: A second approach.
arXiv:2104.07842, 2021.
[FS09] Philippe Flajolet and Robert Sedgewick.
Analytic Combinatorics.
Cambridge University Press, 2009.
[FYZ21] Michael Fuchs, GuanRu Yu, and Louxin Zhang.
On the asymptotic growth of the number of tree-child networks.
European J. Combin., 93:Paper No. 103278, 20, 2021.
[MS00] Andy McKenzie and Mike Steel.
Distributions of cherries for two models of trees.
Mathematical biosciences, 164(1):81–92, 2000.
[PB21] Miquel Pons and Josep Batle.
On the exact counting of tree-child networks.
2021.
[SF13] Robert Sedgewick and Philippe Flajolet.
An Introduction to The Analysis of Algorithms.
Pearson Education India, 2013.
[Zha19] Louxin Zhang.
Generating normal networks via leaf insertion and nearest neighbor interchange.
BMC bioinformatics, 20(20):1–9, 2019. |
| Description: | 碩士
國立政治大學
應用數學系
108751014 |
| Source URI: | http://thesis.lib.nccu.edu.tw/record/#G0108751014 |
| Data Type: | thesis |
| DOI: | 10.6814/NCCU202200447 |
| Appears in Collections: | [應用數學系] 學位論文
|
Files in This Item:
| File |
Description |
Size | Format | |
|---|
| 101401.pdf | | 660Kb | Adobe PDF2 | 97 | View/Open |
|
All items in 政大典藏 are protected by copyright, with all rights reserved.
|
