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

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

English | 正體中文 | 简体中文 | Post-Print筆數 : 27 | 全文筆數/總筆數 : 114205/145239 (79%)
造訪人次 : 52936163 線上人數 : 555

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

搜尋範圍

查詢小技巧：

您可在西文檢索詞彙前後加上"雙引號"，以獲取較精準的檢索結果

若欲以作者姓名搜尋，建議至進階搜尋限定作者欄位，可獲得較完整資料

進階搜尋

主頁 ‧ 登入 ‧ 上傳 ‧ 說明 ‧ 關於政大典藏 ‧ 管理

到手機版

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

請使用永久網址來引用或連結此文件: https://nccur.lib.nccu.edu.tw/handle/140.119/140217

題名:	譜系網路的計算：Galled Trees 與少量網點的 Tree-child Networks Counting Phylogenetic Networks: Galled Trees and Tree-Child Networks with Few Reticulation Nodes
作者:	黃恩宇 Huang, En-Yu
貢獻者:	符麥克 Fuchs, Michael 黃恩宇 Huang, En-Yu
關鍵詞:	譜系網路元件圖漸近估計 Phylogenetic networks Component graphs Asymptotic estimate
日期:	2022
上傳時間:	2022-06-01 16:33:16 (UTC+8)
摘要:	譜系網路是演化生物學當中的一個重要工具，它們提供一個操作分類單元（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!$.
參考文獻:	[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.
描述:	碩士國立政治大學應用數學系 108751014
資料來源:	http://thesis.lib.nccu.edu.tw/record/#G0108751014
資料類型:	thesis
DOI:	10.6814/NCCU202200447
顯示於類別:	[應用數學系] 學位論文

文件中的檔案:

檔案	描述	大小	格式	瀏覽次數
101401.pdf		660Kb	Adobe PDF2	97	檢視/開啟

在政大典藏中所有的資料項目都受到原著作權保護.

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