{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T19:35:18Z","timestamp":1725564918815},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540223412"},{"type":"electronic","value":"9783540278016"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-27801-6_10","type":"book-chapter","created":{"date-parts":[[2010,9,5]],"date-time":"2010-09-05T23:00:15Z","timestamp":1283727615000},"page":"130-144","source":"Crossref","is-referenced-by-count":9,"title":["On the k-Closest Substring and k-Consensus Pattern Problems"],"prefix":"10.1007","author":[{"given":"Yishan","family":"Jiao","sequence":"first","affiliation":[]},{"given":"Jingyi","family":"Xu","sequence":"additional","affiliation":[]},{"given":"Ming","family":"Li","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"4","key":"10_CR1","doi-asserted-by":"publisher","first-page":"630","DOI":"10.1145\/179812.179818","volume":"41","author":"T. Blum","year":"1994","unstructured":"Blum, T., Jiang, M., Li, J.: Linear Approximation of Shortest Superstrings. Journal of the ACM\u00a041(4), 630\u2013647 (1994)","journal-title":"Journal of the ACM"},{"key":"10_CR2","doi-asserted-by":"publisher","first-page":"419","DOI":"10.1093\/bioinformatics\/17.5.419","volume":"17","author":"J. Buhler","year":"2001","unstructured":"Buhler, J.: Efficient large-scale sequence comparison by locality-sensitive hashing. Bioinformatics\u00a017, 419\u2013428 (2001)","journal-title":"Bioinformatics"},{"key":"10_CR3","doi-asserted-by":"crossref","unstructured":"Feder, T., Greene, D.H.: Optimal algorithms for approximate clustering. In: Proceedings of the 20th Annual ACM Symposium on Theory of Computing, pp. 434\u2013444 (1988)","DOI":"10.1145\/62212.62255"},{"issue":"3","key":"10_CR4","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1016\/0020-0190(81)90111-3","volume":"12","author":"R.J. Fowler","year":"1981","unstructured":"Fowler, R.J., Paterson, M.S., Tanimoto, S.L.: Optimal packing and covering in the plane are NP-complete. Inf. Proc. Letters\u00a012(3), 133\u2013137 (1981)","journal-title":"Inf. Proc. Letters"},{"key":"10_CR5","doi-asserted-by":"publisher","first-page":"826","DOI":"10.1137\/0132071","volume":"32","author":"M.R. Garey","year":"1977","unstructured":"Garey, M.R., Johnson, D.S.: The rectilinear Steiner tree problem is NPcomplete. SIAM J. Appl. Math.\u00a032, 826\u2013834 (1977)","journal-title":"SIAM J. Appl. Math."},{"key":"10_CR6","unstructured":"Gasieniec, L., Jansson, J., Lingas, A.: Efficient approximation algorithms for the Hamming center problem. In: Proc. 10th ACM-SIAM Symp. on Discrete Algorithms (1999),pp.S905\u2013S906 (1999)"},{"key":"10_CR7","doi-asserted-by":"crossref","unstructured":"Gasieniec, L., Jansson, J., Lingas, A.: Approximation Algorithms for Hamming Clustering Problems. In: Proc. 11th Symp. CPM (2000), pp. 108\u2013118 (2000)","DOI":"10.1007\/3-540-45123-4_11"},{"key":"10_CR8","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1016\/0304-3975(85)90224-5","volume":"38","author":"T.F. Gonzalez","year":"1985","unstructured":"Gonzalez, T.F.: Clustering to minimize the maximum intercluster distance. Theoretical Computer Science\u00a038, 293\u2013306 (1985)","journal-title":"Theoretical Computer Science"},{"key":"10_CR9","doi-asserted-by":"crossref","unstructured":"Indyk, P., Motwani, R.: Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality. In: Proc. 30th Annual ACM Symp. Theory Comput., pp. 604\u2013613 (1998)","DOI":"10.1145\/276698.276876"},{"key":"10_CR10","unstructured":"Jansson, J.: Consensus Algorithms for Trees and Strings. Doctoral dissertation (2003)"},{"key":"10_CR11","unstructured":"Lanctot, K., Li, M., Ma, B., Wang, L., Zhang, L.: Distinguishing string selection problems. In: Proc. 10th ACM-SIAM Symp. Discrete Algorithms, pp. 633\u2013642 (1999)"},{"key":"10_CR12","doi-asserted-by":"crossref","unstructured":"Li, M., Ma, B., Wang, L.: Finding similar regions in many strings. In: Proceedings of the 31st Annual ACM Symposium on Theory of Computing (1999), pp. 473\u2013482 (1999)","DOI":"10.1145\/301250.301376"},{"issue":"2","key":"10_CR13","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1145\/506147.506150","volume":"49","author":"M. Li","year":"2002","unstructured":"Li, M., Ma, B., Wang, L.: On the Closest String and Substring Problems. Journal of ACM\u00a049(2), 157\u2013171 (2002)","journal-title":"Journal of ACM"},{"key":"10_CR14","doi-asserted-by":"crossref","unstructured":"Ma, B.: A polynomial time approximation scheme for the Closest Substring problem. In: Proc. 11th Annual Symposium on Combinatorial Pattern Matching, pp. 99\u2013107 (2000)","DOI":"10.1007\/3-540-45123-4_10"},{"key":"10_CR15","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511814075","volume-title":"Randomized Algorithms","author":"R. Motwani","year":"1995","unstructured":"Motwani, R., Raghavan, P.: Randomized Algorithms. Cambridge University Press, Cambridge (1995)"},{"issue":"2","key":"10_CR16","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1145\/506147.506149","volume":"49","author":"R. Ostrovsky","year":"2002","unstructured":"Ostrovsky, R., Rabani, Y.: Polynomial-Time Approximation Schemes for Geometric Min-Sum Median Clustering. Journal of ACM\u00a049(2), 139\u2013156 (2002)","journal-title":"Journal of ACM"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Pattern Matching"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-27801-6_10.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,3]],"date-time":"2021-05-03T03:26:51Z","timestamp":1620012411000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-27801-6_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540223412","9783540278016"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-27801-6_10","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2004]]}}}