{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,6,22]],"date-time":"2024-06-22T16:00:07Z","timestamp":1719072007943},"reference-count":24,"publisher":"Oxford University Press (OUP)","issue":"17","license":[{"start":{"date-parts":[[2016,11,10]],"date-time":"2016-11-10T00:00:00Z","timestamp":1478736000000},"content-version":"vor","delay-in-days":73,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016,9,1]]},"abstract":"Abstract<\/jats:title>\n \n Motivation<\/jats:title>\n Genetic material is transferred in a non-reproductive manner across species more frequently than commonly thought, particularly in the bacteria kingdom. On one hand, extant genomes are thus more properly considered as a fusion product of both reproductive and non-reproductive genetic transfers. This has motivated researchers to adopt phylogenetic networks to study genome evolution. On the other hand, a gene\u2019s evolution is usually tree-like and has been studied for over half a century. Accordingly, the relationships between phylogenetic trees and networks are the basis for the reconstruction and verification of phylogenetic networks. One important problem in verifying a network model is determining whether or not certain existing phylogenetic trees are displayed in a phylogenetic network. This problem is formally called the tree containment problem. It is NP-complete even for binary phylogenetic networks.<\/jats:p>\n <\/jats:sec>\n \n Results<\/jats:title>\n We design an exponential time but efficient method for determining whether or not a phylogenetic tree is displayed in an arbitrary phylogenetic network. It is developed on the basis of the so-called reticulation-visible property of phylogenetic networks.<\/jats:p>\n <\/jats:sec>\n \n Availability and Implementation<\/jats:title>\n A C-program is available for download on http:\/\/www.math.nus.edu.sg\/\u223cmatzlx\/tcp_package.<\/jats:p>\n <\/jats:sec>\n \n Contact<\/jats:title>\n matzlx@nus.edu.sg<\/jats:p>\n <\/jats:sec>\n \n Supplementary information<\/jats:title>\n Supplementary data are available at Bioinformatics online.<\/jats:p>\n <\/jats:sec>","DOI":"10.1093\/bioinformatics\/btw467","type":"journal-article","created":{"date-parts":[[2016,9,1]],"date-time":"2016-09-01T07:53:39Z","timestamp":1472716419000},"page":"i503-i510","source":"Crossref","is-referenced-by-count":12,"title":["A program for verification of phylogenetic network models"],"prefix":"10.1093","volume":"32","author":[{"given":"Andreas DM","family":"Gunawan","sequence":"first","affiliation":[{"name":"Department of Mathematics"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bingxin","family":"Lu","sequence":"additional","affiliation":[{"name":"Department of Computer Science, National University of Singapore, Singapore 117417, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Louxin","family":"Zhang","sequence":"additional","affiliation":[{"name":"Department of Mathematics"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2016,8,29]]},"reference":[{"key":"2023020113254933300_btw467-B1","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1016\/j.aam.2016.04.004","article-title":"Reticulation-visible networks","volume":"78","author":"Bordewich","year":"2015","journal-title":"Adv. Appl. Math"},{"key":"2023020113254933300_btw467-B2","doi-asserted-by":"crossref","first-page":"552","DOI":"10.1109\/TCBB.2007.70270","article-title":"Comparison of tree-child phylogenetic networks","volume":"6","author":"Cardona","year":"2009","journal-title":"IEEE-ACM Trans. Comput. Biol. Bioinform"},{"key":"2023020113254933300_btw467-B3","doi-asserted-by":"crossref","first-page":"18566","DOI":"10.1073\/pnas.1313480110","article-title":"Topology of viral evolution","volume":"110","author":"Chan","year":"2013","journal-title":"Proc. Natl. Acad. Sci. U.S.A"},{"key":"2023020113254933300_btw467-B4","doi-asserted-by":"crossref","first-page":"555","DOI":"10.3852\/07-108R","article-title":"Phylogenetic relatedness of the M2 double-stranded RNA in Rhizoctonia fungi","volume":"100","author":"Charlton","year":"2008","journal-title":"Mycologia"},{"key":"2023020113254933300_btw467-B5","doi-asserted-by":"crossref","first-page":"2124","DOI":"10.1126\/science.284.5423.2124","article-title":"Phylogenetic classification and the universal tree","volume":"248","author":"Doolittle","year":"1999","journal-title":"Science"},{"key":"2023020113254933300_btw467-B6","author":"Gambette","year":"2015"},{"key":"2023020113254933300_btw467-B7","volume-title":"Concrete Mathematics","author":"Graham","year":"2002"},{"key":"2023020113254933300_btw467-B8","author":"Gunawan","year":"2016"},{"key":"2023020113254933300_btw467-B9","doi-asserted-by":"crossref","DOI":"10.7551\/mitpress\/9432.001.0001","volume-title":"ReCombinatorics: The Algorithmics of Ancestral Recombination Graphs and Explicit Phylogenetic Networks","author":"Gusfield","year":"2014"},{"key":"2023020113254933300_btw467-B10","doi-asserted-by":"crossref","first-page":"102","DOI":"10.1093\/sysbio\/syu076","article-title":"How much information is needed to infer reticulate evolutionary histories?","volume":"64","author":"Huber","year":"2015","journal-title":"Syst. Biol"},{"key":"2023020113254933300_btw467-B11","doi-asserted-by":"crossref","first-page":"460","DOI":"10.1186\/1471-2105-8-460","article-title":"Dendroscope: an interactive viewer for large phylogenetic trees","volume":"22","author":"Huson","year":"2007","journal-title":"BMC Bioinformatics"},{"key":"2023020113254933300_btw467-B12","volume-title":"Phylogenetic Networks: Concepts, Algorithms and Applications","author":"Huson","year":"2011"},{"key":"2023020113254933300_btw467-B13","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1016\/j.tcs.2008.04.019","article-title":"Seeing the trees and their branches in the network is hard","volume":"401","author":"Kanj","year":"2008","journal-title":"Theor. Comput. Sci"},{"key":"2023020113254933300_btw467-B14","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1186\/1471-2148-7-7","article-title":"Reticulate phylogeny of gastropod-shell-breeding cichlids from Lake Tanganyika: the result of repeated introgressive hybridization","volume":"7","author":"Koblm\u00fcller","year":"2007","journal-title":"BMC Evol. Biol"},{"key":"2023020113254933300_btw467-B15","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1109\/TCBB.2004.10","article-title":"Phylogenetic networks: modeling, reconstructibility, and accuracy","volume":"1","author":"Moret","year":"2004","journal-title":"IEEE-ACM Trans. Comput. Biol. Bioinform"},{"key":"2023020113254933300_btw467-B16","doi-asserted-by":"crossref","first-page":"719","DOI":"10.1016\/j.tree.2013.09.004","article-title":"Computational approaches to species phylogeny inference and gene tree reconciliation","volume":"28","author":"Nakhleh","year":"2013","journal-title":"Trends Ecol. Evol"},{"key":"2023020113254933300_btw467-B17","doi-asserted-by":"crossref","first-page":"1345","DOI":"10.1089\/cmb.2009.0243","article-title":"Ancestral recombinations graph: a reconstructability perspective using random-graphs framework","volume":"17","author":"Parida","year":"2010","journal-title":"J. Comput. Biol"},{"key":"2023020113254933300_btw467-B18","doi-asserted-by":"crossref","first-page":"i413","DOI":"10.1093\/bioinformatics\/bti1033","article-title":"Efficient computation of close lower and upper bounds on the minimum number of recombinations in biological sequence evolution","volume":"21","author":"Song","year":"2005","journal-title":"Bioinformatics"},{"key":"2023020113254933300_btw467-B19","doi-asserted-by":"crossref","first-page":"e1001284.","DOI":"10.1371\/journal.pgen.1001284","article-title":"Horizontal transfer, not duplication, drives the expansion of protein families in prokaryotes","volume":"7","author":"Treangen","year":"2011","journal-title":"PLoS Genet"},{"key":"2023020113254933300_btw467-B20","doi-asserted-by":"crossref","first-page":"1037","DOI":"10.1016\/j.ipl.2010.07.027","article-title":"Locating a tree in a phylogenetic network","volume":"110","author":"van Iersel","year":"2010","journal-title":"Inform. Process. Lett"},{"key":"2023020113254933300_btw467-B21","doi-asserted-by":"crossref","first-page":"i124","DOI":"10.1093\/bioinformatics\/btq202","article-title":"Phylogenetic networks do not need to be complex: using fewer reticulations to represent conflicting clusters","volume":"24","author":"van Iersel","year":"2010","journal-title":"Bioinformatics"},{"key":"2023020113254933300_btw467-B22","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1089\/106652701300099119","article-title":"Perfect phylogenetic networks with recombination","volume":"8","author":"Wang","year":"2001","journal-title":"J. Comp. Biol"},{"key":"2023020113254933300_btw467-B23","doi-asserted-by":"crossref","first-page":"16448","DOI":"10.1073\/pnas.1407950111","article-title":"Maximum likelihood inference of reticulate evolutionary histories","volume":"111","author":"Yu","year":"2014","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"2023020113254933300_btw467-B24","doi-asserted-by":"crossref","first-page":"553","DOI":"10.1089\/cmb.2015.0228","article-title":"On tree-based phylogenetic networks","volume":"23","author":"Zhang","year":"2016","journal-title":"J. Comput. Biol"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/32\/17\/i503\/49022850\/bioinformatics_32_17_i503.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/32\/17\/i503\/49022850\/bioinformatics_32_17_i503.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,1]],"date-time":"2023-02-01T23:29:23Z","timestamp":1675294163000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/32\/17\/i503\/2450798"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,8,29]]},"references-count":24,"journal-issue":{"issue":"17","published-print":{"date-parts":[[2016,9,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btw467","relation":{},"ISSN":["1367-4803","1367-4811"],"issn-type":[{"value":"1367-4803","type":"print"},{"value":"1367-4811","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2016,9,1]]},"published":{"date-parts":[[2016,8,29]]}}}