{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:50Z","timestamp":1740109310350,"version":"3.37.3"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2019,11,4]],"date-time":"2019-11-04T00:00:00Z","timestamp":1572825600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,11,4]],"date-time":"2019-11-04T00:00:00Z","timestamp":1572825600000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2020,5]]},"DOI":"10.1007\/s00453-019-00647-9","type":"journal-article","created":{"date-parts":[[2019,11,4]],"date-time":"2019-11-04T06:03:01Z","timestamp":1572847381000},"page":"1378-1409","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Consensus Strings with Small Maximum Distance and Small Distance Sum"],"prefix":"10.1007","volume":"82","author":[{"given":"Laurent","family":"Bulteau","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5137-1504","authenticated-orcid":false,"given":"Markus L.","family":"Schmid","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,11,4]]},"reference":[{"key":"647_CR1","doi-asserted-by":"publisher","first-page":"5239","DOI":"10.1016\/j.tcs.2011.05.034","volume":"412","author":"A Amir","year":"2011","unstructured":"Amir, A., Landau, G.M., Na, J.C., Park, H., Park, K., Sim, J.S.: Efficient algorithms for consensus string problems minimizing both distance sum and radius. Theor. Comput. Sci. 412, 5239\u20135246 (2011)","journal-title":"Theor. Comput. Sci."},{"key":"647_CR2","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1016\/j.tcs.2018.03.024","volume":"730","author":"M Basavaraju","year":"2018","unstructured":"Basavaraju, M., Panolan, F., Rai, A., Ramanujan, M.S., Saurabh, S.: On the kernelization complexity of string problems. Theor. Comput. Sci. 730, 21\u201331 (2018)","journal-title":"Theor. Comput. Sci."},{"key":"647_CR3","unstructured":"Ben-Dor, A., Lancia, G., Ravi, R., Perone, J.: Banishing bias from consensus sequences. In: Proc. 8th Annual Symposium on Combinatorial Pattern Matching, CPM 1997, LNCS, 1264, pp. 247\u2013261 (1997)"},{"issue":"35","key":"647_CR4","doi-asserted-by":"publisher","first-page":"4570","DOI":"10.1016\/j.tcs.2011.04.039","volume":"412","author":"HL Bodlaender","year":"2011","unstructured":"Bodlaender, H.L., Thomass\u00e9, S., Yeo, A.: Kernel bounds for disjoint cycles and disjoint paths. Theor. Comput. Sci. 412(35), 4570\u20134578 (2011)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"647_CR5","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1137\/120880240","volume":"28","author":"HL Bodlaender","year":"2014","unstructured":"Bodlaender, H.L., Jansen, B.M.P., Kratsch, S.: Kernelization lower bounds by cross-composition. SIAM J. Discrete Math. 28(1), 277\u2013305 (2014)","journal-title":"SIAM J. Discrete Math."},{"key":"647_CR6","doi-asserted-by":"publisher","first-page":"S55","DOI":"10.1186\/1471-2105-12-S1-S55","volume":"12","author":"C Boucher","year":"2011","unstructured":"Boucher, C., Ma, B.: Closest string with outliers. BMC Bioinformatics 12, S55 (2011)","journal-title":"BMC Bioinformatics"},{"key":"647_CR7","first-page":"31","volume":"114","author":"L Bulteau","year":"2014","unstructured":"Bulteau, L., H\u00fcffner, F., Komusiewicz, C., Niedermeier, R.: Multivariate algorithmics for NP-hard string problems. Bull. EATCS 114, 31\u201373 (2014)","journal-title":"Bull. EATCS"},{"key":"647_CR8","unstructured":"Chen, J., Hermelin, D., Sorge, M.: On computing centroids according to the p-norms of hamming distance vectors. In: 27th Annual European Symposium on Algorithms, ESA 2019, September 9\u201311, 2019, Munich\/Garching, Germany, pp. 28:1\u201328:16 (2019)"},{"key":"647_CR9","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized Algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., Fomin, F., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, New York (2015)"},{"issue":"4","key":"647_CR10","doi-asserted-by":"publisher","first-page":"1073","DOI":"10.1137\/S0097539701397825","volume":"32","author":"X Deng","year":"2003","unstructured":"Deng, X., Li, G., Li, Z., Ma, B., Wang, L.: Genetic design of drugs without side-effects. SIAM J. Comput. 32(4), 1073\u20131090 (2003)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"647_CR11","first-page":"123","volume":"9","author":"J Dopazo","year":"1993","unstructured":"Dopazo, J., Rodr\u00edguez, A., S\u00e1iz, J., Sobrino, F.: Design of primers for PCR amplification of highly variable genomes. Comput. Appl. Biosci. 9(2), 123\u2013125 (1993)","journal-title":"Comput. Appl. Biosci."},{"key":"647_CR12","volume-title":"Parameterized Complexity","author":"RG Downey","year":"2012","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, New York (2012)"},{"key":"647_CR13","series-title":"Texts in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-5559-1","volume-title":"Fundamentals of Parameterized Complexity","author":"RG Downey","year":"2013","unstructured":"Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, London (2013)"},{"key":"647_CR14","unstructured":"Evans, P.A., Smith, A., Wareham, H.T.: The parameterized complexity of p-center approximate substring problems. Technical Report TR01-149, Faculty of Computer Science, University of New Brunswick, Canada (2001)"},{"key":"647_CR15","doi-asserted-by":"publisher","first-page":"407","DOI":"10.1016\/S0304-3975(03)00320-7","volume":"306","author":"PA Evans","year":"2003","unstructured":"Evans, P.A., Smith, A.D., Wareham, H.T.: On the complexity of finding common approximate substrings. Theor. Comput. Sci. 306, 407\u2013430 (2003)","journal-title":"Theor. Comput. Sci."},{"key":"647_CR16","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1007\/s00493-006-0011-4","volume":"26","author":"MR Fellows","year":"2006","unstructured":"Fellows, M.R., Gramm, J., Niedermeier, R.: On the parameterized intractability of motif search problems. Combinatorica 26, 141\u2013167 (2006)","journal-title":"Combinatorica"},{"key":"647_CR17","volume-title":"Parameterized Complexity Theory","author":"J Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Berlin (2006)"},{"key":"647_CR18","volume-title":"Kernelization: Theory of Parameterized Preprocessing","author":"FV Fomin","year":"2019","unstructured":"Fomin, F.V., Lokshtanov, D., Saurabh, S., Zehavi, M.: Kernelization: Theory of Parameterized Preprocessing. Cambridge University Press, Cambridge (2019)"},{"key":"647_CR19","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1007\/BF02679443","volume":"30","author":"M Frances","year":"1997","unstructured":"Frances, M., Litman, A.: On covering problems of codes. Theory Comput. Syst. 30, 113\u2013119 (1997)","journal-title":"Theory Comput. Syst."},{"key":"647_CR20","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1007\/s00453-003-1028-3","volume":"37","author":"J Gramm","year":"2003","unstructured":"Gramm, J., Niedermeier, R., Rossmanith, P.: Fixed-parameter algorithms for closest string and related problems. Algorithmica 37, 25\u201342 (2003)","journal-title":"Algorithmica"},{"key":"647_CR21","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1016\/S0890-5401(03)00057-9","volume":"185","author":"JK Lanctot","year":"2003","unstructured":"Lanctot, J.K., Li, M., Ma, B., Wang, S., Zhang, L.: Distinguishing string selection problems. Inf. Comput. 185, 41\u201355 (2003)","journal-title":"Inf. Comput."},{"issue":"4","key":"647_CR22","doi-asserted-by":"publisher","first-page":"538","DOI":"10.1287\/moor.8.4.538","volume":"8","author":"HW Lenstra","year":"1983","unstructured":"Lenstra, H.W.: Integer programming with a fixed number of variables. Math. Oper. Res. 8(4), 538\u2013548 (1983)","journal-title":"Math. Oper. Res."},{"issue":"1","key":"647_CR23","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1006\/jcss.2002.1823","volume":"65","author":"M Li","year":"2002","unstructured":"Li, M., Ma, B., Wang, L.: Finding similar regions in many sequences. J. Comput. Syst. Sci. 65(1), 73\u201396 (2002). \nhttps:\/\/doi.org\/10.1006\/jcss.2002.1823","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"647_CR24","first-page":"525","volume":"7","author":"K Lucas","year":"1991","unstructured":"Lucas, K., Busch, M., M\u00f6ssinger, S., Thompson, J.A.: An improved microcomputer program for finding gene- or gene family-specific oligonucleotides suitable as primers for polymerase chain reactions or as probes. Comput. Appl. Biosci. 7(4), 525\u2013529 (1991)","journal-title":"Comput. Appl. Biosci."},{"key":"647_CR25","doi-asserted-by":"publisher","first-page":"1382","DOI":"10.1137\/060673898","volume":"38","author":"D Marx","year":"2008","unstructured":"Marx, D.: Closest substring problems with small distances. SIAM J. Comput. 38, 1382\u20131410 (2008)","journal-title":"SIAM J. Comput."},{"key":"647_CR26","doi-asserted-by":"publisher","first-page":"S207","DOI":"10.1093\/bioinformatics\/17.suppl_1.S207","volume":"17","author":"G Pavesi","year":"2001","unstructured":"Pavesi, G., Mauri, G., Pesole, G.: An algorithm for finding signals of unknown length in DNA sequences. Bioinformatics 17, S207\u2013S214 (2001)","journal-title":"Bioinformatics"},{"key":"647_CR27","unstructured":"Pevzner, P., Sze, S.: Combinatorial approaches to finding subtle signals in DNA strings. In: Proceedings of the 8th International Conference on Intelligent Systems for Molecular Biology, ISMB 2000, pp. 269\u2013278 (2000)"},{"issue":"3","key":"647_CR28","first-page":"253","volume":"12","author":"V Proutski","year":"1996","unstructured":"Proutski, V., Holmes, E.C.: Primer master: a new program for the design and analysis of PCR primers. Comput. Appl. Biosci. 12(3), 253\u2013255 (1996)","journal-title":"Comput. Appl. Biosci."},{"issue":"3","key":"647_CR29","doi-asserted-by":"publisher","first-page":"13:1","DOI":"10.1145\/3110290","volume":"9","author":"ML Schmid","year":"2017","unstructured":"Schmid, M.L.: Finding consensus strings with small length difference between input and solution strings. TOCT 9(3), 13:1\u201313:18 (2017)","journal-title":"TOCT"},{"issue":"1","key":"647_CR30","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1038\/nbt1053","volume":"23","author":"M Tompa","year":"2005","unstructured":"Tompa, M., Li, N., Bailey, T.L., Church, G.M., Moor, B.D., Eskin, E., Favorov, A.V., Frith, M.C., Fu, Y., Kent, W.J., Makeev, V.J., Mironov, A.A., Noble, W.S., Pavesi, G., Pesole, G., R\u00e9gnier, M., Simonis, N., Sinha, S., Thijs, G., van Helden, J., Vandenbogaert, M., Weng, Z., Workman, C., Ye, C., Zhu, Z.: Assessing computational tools for the discovery of transcription factor binding sites. Nat. Biotechnol. 23(1), 137\u2013144 (2005)","journal-title":"Nat. Biotechnol."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00647-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-019-00647-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00647-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,3]],"date-time":"2020-11-03T00:11:28Z","timestamp":1604362288000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-019-00647-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,11,4]]},"references-count":30,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2020,5]]}},"alternative-id":["647"],"URL":"https:\/\/doi.org\/10.1007\/s00453-019-00647-9","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2019,11,4]]},"assertion":[{"value":"20 November 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 October 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 November 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}