{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,12]],"date-time":"2026-03-12T00:15:12Z","timestamp":1773274512506,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642047435","type":"print"},{"value":"9783642047442","type":"electronic"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-04744-2_5","type":"book-chapter","created":{"date-parts":[[2009,9,23]],"date-time":"2009-09-23T09:16:13Z","timestamp":1253697373000},"page":"48-58","source":"Crossref","is-referenced-by-count":8,"title":["Minimal Conflicting Sets for the Consecutive Ones Property in Ancestral Genome Reconstruction"],"prefix":"10.1007","author":[{"given":"Cedric","family":"Chauve","sequence":"first","affiliation":[]},{"given":"Utz-Uwe","family":"Haus","sequence":"additional","affiliation":[]},{"given":"Tamon","family":"Stephen","sequence":"additional","affiliation":[]},{"given":"Vivija P.","family":"You","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"5_CR1","doi-asserted-by":"publisher","first-page":"436","DOI":"10.1089\/cmb.2007.A005","volume":"14","author":"Z. Adam","year":"2007","unstructured":"Adam, Z., Turmel, M., Lemieux, C., Sankoff, D.: Common intervals and symmetric difference in a model-free phylogenomics, with an application to streptophyte evolution. J. Comput. Biol.\u00a014, 436\u2013445 (2007)","journal-title":"J. Comput. Biol."},{"key":"5_CR2","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1089\/cmb.1995.2.159","volume":"2","author":"F. Alizadeh","year":"1995","unstructured":"Alizadeh, F., Karp, R., Weisser, D., Zweig, G.: Physical mapping of chromosomes using unique probes. J. Comput. Biol.\u00a02, 159\u2013184 (1995)","journal-title":"J. Comput. Biol."},{"key":"5_CR3","series-title":"Lecture Notes in Bioinformatics","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1007\/978-3-540-30219-3_2","volume-title":"Algorithms in Bioinformatics","author":"A. Bergeron","year":"2004","unstructured":"Bergeron, A., Blanchette, M., Chateau, A., Chauve, C.: Reconstructing ancestral gene orders using conserved intervals. In: Jonassen, I., Kim, J. (eds.) WABI 2004. LNCS (LNBI), vol.\u00a03240, pp. 14\u201325. Springer, Heidelberg (2004)"},{"key":"5_CR4","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1016\/S0022-0000(76)80045-1","volume":"13","author":"K.S. Booth","year":"1976","unstructured":"Booth, K.S., Lueker, G.S.: Testing for the consecutive ones property, interval graphs, and graph planarity. J. Comput. Syst. Sci.\u00a013, 335\u2013379 (1976)","journal-title":"J. Comput. Syst. Sci."},{"key":"5_CR5","doi-asserted-by":"publisher","first-page":"1000234","DOI":"10.1371\/journal.pcbi.1000234","volume":"4","author":"C. Chauve","year":"2008","unstructured":"Chauve, C., Tannier, E.: A methodological framework for the reconstruction of contiguous regions of ancestral genomes and its application to mammalian genome. PLoS Comput. Biol.\u00a04, e1000234 (2008)","journal-title":"PLoS Comput. Biol."},{"key":"5_CR6","doi-asserted-by":"publisher","first-page":"433","DOI":"10.1089\/cmb.1997.4.433","volume":"4","author":"T. Christof","year":"1997","unstructured":"Christof, T., J\u00fcnger, M., Kececioglu, J., Mutzel, P., Reinelt, G.: A branch-and-cut approach to physical mapping of chromosome by unique end-probes. J. Comput. Biol.\u00a04, 433\u2013447 (1997)","journal-title":"J. Comput. Biol."},{"key":"5_CR7","unstructured":"Dom, M.: Recognition, Generation, and Application of Binary Matrices with the Consecutive-Ones Property. Dissertation, Institut f\u00fcr Informatik, Friedrich-Schiller-Universit\u00e4t, Jena (2008)"},{"key":"5_CR8","doi-asserted-by":"publisher","first-page":"2035","DOI":"10.1016\/j.dam.2007.04.017","volume":"156","author":"T. Eiter","year":"2008","unstructured":"Eiter, T., Makino, K., Gottlob, G.: Computational aspects of monotone dualization: A brief survey. Disc. Appl. Math.\u00a0156, 2035\u20132049 (2008)","journal-title":"Disc. Appl. Math."},{"key":"5_CR9","doi-asserted-by":"publisher","first-page":"618","DOI":"10.1006\/jagm.1996.0062","volume":"21","author":"M.L. Fredman","year":"1996","unstructured":"Fredman, M.L., Khachiyan, L.: On the complexity of dualization of monotone disjunctive normal forms. J. Algorithms\u00a021, 618\u2013628 (1996)","journal-title":"J. Algorithms"},{"key":"5_CR10","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1089\/cmb.1995.2.139","volume":"2","author":"P.W. Goldberg","year":"1995","unstructured":"Goldberg, P.W., Golumbic, M.C., Kaplan, H., Shamir, R.: Four strikes againts physical mapping of DNA. J. Comput. Biol.\u00a02, 139\u2013152 (1995)","journal-title":"J. Comput. Biol."},{"key":"5_CR11","first-page":"209","volume-title":"PODS 1997","author":"D. Gunopulos","year":"1997","unstructured":"Gunopulos, D., Khardon, R., Mannila, H., Toivonen, H.: Data mining, hypergraph transversals and machine learning. In: PODS 1997, pp. 209\u2013216. ACM, New York (1997)"},{"key":"5_CR12","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1016\/S0166-218X(99)00099-2","volume":"96-97","author":"V. Gurvich","year":"1999","unstructured":"Gurvich, V., Khachiyan, L.: On generating the ireedundant conjunctive and disjunctive normal forms of monotone Boolean functions. Disc. Appl. Math.\u00a096-97, 363\u2013373 (1999)","journal-title":"Disc. Appl. Math."},{"key":"5_CR13","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1016\/S0304-3975(97)00241-7","volume":"234","author":"M. Habib","year":"2000","unstructured":"Habib, M., McConnell, R.M., Paul, C., Viennot, L.: Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing. Theoret. Comput. Sci.\u00a0234, 59\u201384 (2000)","journal-title":"Theoret. Comput. Sci."},{"key":"5_CR14","unstructured":"Haus, U.-U., Stephen, T.: CL-JOINTGEN: A Common Lisp Implementation of the Joint Generation Method (2008), http:\/\/primaldual.de\/cl-jointgen\/"},{"key":"5_CR15","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1006\/jagm.2001.1205","volume":"43","author":"W.-L. Hsu","year":"2002","unstructured":"Hsu, W.-L.: A simple test for the Consecutive Ones Porperty. J. Algorithms\u00a043, 1\u201316 (2002)","journal-title":"J. Algorithms"},{"key":"5_CR16","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1016\/0304-3975(86)90174-X","volume":"43","author":"M.R. Jerrum","year":"1986","unstructured":"Jerrum, M.R., Valiant, L.G., Vazirani, V.Y.: Random generation of combinatorial structures from a uniform distribution. Theoret. Comput. Sci.\u00a043, 169\u2013188 (1986)","journal-title":"Theoret. Comput. Sci."},{"key":"5_CR17","doi-asserted-by":"publisher","first-page":"709","DOI":"10.1089\/106652703322539051","volume":"10","author":"W.-F. Lu","year":"2003","unstructured":"Lu, W.-F., Hsu, W.-L.: A test for the Consecutive Ones Property on noisy data \u2013 application to physical mapping and sequence assembly. J. Comp. Biol.\u00a010, 709\u2013735 (2003)","journal-title":"J. Comp. Biol."},{"key":"5_CR18","doi-asserted-by":"publisher","first-page":"1557","DOI":"10.1101\/gr.5383506","volume":"16","author":"J. Ma","year":"2006","unstructured":"Ma, J., et al.: Reconstructing contiguous regions of an ancestral genome. Genome Res.\u00a016, 1557\u20131565 (2006)","journal-title":"Genome Res."},{"key":"5_CR19","first-page":"761","volume-title":"SODA 2004","author":"R.M. McConnell","year":"2004","unstructured":"McConnell, R.M.: A certifying algorithm for the consecutive-ones property. In: SODA 2004, pp. 761\u2013770. ACM, New York (2004)"},{"key":"5_CR20","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1016\/S0166-218X(98)00078-X","volume":"88","author":"J. Meidanis","year":"1998","unstructured":"Meidanis, J., Porto, O., Telle, G.P.: On the consecutive ones property. Discrete Appl. Math.\u00a088, 325\u2013354 (1998)","journal-title":"Discrete Appl. Math."},{"key":"5_CR21","series-title":"LNBI","volume-title":"ISBRA 2009","author":"A. Ouangraoua","year":"2009","unstructured":"Ouangraoua, A., Boyer, F., McPherson, A., Tannier, E., Chauve, C.: Prediction of contiguous ancestral regions in the amniote ancestral genome. In: Narasimhan, G., Zhang, Y., M\u0103ndoiu, I. (eds.) ISBRA 2009. LNCS (LNBI), vol.\u00a05542, Springer, Heidelberg (2009)"},{"key":"5_CR22","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1002\/net.1975.5.3.237","volume":"5","author":"R.C. Read","year":"1975","unstructured":"Read, R.C., Tarjan, R.E.: Bounds on backtrack algorithms for listing cycles, paths, and spanning trees. Networks\u00a05, 237\u2013252 (1975)","journal-title":"Networks"},{"key":"5_CR23","doi-asserted-by":"crossref","unstructured":"Stoye, J., Wittler, R.: A unified approach for reconstructing ancient gene clusters. IEEE\/ACM Trans. Comput. Biol. Bioinfo (to appear, 2009)","DOI":"10.1109\/TCBB.2008.135"},{"key":"5_CR24","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1016\/0095-8956(72)90019-6","volume":"12","author":"A.C. Tucker","year":"1972","unstructured":"Tucker, A.C.: A structure theorem for the consecutive 1\u2019s property. J. Combinat. Theory (B)\u00a012, 153\u2013162 (1972)","journal-title":"J. Combinat. Theory (B)"},{"key":"5_CR25","doi-asserted-by":"publisher","first-page":"410","DOI":"10.1137\/0208032","volume":"8","author":"L.G. Valiant","year":"1979","unstructured":"Valiant, L.G.: The complexity of enumeration and reliability problems. SIAM J. Comput.\u00a08, 410\u2013421 (1979)","journal-title":"SIAM J. Comput."}],"container-title":["Lecture Notes in Computer Science","Comparative Genomics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-04744-2_5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,22]],"date-time":"2019-05-22T15:51:26Z","timestamp":1558540286000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-04744-2_5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642047435","9783642047442"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-04744-2_5","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009]]}}}