{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T00:39:19Z","timestamp":1725496759355},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540402053"},{"type":"electronic","value":"9783540448679"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/3-540-44867-5_16","type":"book-chapter","created":{"date-parts":[[2007,11,30]],"date-time":"2007-11-30T01:34:45Z","timestamp":1196386485000},"page":"195-208","source":"Crossref","is-referenced-by-count":0,"title":["A Clustering Algorithm for Interval Graph Test on Noisy Data"],"prefix":"10.1007","author":[{"given":"Wei-Fu","family":"Lu","sequence":"first","affiliation":[]},{"given":"Wen-Lian","family":"Hsu","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2003,5,13]]},"reference":[{"key":"16_CR1","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1016\/S0166-218X(96)00057-1","volume":"71","author":"H. L. Bodlaender","year":"1996","unstructured":"H. L. Bodlaender, B. de Fluiter. On Intervalizing k-Colored Graphs for DNA Physical Mapping. Discrete Applied Math., 71, 55\u201377, 1996.","journal-title":"Discrete Applied Math."},{"key":"16_CR2","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1016\/S0022-0000(76)80045-1","volume":"13","author":"K. S. Booth","year":"1976","unstructured":"K. S. Booth and G. S. Lueker, Testing for the Consecutive Ones Property, Interval Graphs, and Graph Planarity Using PQ-tree Algorithms, J. Comput Syst. Sci., 13, 335\u2013379, 1976.","journal-title":"J. Comput Syst. Sci."},{"key":"16_CR3","doi-asserted-by":"crossref","first-page":"1059","DOI":"10.1139\/g89-182","volume":"31","author":"A. V. Carrano","year":"1989","unstructured":"A. V. Carrano, P. J. de John, E. Branscomb, T. Slezak, B. W. Watkins. Constructing chromosome and region-specific cosmid map of the human genome, Genome, 31, 1059\u20131065, 1989.","journal-title":"Genome"},{"key":"16_CR4","doi-asserted-by":"publisher","first-page":"7821","DOI":"10.1073\/pnas.83.20.7821","volume":"83","author":"A. Coulson","year":"1987","unstructured":"A. Coulson, J. Sulston, S. Brenner, J. Karn. Towatrd a physical map of the genome of the nematode, Caenorhabditis Elegans. Proc. Natl. Acad. Sci. USA, 83, 7821\u20137825, 1987.","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"16_CR5","first-page":"260","volume":"726","author":"M. R. Fellows","year":"1993","unstructured":"M. R. Fellows, M. T. Hallett, H. T. Wareham. DNA Physical Mapping: Three Ways Difficult. LNCS 726, 260\u2013271, 1993.","journal-title":"LNCS"},{"key":"16_CR6","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1016\/0735-0651(87)90010-0","volume":"4","author":"R. M. Gemmil","year":"1987","unstructured":"R. M. Gemmil, J. F. Coyle-Morris, F. D. Jr. McPeek, L. F. Wara-Uribe, F. Hecht. Construction of long-range restriction maps in human DNA using pulsed filed gel electrophoresis. Gene Anal. Technol., 4, 119\u2013131, 1987.","journal-title":"Gene Anal. Technol."},{"key":"16_CR7","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1089\/cmb.1995.2.139","volume":"2","author":"P. W. Goldberg","year":"1995","unstructured":"P. W. Goldberg. M. C. Golumbic, H. Kaplan and R. Shamir. Four strikes against physical mapping of DNA. J. Comput. Biol., 2, 139\u2013152, 1995.","journal-title":"J. Comput. Biol."},{"key":"16_CR8","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1006\/aama.1994.1009","volume":"15","author":"M. C. Golumbic","year":"1994","unstructured":"M. C. Golumbic, H. Kaplan, R. Shamir. On the complexity of DNA physical mapping. Advances in Applied Mathematics, 15, 251\u2013261, 1994.","journal-title":"Advances in Applied Mathematics"},{"key":"16_CR9","doi-asserted-by":"publisher","first-page":"94","DOI":"10.1126\/science.2218515","volume":"250","author":"E. D. Green","year":"1990","unstructured":"E. D. Green and M. V. Olson. Chromosomal region of the cystic fibrosis gene in yeast artificial chromosomes: a model for human genome mapping, Science, 250, 94\u201398, 1990.","journal-title":"Science"},{"key":"16_CR10","first-page":"11","volume":"657","author":"W. L. Hsu","year":"1992","unstructured":"W. L. Hsu, As imple test for interval graphs, LNCS 657, 11\u201316, 1992.","journal-title":"LNCS"},{"key":"16_CR11","first-page":"52","volume":"557","author":"W. L. Hsu","year":"1991","unstructured":"W. L. Hsu and T. H. Ma, Substitution Decomposition on Chordal Graphs and Applications, LNCS 557, 52\u201360, 1991.","journal-title":"LNCS"},{"key":"16_CR12","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1137\/0218005","volume":"18","author":"N. Korte","year":"1989","unstructured":"N. Korte and R. H. Mohring, An Incremental Linear-Time Algorithm for Recognizing Interval Graphs, SIAM J. Comput., 18, 68\u201381, 1989.","journal-title":"SIAM J. Comput."},{"issue":"3","key":"16_CR13","doi-asserted-by":"publisher","first-page":"540","DOI":"10.1137\/S0097539793258143","volume":"25","author":"H. Kaplan","year":"1996","unstructured":"H. Kaplan, R. Shamir. Pathwidth, bandwidth, and completion problems to proper interval graphs with small cliques. SIAM J. Comput., 25(3), 540\u2013561, 1996.","journal-title":"SIAM J. Comput."},{"key":"16_CR14","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1007\/PL00009277","volume":"24","author":"H. Kaplan","year":"1999","unstructured":"H. Kaplan, R. Shamir. Bounded Degree Interval Sandwich Problems. Algorithmica, 24, 96\u2013104, 1999.","journal-title":"Algorithmica"},{"issue":"5","key":"16_CR15","doi-asserted-by":"publisher","first-page":"1906","DOI":"10.1137\/S0097539796303044","volume":"28","author":"H. Kaplan","year":"1999","unstructured":"H. Kaplan, R. Shamir, R. E. Tarjan. Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval Graphs. SIAM J. Comput., 28(5), 1906\u20131922, 1999.","journal-title":"SIAM J. Comput."},{"key":"16_CR16","unstructured":"W. F. Lu and W. L. Hsu. A test for the Consecutive Ones Property on Noisy Data. To appear in Journal of Computational Biology."},{"issue":"3","key":"16_CR17","first-page":"203","volume":"3","author":"F. Michiels","year":"1987","unstructured":"F. Michiels, A. G. Craig, G. Zehetner, G. P. Smith, and H. Lehrach. Molecular approaches to genome analysis: A strategy for the construction of ordered overlapping clone libraries. Comput. App. Biosci., 3(3), 203\u2013210, 1987.","journal-title":"Comput. App. Biosci."},{"key":"16_CR18","doi-asserted-by":"crossref","unstructured":"A. Natanzon, R. Shamir, R. Sharan. A Polynomial Approximation Algorithm for the Minimum Fill-In Problem. STOC 1998, 41\u201347, 1998.","DOI":"10.1145\/276698.276710"},{"key":"16_CR19","doi-asserted-by":"publisher","first-page":"7826","DOI":"10.1073\/pnas.83.20.7826","volume":"83","author":"M. V. Olson","year":"1989","unstructured":"M. V. Olson, E. Dutchik, M. Y. Graham, G. M. Brodeur, C. Helms, M. Frank, M. MacCollin, R. Acheinman, T. Frand. Random-clone strategy for genomic restriction mapping in yeast, Proc. Natl. Acad. Sci. USA, 83, 7826\u20137830, 1989.","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"16_CR20","first-page":"1434","volume":"234","author":"M. V. Olson","year":"1985","unstructured":"M. V. Olson, L. Hood, C. Cantor, and D. Botstein, A common language for physical mapping of the human genome, Science, 234, 1434\u20131435, 1985.","journal-title":"Science"},{"issue":"4","key":"16_CR21","doi-asserted-by":"publisher","first-page":"585","DOI":"10.1145\/263867.263872","volume":"44","author":"M. Stoer","year":"1997","unstructured":"M. Stoer and F. Wagner. A simple min-cut algorithm. J. ACM, 44(4), 585\u2013591, 1997.","journal-title":"J. ACM"},{"key":"16_CR22","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1137\/0602010","volume":"2","author":"M. Yannakakis","year":"1981","unstructured":"M. Yannakakis. Computing the Minimum Fill-In is NP-Complete, SIAM J. Alg. Disc. Meth, 2, 77\u201379, 1981.","journal-title":"SIAM J. Alg. Disc. Meth"}],"container-title":["Lecture Notes in Computer Science","Experimental and Efficient Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44867-5_16","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,2,25]],"date-time":"2019-02-25T19:38:39Z","timestamp":1551123519000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44867-5_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540402053","9783540448679"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/3-540-44867-5_16","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2003]]}}}