{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,12]],"date-time":"2026-03-12T00:29:10Z","timestamp":1773275350847,"version":"3.50.1"},"reference-count":15,"publisher":"World Scientific Pub Co Pte Lt","issue":"05","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. Bioinform. Comput. Biol."],"published-print":{"date-parts":[[2012,10]]},"abstract":"<jats:p> For a given set [Formula: see text] of species and a set [Formula: see text] of triplets on [Formula: see text], we seek to construct a phylogenetic network which is consistent with [Formula: see text] i.e. which represents all triplets of [Formula: see text]. The level of a network is defined as the maximum number of hybrid vertices in its biconnected components. When [Formula: see text] is dense, there exist polynomial time algorithms to construct level-0,1 and 2 networks (Aho et al., 1981; Jansson, Nguyen and Sung, 2006; Jansson and Sung, 2006; Iersel et al., 2009). For higher levels, partial answers were obtained in the paper by Iersel and Kelk (2008), with a polynomial time algorithm for simple networks. In this paper, we detail the first complete answer for the general case, solving a problem proposed in Jansson and Sung (2006) and Iersel et al. (2009). For any k fixed, it is possible to construct a level-k network having the minimum number of hybrid vertices and consistent with [Formula: see text], if there is any, in time [Formula: see text]. <\/jats:p>","DOI":"10.1142\/s0219720012500138","type":"journal-article","created":{"date-parts":[[2012,6,4]],"date-time":"2012-06-04T15:54:34Z","timestamp":1338825274000},"page":"1250013","source":"Crossref","is-referenced-by-count":13,"title":["CONSTRUCTING A MINIMUM PHYLOGENETIC NETWORK FROM A DENSE TRIPLET SET"],"prefix":"10.1142","volume":"10","author":[{"given":"MICHEL","family":"HABIB","sequence":"first","affiliation":[{"name":"Universit\u00e9 Paris Diderot \u2014 Paris 7, LIAFA, Case 7014, 75205 Paris Cedex 13, France"}]},{"given":"THU-HIEN","family":"TO","sequence":"additional","affiliation":[{"name":"LIRMM \u2014 CNRS, France"}]}],"member":"219","published-online":{"date-parts":[[2012,8]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.1093\/molbev\/msn219"},{"key":"rf2","volume-title":"Reconstructing Evolution: New Mathematical and Computational Advances","author":"Semple Charles","year":"2006"},{"key":"rf3","first-page":"806","volume":"155","author":"Gusfield D.","journal-title":"DAM"},{"key":"rf4","volume-title":"Problem Solving Handbook in Computational Biology and Bioinformatics","author":"Nakhleh L.","year":"2009"},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.12.012"},{"key":"rf7","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704446529"},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1109\/TCBB.2009.22"},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1142\/S0219720009004308"},{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2006.06.022"},{"key":"rf12","doi-asserted-by":"publisher","DOI":"10.1137\/0210030"},{"key":"rf14","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009268"},{"key":"rf15","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2009.01.004"},{"key":"rf17","doi-asserted-by":"publisher","DOI":"10.1016\/j.jtbi.2010.10.032"},{"key":"rf19","volume-title":"Combinatorial Optimization - Polyhedra and Efficiency","author":"Schrijver A.","year":"2003"},{"key":"rf20","volume-title":"Parametrized Complexity Theory","author":"Flum J.","year":"2006"}],"container-title":["Journal of Bioinformatics and Computational Biology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0219720012500138","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T21:16:39Z","timestamp":1565126199000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0219720012500138"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,8]]},"references-count":15,"journal-issue":{"issue":"05","published-online":{"date-parts":[[2012,8]]},"published-print":{"date-parts":[[2012,10]]}},"alternative-id":["10.1142\/S0219720012500138"],"URL":"https:\/\/doi.org\/10.1142\/s0219720012500138","relation":{},"ISSN":["0219-7200","1757-6334"],"issn-type":[{"value":"0219-7200","type":"print"},{"value":"1757-6334","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,8]]}}}