譜系網路的計算：Galled Trees 與少量網點的 Tree-child Networks

Abstract

譜系網路是演化生物學當中的一個重要工具，它們提供一個操作分類單元（operational taxonomic units）間關係的圖像化表示法，特別是演化歷史。在近年的研究當中，許多組合相關的問題諸如：實際數量的計算與漸近行為的估計已經慢慢被理解，在這篇論文當中，我們將探討在應用上常見的兩大主要譜系網路： galled trees 與 tree-­child networks.\n\n首先是 galled trees 的部分，在 \\cite{bouvel2020counting} 中，Bouvel 等人對 galled trees 實際數量的計算與漸近行為的估計有詳細的討論，然而，在實務上有兩個常見子類別─有 normal 與 one-component 性質的 galled trees─在這篇研究當中沒有被探討；在另外一篇研究當中 (\\cite{CZcounting}) ，Cardona 跟 Zhang 對 galled trees 以及上述的兩個子類別在實際數量上都做了詳細的計算，惟漸近估計的部分有所缺乏。我們將會提出三個類別 galled trees 數量的計算公式並討論他們的漸近表現，對這兩篇研究做出結合與延伸，此外，我們也會多考慮網點數量，給予漸近分布的結果。\n\n計算具少量網點的 Tree-child networks 已經在許多研究中藉由不同的方法討論過，舉例來說， tree-child networks 的漸近表現在 \\cite{fuchs2018counting} 與 \\cite{fuchs2020counting} 二篇論文中已被解出，當葉子數$n$趨近於無限大時，具$k$個網點的 tree-child networks 的數量會逼近\n$$\nc_k \\left(\\frac{2}{e}\\right)^{n} n^{n+2k-1}.\n$$\n另一方面，在 \\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.\nFor 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.\nThe 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\ntheir number has the first order asymptotics:\n$$\nc_k \\left(\\frac{2}{e}\\right)^{n} n^{n+2k-1},\n$$\nas 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\nderived with different methods). Moreover, the counting method via component graphs also gives a more straightforward proof of the above asymptotic result; in\naddition, it yields an easy expression for ck, namely, $c_k = 2^{k-1}\\sqrt{2}/k!$.