{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:05:02Z","timestamp":1787321102409,"version":"build-2736575974"},"reference-count":29,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","funder":[{"DOI":"10.13039\/501100009023","name":"Precursory Research for Embryonic Science and Technology","doi-asserted-by":"publisher","award":["JPMJPR16EB"],"award-info":[{"award-number":["JPMJPR16EB"]}],"id":[{"id":"10.13039\/501100009023","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100009023","name":"Precursory Research for Embryonic Science and Technology","doi-asserted-by":"publisher","award":["JPMJPR1929"],"award-info":[{"award-number":["JPMJPR1929"]}],"id":[{"id":"10.13039\/501100009023","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2021,1]]},"abstract":"<jats:p>Attempting to recognize a tree inside a phylogenetic network is a fundamental undertaking in evolutionary analysis. In the last few years, therefore, \u201ctree-based\u201d phylogenetic networks, which are defined by a spanning tree called a \u201csubdivision tree\u201d that is an embedding of a phylogenetic tree on the same leaf-set, have attracted the attention of many theoretical biologists. However, the application of such networks is still not easy, due to many important computational problems whose time complexities are unknown or not clearly understood. In this paper, we provide a general framework for solving those various old or new problems on tree-based phylogenetic networks from a coherent perspective, rather than analyzing the complexity of each individual problem or developing an algorithm one by one. More precisely, we establish a structure theorem that gives a way to canonically decompose any rooted binary phylogenetic network $N$ into maximal zig-zag trails that are uniquely determined by $N$, and furthermore use it to characterize the set of subdivision trees of $N$ in the form of a direct product. From these main results, we derive a series of linear time (and linear time delay) algorithms for solving the following problems: given a rooted binary phylogenetic network $N$, (1) determine whether or not $N$ has a subdivision tree and find one if there exists any (decision\/search problems); (2) measure the deviation of $N$ from being tree-based (deviation quantification problem); (3) compute the number of subdivision trees of $N$ (counting problem); (4) list all subdivision trees of $N$ (enumeration problem); and (5) find a subdivision tree to maximize or minimize a prescribed objective function (optimization problem). All algorithms proposed here are optimal in terms of time complexity. Our results not only imply and unify various known results in the relevant literature, but also answer many open questions and moreover enable novel applications, such as the estimation of a maximum likelihood tree underlying a tree-based network. The results and algorithms in this paper also apply for a special class of rooted nonbinary phylogenetic networks.<\/jats:p>","DOI":"10.1137\/19m1297403","type":"journal-article","created":{"date-parts":[[2021,10,19]],"date-time":"2021-10-19T10:50:34Z","timestamp":1634640634000},"page":"2490-2516","source":"Crossref","is-referenced-by-count":5,"title":["A Structure Theorem for Rooted Binary Phylogenetic Networks and Its Implications for Tree-Based Networks"],"prefix":"10.1137","volume":"35","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8825-6331","authenticated-orcid":true,"given":"Momoko","family":"Hayamizu","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2021,10,19]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1007\/s11538-016-0169-x"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2018.05.010"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1093\/molbev\/msh018"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2019.12.019"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2021.01.005"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1007\/s11538-017-0381-3"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1016\/j.jtbi.2018.03.011"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1016\/j.aam.2017.08.003"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1093\/sysbio\/syv037"},{"key":"atypb10","unstructured":"L. A. Goldberg,\n                      Efficient Algorithms for Listing Combinatorial Structures\n                      , Disting. Diss. Comput. Sci. 5, Cambridge University Press, 2009."},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1016\/j.jtbi.2016.02.023"},{"key":"atypb12","unstructured":"M. Hayamizu,\n                      A linear time algorithm for counting the number of support trees for a binary phylogenetic network\n                      , in The 22nd Annual New Zealand Phylogenomics Meeting (Portobello 2018): The Interface of Mathematics and Biology, Portobello, New Zealand, 2018."},{"key":"atypb13","doi-asserted-by":"crossref","unstructured":"M. Hayamizu and K. Makino,\n                      Ranking Top-k Trees in Tree-Based Phylogenetic Networks\n                      , preprint,https:\/\/arxiv.org\/abs\/1904.12432, 2019.","DOI":"10.21203\/rs.2.15349\/v1"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1016\/j.mbs.2018.06.005"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1137\/0202019"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1093\/molbev\/msj030"},{"key":"atypb17","doi-asserted-by":"crossref","unstructured":"D. H. Huson, R. Rupp, and C. Scornavacca,\n                      Phylogenetic Networks: Concepts, Algorithms and Applications\n                      , Cambridge University Press, 2010.","DOI":"10.1017\/CBO9780511974076"},{"key":"atypb18","unstructured":"L. Jetten,\n                      Characterising Tree-Based Phylogenetic Networks\n                      , Bachelor thesis, TU Delft repository, 2015, uuid: fda2636d-0ed5-4dd2-bacf-8abbbad8994e."},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1109\/TCBB.2016.2615918"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(88)90065-8"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1137\/12089394X"},{"key":"atypb22","unstructured":"A. Mooiman,\n                      Computing Measures for Tree-Basedness of Phylogenetic Networks\n                      , Bachelor thesis, TU Delft repository, 2018, uuid: 7739fe8e-e2b2-493a-983d-d1a47603f2eb."},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1007\/s00285-018-1296-9"},{"key":"atypb24","unstructured":"B. Schr\u00f6der,\n                      Ordered Sets: An Introduction with Connections from Combinatorics to Topology\n                      , 2nd ed., Birkh\u00e4user, 2016."},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1007\/s11538-015-0132-2"},{"key":"atypb26","doi-asserted-by":"crossref","unstructured":"M. Steel,\n                      Phylogeny: Discrete and Random Processes in Evolution\n                      , SIAM, 2016,https:\/\/doi.org\/10.1137\/1.9781611974485.","DOI":"10.1137\/1.9781611974485"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1137\/0208032"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2010.07.027"},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1089\/cmb.2015.0228"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/19M1297403","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:06:27Z","timestamp":1787317587000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/19M1297403"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1]]},"references-count":29,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,1]]}},"alternative-id":["10.1137\/19M1297403"],"URL":"https:\/\/doi.org\/10.1137\/19m1297403","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,1]]}}}