{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,12]],"date-time":"2026-03-12T01:06:08Z","timestamp":1773277568610,"version":"3.50.1"},"reference-count":24,"publisher":"Oxford University Press (OUP)","issue":"12","license":[{"start":{"date-parts":[[2016,10,2]],"date-time":"2016-10-02T00:00:00Z","timestamp":1475366400000},"content-version":"vor","delay-in-days":2315,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc\/2.0\/uk\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010,6,15]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Motivation: Reticulate network is a model for displaying and quantifying the effects of complex reticulate processes on the evolutionary history of species undergoing reticulate evolution. A central computational problem on reticulate networks is: given a set of phylogenetic trees (each for some region of the genomes), reconstruct the most parsimonious reticulate network (called the minimum reticulate network) that combines the topological information contained in the given trees. This problem is well-known to be NP-hard. Thus, existing approaches for this problem either work with only two input trees or make simplifying topological assumptions.<\/jats:p><jats:p>Results: We present novel results on the minimum reticulate network problem. Unlike existing approaches, we address the fully general problem: there is no restriction on the number of trees that are input, and there is no restriction on the form of the allowed reticulate network. We present lower and upper bounds on the minimum number of reticulation events in the minimum reticulate network (and infer an approximately parsimonious reticulate network). A program called PIRN implements these methods, which also outputs a graphical representation of the inferred network. Empirical results on simulated and biological data show that our methods are practical for a wide range of data. More importantly, the lower and upper bounds match for many datasets (especially when the number of trees is small or reticulation level is low), and this allows us to solve the minimum reticulate network problem exactly for these datasets.<\/jats:p><jats:p>Availability: A software tool, PIRN, is available for download from the web page: http:\/\/www.engr.uconn.edu\/~ywu.<\/jats:p><jats:p>Contact: \u00a0ywu@engr.uconn.edu<\/jats:p><jats:p>Supplementary information: \u00a0Supplementary data is available at Bioinformatics online.<\/jats:p>","DOI":"10.1093\/bioinformatics\/btq198","type":"journal-article","created":{"date-parts":[[2010,6,7]],"date-time":"2010-06-07T07:28:13Z","timestamp":1275895693000},"page":"i140-i148","source":"Crossref","is-referenced-by-count":40,"title":["Close lower and upper bounds for the minimum reticulate network of multiple phylogenetic trees"],"prefix":"10.1093","volume":"26","author":[{"given":"Yufeng","family":"Wu","sequence":"first","affiliation":[{"name":"Department of Computer Science and Engineering, University of Connecticut, Storrs, CT 06269, USA"}]}],"member":"286","published-online":{"date-parts":[[2010,6,1]]},"reference":[{"key":"2023012508054605400_B1","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1007\/s00285-005-0315-9","article-title":"Bounding the number of hybridisation events for a consistent evolutionary history","volume":"51","author":"Baroni","year":"2005","journal-title":"J. Math. Biol."},{"key":"2023012508054605400_B2","doi-asserted-by":"crossref","first-page":"391","DOI":"10.1007\/s00026-004-0228-0","article-title":"A framework for representing reticulate evolution","volume":"8","author":"Baroni","year":"2004","journal-title":"Ann. Comb."},{"key":"2023012508054605400_B3","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1177\/117693430700300017","article-title":"A reduction algorithm for computing the hybridization number of two trees","volume":"3","author":"Bordewich","year":"2007","journal-title":"Evol. Bioinform."},{"key":"2023012508054605400_B4","doi-asserted-by":"crossref","first-page":"409","DOI":"10.1007\/s00026-004-0229-z","article-title":"On the computational complexity of the rooted subtree prune and regraft distance","volume":"8","author":"Bordewich","year":"2004","journal-title":"Ann. Comb."},{"key":"2023012508054605400_B5","doi-asserted-by":"crossref","first-page":"914","DOI":"10.1016\/j.dam.2006.08.008","article-title":"Computing the minimum number of hybridization events for a consistent evolutionary history","volume":"155","author":"Bordewich","year":"2007","journal-title":"Dis. Appl. Math."},{"key":"2023012508054605400_B6","doi-asserted-by":"crossref","first-page":"373","DOI":"10.2307\/3298585","article-title":"Phylogeny and subfamilial classification of the grasses (poaceae)","volume":"88","author":"Grass Phylogeny Working Group","year":"2001","journal-title":"Ann. Mo. Bot. Gard."},{"key":"2023012508054605400_B7","doi-asserted-by":"crossref","first-page":"381","DOI":"10.1016\/j.jcss.2004.12.009","article-title":"Optimal, efficient reconstruction of Root-Unknown phylogenetic networks with constrained and structured recombination","volume":"70","author":"Gusfield","year":"2005","journal-title":"J. Comput. Syst, Sci."},{"key":"2023012508054605400_B8","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1145\/369133.369188","article-title":"Efficient algorithms for lateral gene transfer problems","volume-title":"Proceedings of Fifth Annual Conference on Research in Computational Molecular Biology (RECOMB 2001)","author":"Hallett","year":"2001"},{"key":"2023012508054605400_B9","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1016\/S0166-218X(96)00062-5","article-title":"On the complexity of comparing evolutionary trees","volume":"71","author":"Hein","year":"1996","journal-title":"Dis. Appl. Math."},{"key":"2023012508054605400_B10","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1093\/bioinformatics\/18.2.337","article-title":"Generating samples under the Wright-Fisher neutral model of genetic variation","volume":"18","author":"Hudson","year":"2002","journal-title":"Bioinformatics"},{"key":"2023012508054605400_B11","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1093\/oso\/9780199208227.003.0009","article-title":"Split networks and reticulate networks","volume-title":"Reconstructing Evolution: New Mathematical and Computational Advances.","author":"Huson","year":"2007"},{"key":"2023012508054605400_B12","doi-asserted-by":"crossref","first-page":"254","DOI":"10.1093\/molbev\/msj030","article-title":"Application of phylogenetic networks in evolutionary studies","volume":"23","author":"Huson","year":"2006","journal-title":"Mol. Biol. Evol."},{"key":"2023012508054605400_B13","first-page":"211","article-title":"Beyond galled trees - decomposition and computation of galled networks","volume-title":"Proceeding of RECOMB 2007: The 11th Annual International Conference Research in Computational Molecular Biology","author":"Huson","year":"2007"},{"key":"2023012508054605400_B14","first-page":"233","article-title":"Reconstruction of reticulate networks from gene trees","volume-title":"Proceeding of RECOMB 2005: The 9th Annual International Conference Research in Computational Molecular Biology","author":"Huson","year":"2005"},{"key":"2023012508054605400_B15","doi-asserted-by":"crossref","first-page":"i85","DOI":"10.1093\/bioinformatics\/btp217","article-title":"Computing galled networks from real data","volume":"25","author":"Huson","year":"2009","journal-title":"Bioinformatics"},{"key":"2023012508054605400_B16","doi-asserted-by":"crossref","first-page":"30","DOI":"10.1109\/TCBB.2008.86","article-title":"Hybridization in nonbinary trees","volume":"6","author":"Linz","year":"2009","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform."},{"key":"2023012508054605400_B17","article-title":"Evolutionary phylogenetic networks: models and issues","volume-title":"The Problem Solving Handbook for Computational Biology and Bioinformatics.","author":"Nakhleh","year":"2009"},{"key":"2023012508054605400_B18","first-page":"337","article-title":"Reconstructing reticulate evolution in species - theory and practice","volume-title":"Proceeding of 8th Annual International Conference on Computational Molecular Biology","author":"Nakhleh","year":"2004"},{"key":"2023012508054605400_B19","doi-asserted-by":"crossref","first-page":"796","DOI":"10.1089\/cmb.2005.12.796","article-title":"Reconstructing reticulate evolution in species - theory and practice","volume":"12","author":"Nakhleh","year":"2005","journal-title":"J. Comp. Biol."},{"key":"2023012508054605400_B20","article-title":"Phylogenetic trees from large datasets","volume-title":"PhD Thesis","author":"Schmidt","year":"2003"},{"key":"2023012508054605400_B21","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1093\/oso\/9780199208227.003.0010","article-title":"Hybridization networks","volume-title":"Reconstructing Evolution: New Mathematical and Computational Advances.","author":"Semple","year":"2007"},{"key":"2023012508054605400_B22","first-page":"450","article-title":"Constructing level-2 phylogenetic networks from triplets","volume-title":"Proceeding of RECOMB 2008: The 12th Annual International Conference Research in Computational Molecular Biology","author":"van Iersel","year":"2008"},{"key":"2023012508054605400_B23","doi-asserted-by":"crossref","first-page":"190","DOI":"10.1093\/bioinformatics\/btn606","article-title":"A practical method for exact computation of subtree prune and regraft distance","volume":"25","author":"Wu","year":"2009","journal-title":"Bioinformatics"},{"key":"2023012508054605400_B24","first-page":"203","article-title":"Fast Computation of the exact hybridization number of two phylogenetic trees","volume-title":"Proceeding of ISBRA 2010: The 6th International Symposium on Bioinformatics Research and Applications","author":"Wu","year":"2010"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/26\/12\/i140\/48858503\/bioinformatics_26_12_i140.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/26\/12\/i140\/48858503\/bioinformatics_26_12_i140.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,27]],"date-time":"2024-03-27T10:23:28Z","timestamp":1711535008000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/26\/12\/i140\/284107"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,6,1]]},"references-count":24,"journal-issue":{"issue":"12","published-print":{"date-parts":[[2010,6,15]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btq198","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2010,6,15]]},"published":{"date-parts":[[2010,6,1]]}}}