{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,8]],"date-time":"2026-07-08T04:05:29Z","timestamp":1783483529840,"version":"3.55.0"},"reference-count":15,"publisher":"World Scientific Pub Co Pte Lt","issue":"01","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. Bioinform. Comput. Biol."],"published-print":{"date-parts":[[2004,3]]},"abstract":"<jats:p>A phylogenetic network is a generalization of a phylogenetic tree, allowing structural properties that are not tree-like. In a seminal paper, Wang et al.<jats:sup>1<\/jats:sup>studied the problem of constructing a phylogenetic network, allowing recombination between sequences, with the constraint that the resulting cycles must be disjoint. We call such a phylogenetic network a \"galled-tree\". They gave a polynomial-time algorithm that was intended to determine whether or not a set of sequences could be generated on galled-tree. Unfortunately, the algorithm by Wang et al.<jats:sup>1<\/jats:sup>is incomplete and does not constitute a necessary test for the existence of a galled-tree for the data. In this paper, we completely solve the problem. Moreover, we prove that if there is a galled-tree, then the one produced by our algorithm minimizes the number of recombinations over all phylogenetic networks for the data, even allowing multiple-crossover recombinations. We also prove that when there is a galled-tree for the data, the galled-tree minimizing the number of recombinations is \"essentially unique\". We also note two additional results: first, any set of sequences that can be derived on a galled tree can be derived on a true tree (without recombination cycles), where at most one back mutation per site is allowed; second, the site compatibility problem (which is NP-hard in general) can be solved in polynomial time for any set of sequences that can be derived on a galled tree.<\/jats:p><jats:p>Perhaps more important than the specific results about galled-trees, we introduce an approach that can be used to study recombination in general phylogenetic networks.<\/jats:p><jats:p>This paper greatly extends the conference version that appears in an earlier work.<jats:sup>8<\/jats:sup>PowerPoint slides of the conference talk can be found at our website.<jats:sup>7<\/jats:sup><\/jats:p>","DOI":"10.1142\/s0219720004000521","type":"journal-article","created":{"date-parts":[[2004,5,26]],"date-time":"2004-05-26T11:22:29Z","timestamp":1085570549000},"page":"173-213","source":"Crossref","is-referenced-by-count":139,"title":["OPTIMAL, EFFICIENT RECONSTRUCTION OF PHYLOGENETIC NETWORKS WITH CONSTRAINED RECOMBINATION"],"prefix":"10.1142","volume":"02","author":[{"given":"DAN","family":"GUSFIELD","sequence":"first","affiliation":[{"name":"Computer Science, University of California, Davis, Kemper Hall, Davis, California, 95616, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"SATISH","family":"EDDHU","sequence":"additional","affiliation":[{"name":"Computer Science, University of California, Davis, Kemper Hall, Davis, California, 95616, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"CHARLES","family":"LANGLEY","sequence":"additional","affiliation":[{"name":"Division of Evolution and Ecology, University of California, Davis, Storer Hall, Davis, California, 95616, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"219","published-online":{"date-parts":[[2011,11,21]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.1089\/106652701300099119"},{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.2307\/2413432"},{"key":"rf3","first-page":"427","author":"Dragan F.","journal-title":"Discrete Applied Math."},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230210104"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511574931"},{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.1016\/0025-5564(90)90123-G"},{"key":"rf11","first-page":"396","volume":"36","author":"Hein J.","journal-title":"J. Mol. Evol."},{"key":"rf12","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1093\/genetics\/111.1.147","volume":"111","author":"Hudson R.","journal-title":"Genetics"},{"key":"rf13","first-page":"239","author":"Kececioglu J. D.","journal-title":"Discrete Applied Math."},{"key":"rf14","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.98.2.531"},{"key":"rf15","doi-asserted-by":"crossref","first-page":"375","DOI":"10.1093\/genetics\/163.1.375","volume":"163","author":"Myers S. R.","journal-title":"Genetics"},{"key":"rf17","doi-asserted-by":"publisher","DOI":"10.1016\/S0168-9525(02)02557-X"},{"key":"rf18","doi-asserted-by":"publisher","DOI":"10.1016\/S0169-5347(00)02026-7"},{"key":"rf19","doi-asserted-by":"crossref","first-page":"879","DOI":"10.1093\/genetics\/156.2.879","volume":"156","author":"Schierup M. H.","journal-title":"Genetics"},{"key":"rf20","author":"Song Y.","journal-title":"J. Math. Bio."}],"container-title":["Journal of Bioinformatics and Computational Biology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0219720004000521","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,6,17]],"date-time":"2021-06-17T23:54:43Z","timestamp":1623974083000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0219720004000521"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,3]]},"references-count":15,"journal-issue":{"issue":"01","published-online":{"date-parts":[[2011,11,21]]},"published-print":{"date-parts":[[2004,3]]}},"alternative-id":["10.1142\/S0219720004000521"],"URL":"https:\/\/doi.org\/10.1142\/s0219720004000521","relation":{},"ISSN":["0219-7200","1757-6334"],"issn-type":[{"value":"0219-7200","type":"print"},{"value":"1757-6334","type":"electronic"}],"subject":[],"published":{"date-parts":[[2004,3]]}}}