{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,12]],"date-time":"2026-03-12T01:06:51Z","timestamp":1773277611978,"version":"3.50.1"},"reference-count":25,"publisher":"Oxford University Press (OUP)","issue":"17","license":[{"start":{"date-parts":[[2018,9,1]],"date-time":"2018-09-01T00:00:00Z","timestamp":1535760000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/about_us\/legal\/notices"}],"funder":[{"name":"Singapore Ministry of Education Academic Research Fund Tier-1","award":["R-146-000-238-114"],"award-info":[{"award-number":["R-146-000-238-114"]}]},{"DOI":"10.13039\/501100001866","name":"National Research Fund","doi-asserted-by":"publisher","award":["NRF2016NRF-NSFC001-026"],"award-info":[{"award-number":["NRF2016NRF-NSFC001-026"]}],"id":[{"id":"10.13039\/501100001866","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018,9,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:sec>\n                  <jats:title>Motivation<\/jats:title>\n                  <jats:p>Comparative genomic studies indicate that extant genomes are more properly considered to be a fusion product of random mutations over generations (vertical evolution) and genomic material transfers between individuals of different lineages (reticulate transfer). This has motivated biologists to use phylogenetic networks and other general models to study genome evolution. Two fundamental algorithmic problems arising from verification of phylogenetic networks and from computing Robinson-Foulds distance in the space of phylogenetic networks are the tree and cluster containment problems. The former asks how to decide whether or not a phylogenetic tree is displayed in a phylogenetic network. The latter is to decide whether a subset of taxa appears as a cluster in some tree displayed in a phylogenetic network. The cluster containment problem (CCP) is also closely related to testing the infinite site model on a recombination network. Both the tree containment and CCP are NP-complete. Although the CCP was introduced a decade ago, there has been little progress in developing fast algorithms for it on arbitrary phylogenetic networks.<\/jats:p>\n               <\/jats:sec>\n               <jats:sec>\n                  <jats:title>Results<\/jats:title>\n                  <jats:p>In this work, we present a fast computer program for the CCP. This program is developed on the basis of a linear-time transformation from the small version of the CCP to the SAT problem.<\/jats:p>\n               <\/jats:sec>\n               <jats:sec>\n                  <jats:title>Availability and implementation<\/jats:title>\n                  <jats:p>The program package is available for download on http:\/\/www.math.nus.edu.sg\/\u223cmatzlx\/ccp.<\/jats:p>\n               <\/jats:sec>","DOI":"10.1093\/bioinformatics\/bty594","type":"journal-article","created":{"date-parts":[[2018,7,6]],"date-time":"2018-07-06T01:20:56Z","timestamp":1530840056000},"page":"i680-i686","source":"Crossref","is-referenced-by-count":7,"title":["S-Cluster++: a fast program for solving the cluster containment problem for phylogenetic networks"],"prefix":"10.1093","volume":"34","author":[{"given":"Hongwei","family":"Yan","sequence":"first","affiliation":[{"name":"Department of Mathematics, National University of Singapore, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andreas D M","family":"Gunawan","sequence":"additional","affiliation":[{"name":"Department of Mathematics, National University of Singapore, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Louxin","family":"Zhang","sequence":"additional","affiliation":[{"name":"Department of Mathematics, National University of Singapore, Singapore"},{"name":"Computational Biology Program, National University of Singapore, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2018,9,8]]},"reference":[{"key":"2023061313505230400_bty594-B1","doi-asserted-by":"crossref","first-page":"46","DOI":"10.1109\/TCBB.2008.70","article-title":"Metrics for phylogenetic networks I: generalizations of the Robinson-Foulds metric","volume":"6","author":"Cardona","year":"2009","journal-title":"IEEE-ACM Trans. Comput. Biol. Bioinform."},{"key":"2023061313505230400_bty594-B2","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. USA"},{"key":"2023061313505230400_bty594-B3","doi-asserted-by":"crossref","first-page":"2043","DOI":"10.1073\/pnas.0610699104","article-title":"Pattern pluralism and the Tree of Life hypothesis","volume":"104","author":"Doolittle","year":"2007","journal-title":"Proc. Natl. Acad. Sci. USA."},{"key":"2023061313505230400_bty594-B4","doi-asserted-by":"crossref","first-page":"1773","DOI":"10.1007\/s11538-016-0199-4","article-title":"Do branch lengths help to locate a tree in a phylogenetic network? Bull","volume":"78","author":"Gambette","year":"2016","journal-title":"Math. Biol."},{"key":"2023061313505230400_bty594-B5","first-page":"62","author":"Gambette","year":"2017"},{"key":"2023061313505230400_bty594-B6","author":"Gunawan","year":"2016"},{"key":"2023061313505230400_bty594-B7","author":"Gunawan","year":"2017"},{"key":"2023061313505230400_bty594-B8","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":"2023061313505230400_bty594-B9","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":"2023061313505230400_bty594-B10","volume-title":"Phylogenetic Networks: Concepts, Algorithms and Applications","author":"Huson","year":"2011"},{"key":"2023061313505230400_bty594-B11","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":"2023061313505230400_bty594-B12","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1186\/s12864-017-3500-5","article-title":"A program to compute the soft Robinson\u2013Foulds distance between phylogenetic networks","volume":"18","author":"Lu","year":"2017","journal-title":"BMC Genomics"},{"key":"2023061313505230400_bty594-B14","doi-asserted-by":"crossref","first-page":"1250092","DOI":"10.1126\/science.1250092","article-title":"Ancient hybridizations among the ancestral genomes of bread wheat","volume":"345","author":"Marcussen","year":"2014","journal-title":"Science"},{"key":"2023061313505230400_bty594-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":"2023061313505230400_bty594-B16","first-page":"245","article-title":"A full derandomization of Sch\u00f6ning\u2019s k-SAT algorithm","volume-title":"Proceedings of the 43rd Annual ACM Symposium on Theory of Computing","author":"Moser","year":"2011"},{"key":"2023061313505230400_bty594-B17","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":"2023061313505230400_bty594-B19","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":"2023061313505230400_bty594-B21","doi-asserted-by":"crossref","first-page":"104","DOI":"10.1038\/nature14895","article-title":"Genetic evidence for two founding populations of the Americas","volume":"525","author":"Skoglund","year":"2015","journal-title":"Nature"},{"key":"2023061313505230400_bty594-B22","first-page":"1","article-title":"Minisat v1. 13-a sat solver with conflict-clause minimization","volume-title":"Proceedings of the 8th International Conference on Theory and Applications of Satisfiability Testing","author":"S\u00f6rensson","year":"2005"},{"key":"2023061313505230400_bty594-B23","doi-asserted-by":"crossref","DOI":"10.1137\/1.9781611974485","volume-title":"Phylogeny: Discrete and Random Processes in Evolution","author":"Steel","year":"2016"},{"key":"2023061313505230400_bty594-B24","doi-asserted-by":"crossref","first-page":"20140335","DOI":"10.1098\/rstb.2014.0335","article-title":"Genome-scale phylogenetic analysis finds extensive gene transfer among fungi","volume":"370","author":"Sz\u00f6ll\u0151si","year":"2015","journal-title":"Philos. T. R. Soc. B"},{"key":"2023061313505230400_bty594-B25","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":"2023061313505230400_bty594-B26","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":"2023061313505230400_bty594-B27","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. Comput. Biol."},{"key":"2023061313505230400_bty594-B28","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"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/34\/17\/i680\/50582484\/bioinformatics_34_17_i680.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/34\/17\/i680\/50582484\/bioinformatics_34_17_i680.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,13]],"date-time":"2023-06-13T13:52:54Z","timestamp":1686664374000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/34\/17\/i680\/5093208"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,9,1]]},"references-count":25,"journal-issue":{"issue":"17","published-print":{"date-parts":[[2018,9,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/bty594","relation":{},"ISSN":["1367-4803","1367-4811"],"issn-type":[{"value":"1367-4803","type":"print"},{"value":"1367-4811","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2018,9,1]]},"published":{"date-parts":[[2018,9,1]]}}}