{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,14]],"date-time":"2026-09-14T13:14:02Z","timestamp":1789391642809,"version":"build-2803163510"},"reference-count":21,"publisher":"World Scientific Pub Co Pte Lt","issue":"04","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. Bioinform. Comput. Biol."],"published-print":{"date-parts":[[2009,8]]},"abstract":"<jats:p> Phylogenetic networks provide a way to describe and visualize evolutionary histories that have undergone so-called reticulate evolutionary events such as recombination, hybridization or horizontal gene transfer. The level k of a network determines how non-treelike the evolution can be, with level-0 networks being trees. We study the problem of constructing level-k phylogenetic networks from triplets, i.e. phylogenetic trees for three leaves (taxa). We give, for each k, a level-k network that is uniquely defined by its triplets. We demonstrate the applicability of this result by using it to prove that (1) for all k \u2265 1 it is NP-hard to construct a level-k network consistent with all input triplets, and (2) for all k \u2265 0 it is NP-hard to construct a level-k network consistent with a maximum number of input triplets, even when the input is dense. As a response to this intractability, we give an exact algorithm for constructing level-1 networks consistent with a maximum number of input triplets. <\/jats:p>","DOI":"10.1142\/s0219720009004308","type":"journal-article","created":{"date-parts":[[2009,7,23]],"date-time":"2009-07-23T11:31:54Z","timestamp":1248348714000},"page":"597-623","source":"Crossref","is-referenced-by-count":29,"title":["UNIQUENESS, INTRACTABILITY AND EXACT ALGORITHMS: REFLECTIONS ON LEVEL-K PHYLOGENETIC NETWORKS"],"prefix":"10.1142","volume":"07","author":[{"given":"LEO","family":"VAN IERSEL","sequence":"first","affiliation":[{"name":"Department of Mathematics and Computer Science, Technische Universiteit Eindhoven, P. O. Box 513, 5600 MB Eindhoven, The Netherlands"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"STEVEN","family":"KELK","sequence":"additional","affiliation":[{"name":"Centrum voor Wiskunde en Informatica (CWI), P. O. Box 94079, 1090 GB Amsterdam, The Netherlands"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"MATTHIAS","family":"MNICH","sequence":"additional","affiliation":[{"name":"Department of Mathematics and Computer Science, Technische Universiteit Eindhoven, P. O. Box 513, 5600 MB Eindhoven, The Netherlands"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"219","published-online":{"date-parts":[[2011,11,21]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.1093\/molbev\/msj030"},{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1142\/S0219720004000521"},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1089\/cmb.2005.12.796"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704446529"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.12.012"},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1038\/nrg1044"},{"key":"rf7","doi-asserted-by":"publisher","DOI":"10.1016\/S0196-6774(03)00049-X"},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1089\/cmb.2007.0103"},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1137\/0210030"},{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.1007\/BF02618470"},{"key":"rf15","doi-asserted-by":"publisher","DOI":"10.1023\/B:JOCO.0000021936.04215.68"},{"key":"rf16","doi-asserted-by":"publisher","DOI":"10.1023\/A:1009833626004"},{"key":"rf18","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(00)00202-X"},{"key":"rf20","doi-asserted-by":"publisher","DOI":"10.1109\/TCBB.2006.58"},{"key":"rf21","first-page":"3","volume":"4","author":"Baum B. R.","journal-title":"Taxon"},{"key":"rf22","doi-asserted-by":"publisher","DOI":"10.1016\/0303-2647(92)90007-L"},{"key":"rf23","doi-asserted-by":"publisher","DOI":"10.1016\/S0169-5347(97)01242-1"},{"key":"rf25","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2006.06.022"},{"key":"rf26","volume-title":"Computers and Intractability","author":"Garey M. R.","year":"1979"},{"key":"rf27","doi-asserted-by":"publisher","DOI":"10.1137\/050623905"},{"key":"rf28","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548306007887"}],"container-title":["Journal of Bioinformatics and Computational Biology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0219720009004308","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T17:00:41Z","timestamp":1565197241000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0219720009004308"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,8]]},"references-count":21,"journal-issue":{"issue":"04","published-online":{"date-parts":[[2011,11,21]]},"published-print":{"date-parts":[[2009,8]]}},"alternative-id":["10.1142\/S0219720009004308"],"URL":"https:\/\/doi.org\/10.1142\/s0219720009004308","relation":{},"ISSN":["0219-7200","1757-6334"],"issn-type":[{"value":"0219-7200","type":"print"},{"value":"1757-6334","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,8]]}}}