{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,14]],"date-time":"2026-02-14T21:18:53Z","timestamp":1771103933145,"version":"3.50.1"},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"S20","license":[{"start":{"date-parts":[[2019,12,1]],"date-time":"2019-12-01T00:00:00Z","timestamp":1575158400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2019,12,17]],"date-time":"2019-12-17T00:00:00Z","timestamp":1576540800000},"content-version":"vor","delay-in-days":16,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["BMC Bioinformatics"],"published-print":{"date-parts":[[2019,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:sec>\n<jats:title>Background<\/jats:title>\n<jats:p>Galled trees are studied as a recombination model in theoretical population genetics. This class of phylogenetic networks has been generalized to tree-child networks and other network classes by relaxing a structural condition imposed on galled trees. Although these networks are simple, their topological structures have yet to be fully understood.<\/jats:p>\n<\/jats:sec><jats:sec>\n<jats:title>Results<\/jats:title>\n<jats:p>It is well-known that all phylogenetic trees on <jats:italic>n<\/jats:italic> taxa can be generated by the insertion of the <jats:italic>n<\/jats:italic>-th taxa to each edge of all the phylogenetic trees on <jats:italic>n<\/jats:italic>\u22121 taxa. We prove that all tree-child (resp. normal) networks with <jats:italic>k<\/jats:italic> reticulate nodes on <jats:italic>n<\/jats:italic> taxa can be uniquely generated via three operations from all the tree-child (resp. normal) networks with <jats:italic>k<\/jats:italic>\u22121 or <jats:italic>k<\/jats:italic> reticulate nodes on <jats:italic>n<\/jats:italic>\u22121 taxa. Applying this result to counting rooted phylogenetic networks, we show that there are exactly <jats:inline-formula><jats:alternatives><jats:tex-math>$\\frac {(2n)!}{2^{n} (n-1)!}-2^{n-1} n!$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mfrac><mml:mrow><mml:mo>(<\/mml:mo><mml:mn>2<\/mml:mn><mml:mi>n<\/mml:mi><mml:mo>)<\/mml:mo><mml:mo>!<\/mml:mo><\/mml:mrow><mml:mrow><mml:msup><mml:mrow><mml:mn>2<\/mml:mn><\/mml:mrow><mml:mrow><mml:mi>n<\/mml:mi><\/mml:mrow><\/mml:msup><mml:mo>(<\/mml:mo><mml:mi>n<\/mml:mi><mml:mo>\u2212<\/mml:mo><mml:mn>1<\/mml:mn><mml:mo>)<\/mml:mo><mml:mo>!<\/mml:mo><\/mml:mrow><\/mml:mfrac><mml:mo>\u2212<\/mml:mo><mml:msup><mml:mrow><mml:mn>2<\/mml:mn><\/mml:mrow><mml:mrow><mml:mi>n<\/mml:mi><mml:mo>\u2212<\/mml:mo><mml:mn>1<\/mml:mn><\/mml:mrow><\/mml:msup><mml:mi>n<\/mml:mi><mml:mo>!<\/mml:mo><\/mml:math><\/jats:alternatives><\/jats:inline-formula> binary phylogenetic networks with one reticulate node on <jats:italic>n<\/jats:italic> taxa.<\/jats:p>\n<\/jats:sec><jats:sec>\n<jats:title>Conclusions<\/jats:title>\n<jats:p>The work makes two contributions to understand normal networks. One is a generalization of an enumeration procedure for phylogenetic trees into one for normal networks. Another is simple formulas for counting normal networks and phylogenetic networks that have only one reticulate node.<\/jats:p>\n<\/jats:sec>","DOI":"10.1186\/s12859-019-3209-3","type":"journal-article","created":{"date-parts":[[2019,12,17]],"date-time":"2019-12-17T01:02:24Z","timestamp":1576544544000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["Generating normal networks via leaf insertion and nearest neighbor interchange"],"prefix":"10.1186","volume":"20","author":[{"given":"Louxin","family":"Zhang","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,12,17]]},"reference":[{"issue":"5423","key":"3209_CR1","doi-asserted-by":"publisher","first-page":"2124","DOI":"10.1126\/science.284.5423.2124","volume":"284","author":"WF Doolittle","year":"1999","unstructured":"Doolittle WF. Phylogenetic classification and the universal tree. Science. 1999; 284(5423):2124\u20138.","journal-title":"Science"},{"key":"3209_CR2","doi-asserted-by":"publisher","DOI":"10.7551\/mitpress\/9432.001.0001","volume-title":"ReCombinatorics: the Algorithmics of Ancestral Recombination Graphs and Explicit Phylogenetic Networks","author":"D Gusfield","year":"2014","unstructured":"Gusfield D. ReCombinatorics: the Algorithmics of Ancestral Recombination Graphs and Explicit Phylogenetic Networks. Cambridge, USA: MIT Press; 2014."},{"issue":"7","key":"3209_CR3","doi-asserted-by":"publisher","first-page":"3801","DOI":"10.1073\/pnas.96.7.3801","volume":"96","author":"R Jain","year":"1999","unstructured":"Jain R, Rivera MC, Lake JA. Horizontal gene transfer among genomes: the complexity hypothesis. Proc Natl Acad Sci. 1999; 96(7):3801\u20136.","journal-title":"Proc Natl Acad Sci"},{"key":"3209_CR4","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511974076","volume-title":"Phylogenetic Networks: Concepts, Algorithms and Applications","author":"DH Huson","year":"2010","unstructured":"Huson DH, Rupp R, Scornavacca C. Phylogenetic Networks: Concepts, Algorithms and Applications. Cambridge, UK: Cambridge University Press; 2010."},{"key":"3209_CR5","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974485","volume-title":"Phylogeny: Discrete and Random Processes in Evolution","author":"M Steel","year":"2016","unstructured":"Steel M. Phylogeny: Discrete and Random Processes in Evolution. Philadelphia, USA: SIAM; 2016."},{"issue":"5","key":"3209_CR6","doi-asserted-by":"publisher","first-page":"722","DOI":"10.1145\/1183907.1183909","volume":"53","author":"B Chor","year":"2006","unstructured":"Chor B, Tuller T. Finding a maximum likelihood tree is hard. J ACM (JACM). 2006; 53(5):722\u201344.","journal-title":"J ACM (JACM)"},{"issue":"1","key":"3209_CR7","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1016\/S0196-8858(82)80004-3","volume":"3","author":"LR Foulds","year":"1982","unstructured":"Foulds LR, Graham RL. The steiner problem in phylogeny is np-complete. Adv Appl Math. 1982; 3(1):43\u20139.","journal-title":"Adv Appl Math"},{"key":"3209_CR8","volume-title":"Inferring Phylogenies, vol. 2","author":"J Felsenstein","year":"2004","unstructured":"Felsenstein J. Inferring Phylogenies, vol. 2. Sunderland: Sinauer Associates; 2004."},{"issue":"46","key":"3209_CR9","doi-asserted-by":"publisher","first-page":"16448","DOI":"10.1073\/pnas.1407950111","volume":"111","author":"Y Yu","year":"2014","unstructured":"Yu Y, Dong J, Liu KJ, Nakhleh L. Maximum likelihood inference of reticulate evolutionary histories. Proc Natl Acad Sci. 2014; 111(46):16448\u201353.","journal-title":"Proc Natl Acad Sci"},{"key":"3209_CR10","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.jtbi.2017.03.032","volume":"423","author":"M Bordewich","year":"2017","unstructured":"Bordewich M, Linz S, Semple C. Lost in space? Generalising subtree prune and regraft to spaces of phylogenetic networks. J Theor Biol. 2017; 423:1\u201312.","journal-title":"J Theor Biol"},{"issue":"5","key":"3209_CR11","doi-asserted-by":"publisher","first-page":"1229","DOI":"10.1007\/s00285-017-1171-0","volume":"76","author":"A Francis","year":"2018","unstructured":"Francis A, Huber KT, Moulton V, Wu T. Bounds for phylogenetic network space metrics. J Math Biol. 2018; 76(5):1229\u201348.","journal-title":"J Math Biol"},{"issue":"8","key":"3209_CR12","doi-asserted-by":"publisher","first-page":"1005611","DOI":"10.1371\/journal.pcbi.1005611","volume":"13","author":"P Gambette","year":"2017","unstructured":"Gambette P, Van Iersel L, Jones M, Lafond M, Pardi F, Scornavacca C. Rearrangement moves on rooted phylogenetic networks. PLoS Comput Biol. 2017; 13(8):1005611.","journal-title":"PLoS Comput Biol"},{"issue":"3","key":"3209_CR13","doi-asserted-by":"publisher","first-page":"699","DOI":"10.1007\/s00285-015-0899-7","volume":"72","author":"KT Huber","year":"2016","unstructured":"Huber KT, Linz S, Moulton V, Wu T. Spaces of phylogenetic networks from generalized nearest-neighbor interchange operations. J Math Biol. 2016; 72(3):699\u2013725.","journal-title":"J Math Biol"},{"key":"3209_CR14","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1016\/j.jtbi.2016.05.030","volume":"404","author":"KT Huber","year":"2016","unstructured":"Huber KT, Moulton V, Wu T. Transforming phylogenetic networks: Moving beyond tree space. J Theor Biol. 2016; 404:30\u20139.","journal-title":"J Theor Biol"},{"issue":"8","key":"3209_CR15","doi-asserted-by":"publisher","first-page":"2177","DOI":"10.1007\/s11538-018-0452-0","volume":"80","author":"R Janssen","year":"2018","unstructured":"Janssen R, Jones M, Erdo\u030bs PL, Van Iersel L, Scornavacca C. Exploring the tiers of rooted phylogenetic network space using tail moves. Bull Math Biol. 2018; 80(8):2177\u2013208.","journal-title":"Bull Math Biol"},{"key":"3209_CR16","doi-asserted-by":"crossref","first-page":"2","DOI":"10.37236\/7860","volume":"26","author":"J Klawitter","year":"2019","unstructured":"Klawitter J, Linz S. On the subnet prune and regraft distance. Electron J Combin. 2019; 26:2\u20133.","journal-title":"Electron J Combin"},{"issue":"4","key":"3209_CR17","doi-asserted-by":"publisher","first-page":"459","DOI":"10.1287\/ijoc.1040.0099","volume":"16","author":"D Gusfield","year":"2004","unstructured":"Gusfield D, Eddhu S, Langley C. The fine structure of galls in phylogenetic networks. INFORMS J Comput. 2004; 16(4):459\u201369.","journal-title":"INFORMS J Comput"},{"issue":"1","key":"3209_CR18","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1089\/106652701300099119","volume":"8","author":"L Wang","year":"2001","unstructured":"Wang L, Zhang K, Zhang L. Perfect phylogenetic networks with recombination. J Comput Biol. 2001; 8(1):69\u201378.","journal-title":"J Comput Biol"},{"key":"3209_CR19","doi-asserted-by":"crossref","unstructured":"Cardona G, Rossello F, Valiente G. IEEE\/ACM Trans Comput Biol Bioinforma (TCBB). 2009; 6(4):552\u2013569.","DOI":"10.1109\/TCBB.2007.70270"},{"issue":"5","key":"3209_CR20","doi-asserted-by":"publisher","first-page":"1709","DOI":"10.1007\/s11538-006-9187-4","volume":"69","author":"SJ Willson","year":"2007","unstructured":"Willson SJ. Unique determination of some homoplasies at hybridization events. Bull Math Biol. 2007; 69(5):1709\u201325.","journal-title":"Bull Math Biol"},{"issue":"5","key":"3209_CR21","doi-asserted-by":"publisher","first-page":"768","DOI":"10.1093\/sysbio\/syv037","volume":"64","author":"AR Francis","year":"2015","unstructured":"Francis AR, Steel M. Which phylogenetic networks are merely trees with additional arcs?Syst Biol. 2015; 64(5):768\u201377.","journal-title":"Syst Biol"},{"issue":"7","key":"3209_CR22","doi-asserted-by":"publisher","first-page":"553","DOI":"10.1089\/cmb.2015.0228","volume":"23","author":"L Zhang","year":"2016","unstructured":"Zhang L. On tree-based phylogenetic networks. J Comput Biol. 2016; 23(7):553\u201365.","journal-title":"J Comput Biol"},{"key":"3209_CR23","volume-title":"Bioinformatics and Phylogenetics","author":"L Zhang","year":"2019","unstructured":"Zhang L. Clusters, trees, and phylogenetic network classes. In: Bioinformatics and Phylogenetics. New York: Springer: 2019. p. 277\u2013315."},{"issue":"3","key":"3209_CR24","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1089\/cmb.2018.0220","volume":"26","author":"AD Gunawan","year":"2019","unstructured":"Gunawan AD, Yan H, Zhang L. Compression of phylogenetic networks and algorithm for the tree containment problem. J Comput Biol. 2019; 26(3):285\u201394.","journal-title":"J Comput Biol"},{"key":"3209_CR25","unstructured":"Bickner DR. On normal networks. PhD thesis, Iowa State University, Department of Mathematics. 2012."},{"key":"3209_CR26","unstructured":"Bouvel M, Gambette P, Mansouri M. Counting level-k phylogenetic networks. arXiv preprint arXiv:1909.10460. 2019."},{"issue":"9","key":"3209_CR27","doi-asserted-by":"publisher","first-page":"e1007347","DOI":"10.1371\/journal.pcbi.1007347","volume":"15","author":"G Cardona","year":"2019","unstructured":"Cardona G, Pons JC, Scornavacca C. Generation of Binary Tree-Child phylogenetic networks. PLoS Computat Biol. 2019; 15(9):e1007347.","journal-title":"PLoS Computat Biol"},{"issue":"2","key":"3209_CR28","first-page":"385","volume":"73","author":"M Fuchs","year":"2019","unstructured":"Fuchs M, Gittenberger B, Mansouri M. Counting phylogenetic networks with few reticulation vertices: tree-child and normal networks. Australas J Comb. 2019; 73(2):385\u2013423.","journal-title":"Australas J Comb"},{"issue":"1","key":"3209_CR29","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1007\/s00026-015-0260-2","volume":"19","author":"C McDiarmid","year":"2015","unstructured":"McDiarmid C, Semple C, Welsh D. Counting phylogenetic networks. Ann Comb. 2015; 19(1):205\u201324.","journal-title":"Ann Comb"},{"key":"3209_CR30","doi-asserted-by":"crossref","unstructured":"Semple C, Steel M. IEEE\/ACM Trans Comput Biol Bioinforma (TCBB). 2006; 3(1):84.","DOI":"10.1109\/TCBB.2006.14"},{"key":"3209_CR31","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139871495","volume-title":"Catalan Numbers","author":"RP Stanley","year":"2015","unstructured":"Stanley RP. Catalan Numbers. Cambridge, UK: Cambridge University Press; 2015."}],"container-title":["BMC Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1186\/s12859-019-3209-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1186\/s12859-019-3209-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1186\/s12859-019-3209-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,12,16]],"date-time":"2020-12-16T00:14:48Z","timestamp":1608077688000},"score":1,"resource":{"primary":{"URL":"https:\/\/bmcbioinformatics.biomedcentral.com\/articles\/10.1186\/s12859-019-3209-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,12]]},"references-count":31,"journal-issue":{"issue":"S20","published-print":{"date-parts":[[2019,12]]}},"alternative-id":["3209"],"URL":"https:\/\/doi.org\/10.1186\/s12859-019-3209-3","relation":{},"ISSN":["1471-2105"],"issn-type":[{"value":"1471-2105","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,12]]},"assertion":[{"value":"17 December 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"This research did not involve any human subjects, human material, or human data. The ethics approval is not applicable.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethics approval and consent to participate"}},{"value":"Not applicable.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent for publication"}},{"value":"The author declares that he has no competing interests.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"642"}}