{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:22:39Z","timestamp":1759638159530},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2014,10,28]],"date-time":"2014-10-28T00:00:00Z","timestamp":1414454400000},"content-version":"tdm","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":[[2016,1]]},"DOI":"10.1007\/s00453-014-9952-y","type":"journal-article","created":{"date-parts":[[2014,10,27]],"date-time":"2014-10-27T11:44:49Z","timestamp":1414410289000},"page":"466-484","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Randomized Fixed-Parameter Algorithms for the Closest String Problem"],"prefix":"10.1007","volume":"74","author":[{"given":"Zhi-Zhong","family":"Chen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bin","family":"Ma","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lusheng","family":"Wang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2014,10,28]]},"reference":[{"key":"9952_CR1","doi-asserted-by":"crossref","unstructured":"B\u00f6cker, S., Jahn, K., Mixtacki, J., Stoye, J.: Computation of median gene clusters. J. Comput. Biol. 16(8), 1085\u20131099 (2009)","DOI":"10.1089\/cmb.2009.0098"},{"key":"9952_CR2","doi-asserted-by":"crossref","unstructured":"Boucher, C., Brown, D.: Detecting motifs in a large data set: applying probabilistic insights to motif finding. In: Proceedings of the Conference on Bioinformatics and Computational Biology (BICoB), pp. 139\u2013150 (2009)","DOI":"10.1007\/978-3-642-00727-9_15"},{"key":"9952_CR3","doi-asserted-by":"crossref","unstructured":"Ben-Dor, A., Lancia, G., Perone, J., Ravi, R.: Banishing bias from consensus sequences. In: Proceedings of the 8th Annual Symposium on Combinatorial Pattern Matching, pp. 247\u2013261 (1997)","DOI":"10.1007\/3-540-63220-4_63"},{"issue":"4","key":"9952_CR4","doi-asserted-by":"crossref","first-page":"472","DOI":"10.1007\/s00453-008-9206-y","volume":"54","author":"J Chen","year":"2008","unstructured":"Chen, J., Lu, S.: Improved parameterized set splitting algorithms: a probabilistic approach. Algorithmica 54(4), 472\u2013489 (2008)","journal-title":"Algorithmica"},{"key":"9952_CR5","unstructured":"Chen, J., Lu, S., Sze, S.H., Zhang, F.: Improved algorithms for path, matching, and packing problems. In: Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 298\u2013307 (2007)"},{"key":"9952_CR6","doi-asserted-by":"crossref","first-page":"164","DOI":"10.1016\/j.jcss.2011.01.003","volume":"78","author":"Z-Z Chen","year":"2012","unstructured":"Chen, Z.-Z., Ma, B., Wang, L.: A three-string approach to the closest string problem. J. Comput. Syst. Sci. 78, 164\u2013178 (2012)","journal-title":"J. Comput. Syst. Sci."},{"issue":"5","key":"9952_CR7","doi-asserted-by":"crossref","first-page":"1400","DOI":"10.1109\/TCBB.2011.21","volume":"8","author":"Z-Z Chen","year":"2011","unstructured":"Chen, Z.-Z., Wang, L.: Fast exact algorithms for the closest string and substring problems with application to the planted $$(\\ell, d)$$ ( \u2113 , d ) -motif model. IEEE\/ACM Trans. Comput. Biol. Bioinform. 8(5), 1400\u20131410 (2011)","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform."},{"key":"9952_CR8","doi-asserted-by":"crossref","unstructured":"Davila, J., Balla, S., Rajasekaran, S.: Space and time efficient algorithms for planted motif search. In: Proceedings of the International Conference on Computational Science, pp. 822\u2013829 (2006)","DOI":"10.1007\/11758525_110"},{"issue":"4","key":"9952_CR9","doi-asserted-by":"crossref","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."},{"key":"9952_CR10","first-page":"123","volume":"9","author":"J Dopazo","year":"1993","unstructured":"Dopazo, J., Rodr\u00edguez, A., S\u00e1iz, J.C., Sobrino, F.: Design of primers for PCR amplification of highly variable genomes. CABIOS 9, 123\u2013125 (1993)","journal-title":"CABIOS"},{"key":"9952_CR11","doi-asserted-by":"crossref","unstructured":"Evans, P.A., Smith, A.D.: Complexity of approximating closest substring problems. In Proceedings of the 14th International Symposium on Foundations of Complexity Theory, pp. 210\u2013221 (2003)","DOI":"10.1007\/978-3-540-45077-1_20"},{"issue":"2","key":"9952_CR12","doi-asserted-by":"crossref","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(2), 141\u2013167 (2006)","journal-title":"Combinatorica"},{"key":"9952_CR13","doi-asserted-by":"crossref","unstructured":"Feng, Q., Wang, J., Li, S., Chen, J.: Random methods for parameterized problems. In: Proceedings of the 19th International Computing and Combinatorics Conference (COCOON), pp. 89\u2013100 (2013)","DOI":"10.1007\/978-3-642-38768-5_10"},{"key":"9952_CR14","first-page":"113","volume":"30","author":"M Frances","year":"1997","unstructured":"Frances, M., Litman, A.: On covering problems of codes. Theor. Comput. Sci. 30, 113\u2013119 (1997)","journal-title":"Theor. Comput. Sci."},{"key":"9952_CR15","doi-asserted-by":"crossref","unstructured":"Gramm, J., Guo, J., Niedermeier, R.: On exact and approximation algorithms for distinguishing substring selection. In: Proceedings of the 14th International Symposium on Foundations of Complexity Theory, pp. 159\u2013209 (2003)","DOI":"10.1007\/978-3-540-45077-1_19"},{"key":"9952_CR16","unstructured":"Gramm, J., H\u00fcffner, F., Niedermeier, R.: Closest strings, primer design, and motif search. In: Florea, L. et al. (eds.) Currents in Computational Molecular Biology. Poster Abstracts of RECOMB 2002, pp. 74\u201375"},{"key":"9952_CR17","doi-asserted-by":"crossref","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":"9952_CR18","doi-asserted-by":"crossref","unstructured":"Hufsky, F., Kuchenbecker, L., Jahn, K., Stoye, J., B\u00f6cker, S.: Swiftly computing center strings. In: Proceedings of the 10th International Workshop on Algorithms in Bioinformatics, pp. 325\u2013336 (2010)","DOI":"10.1007\/978-3-642-15294-8_27"},{"key":"9952_CR19","doi-asserted-by":"crossref","unstructured":"Jiao, Y., Xu, J., Li, M.: On the k-closest substring and k-consensus pattern problems. In: Proceedings of the 15th Annual Symposium on Combinatorial Pattern Matching, pp. 130\u2013144 (2004)","DOI":"10.1007\/978-3-540-27801-6_10"},{"key":"9952_CR20","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1016\/S0890-5401(03)00057-9","volume":"185","author":"K Lanctot","year":"2003","unstructured":"Lanctot, K., Li, M., Ma, B., Wang, S., Zhang, L.: Distinguishing string search problems. Inf. Comput. 185, 41\u201355 (2003)","journal-title":"Inf. Comput."},{"issue":"2","key":"9952_CR21","doi-asserted-by":"crossref","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. J. ACM 49(2), 157\u2013171 (2002)","journal-title":"J. ACM"},{"key":"9952_CR22","first-page":"525","volume":"7","author":"K Lucas","year":"1991","unstructured":"Lucas, K., Busch, M., M\u00f6singer, 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. CABIOS 7, 525\u2013529 (1991)","journal-title":"CABIOS"},{"issue":"4","key":"9952_CR23","doi-asserted-by":"crossref","first-page":"1432","DOI":"10.1137\/080739069","volume":"39","author":"B Ma","year":"2010","unstructured":"Ma, B., Sun, X.: More efficient algorithms for closest string and substring problems. SIAM J. Comput. 39(4), 1432\u20131443 (2010)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"9952_CR24","doi-asserted-by":"crossref","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(4), 1382\u20131410 (2008)","journal-title":"SIAM J. Comput."},{"key":"9952_CR25","doi-asserted-by":"crossref","unstructured":"Marx, D.: Randomized techniques for parameterized algorithms. In: Proceedings of the 7th International Symposium on Parameterized and Exact Computation (IPEC), p. 2 (2012)","DOI":"10.1007\/978-3-642-33293-7_2"},{"key":"9952_CR26","doi-asserted-by":"crossref","unstructured":"Marx, D., Razgon, I.: Fixed-parameter tractability of multicut parameterized by the size of the cutset. In: Proceedings of the 43rd Annual ACM Symposium on Theory of Computing (STOC), pp. 469\u2013478 (2011)","DOI":"10.1145\/1993636.1993699"},{"key":"9952_CR27","doi-asserted-by":"crossref","unstructured":"Mauch, H., Melzer, M.J., Hu, J.S.: Genetic algorithm approach for the closest string problem. In: Proceedings of the 2nd IEEE Computer Society Bioinformatics Conference (CSB), pp. 560\u2013561 (2003)","DOI":"10.1109\/CSB.2003.1227407"},{"key":"9952_CR28","doi-asserted-by":"crossref","first-page":"419","DOI":"10.1287\/ijoc.1040.0090","volume":"16","author":"CN Meneses","year":"2004","unstructured":"Meneses, C.N., Lu, Z., Oliveira, C.A.S., Pardalos, P.M.: Optimal solutions for the closest-string problem via integer programming. INFORMS J. Comput. 16, 419\u2013429 (2004)","journal-title":"INFORMS J. Comput."},{"key":"9952_CR29","doi-asserted-by":"crossref","unstructured":"Nicolas, F., Rivals, E.: Complexities of the centre and median string problems. In: Proceedings of the 14th Annual Symposium on Combinatorial Pattern Matching, pp. 315\u2013327 (2003)","DOI":"10.1007\/3-540-44888-8_23"},{"key":"9952_CR30","first-page":"253","volume":"12","author":"V Proutski","year":"1996","unstructured":"Proutski, V., Holme, E.C.: Primer master: a new program for the design and analysis of PCR primers. CABIOS 12, 253\u2013255 (1996)","journal-title":"CABIOS"},{"key":"9952_CR31","doi-asserted-by":"crossref","unstructured":"Stojanovic, N., Berman, P., Gumucio, D., Hardison, R., Miller, W.: A linear-time algorithm for the 1-mismatch problem. In: Proceedings of the 5th International Workshop on Algorithms and Data Structures, pp. 126\u2013135 (1997)","DOI":"10.1007\/3-540-63307-3_53"},{"issue":"5","key":"9952_CR32","doi-asserted-by":"crossref","first-page":"1039","DOI":"10.1142\/S0219720005001508","volume":"3","author":"L Wang","year":"2005","unstructured":"Wang, L., Dong, L.: Randomized algorithms for motif detection. J. Bioinform. Comput. Biol. 3(5), 1039\u20131052 (2005)","journal-title":"J. Bioinform. Comput. Biol."},{"key":"9952_CR33","doi-asserted-by":"crossref","unstructured":"Wang, L., Zhu, B.: Efficient algorithms for the closest string and distinguishing string selection problems. In: Proceedings of the 3rd International Frontiers of Algorithmics Workshop, pp. 261\u2013270 (2009)","DOI":"10.1007\/978-3-642-02270-8_27"},{"issue":"Suppl. 4","key":"9952_CR34","doi-asserted-by":"crossref","first-page":"S9","DOI":"10.1186\/1471-2105-7-S4-S9","volume":"7","author":"Y Wang","year":"2006","unstructured":"Wang, Y., Chen, W., Li, X., Cheng, B.: Degenerated primer design to amplify the heavy chain variable region from immunoglobulin cDNA. BMC Bioinform. 7(Suppl. 4), S9 (2006)","journal-title":"BMC Bioinform."},{"key":"9952_CR35","unstructured":"Zhao, R., Zhang, N.: A more efficient closest string algorithm. In: Proceedings of the 2nd International Conference on Bioinformatics and Computational Biology (2010)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-014-9952-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-014-9952-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-014-9952-y","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T09:45:14Z","timestamp":1559123114000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-014-9952-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,10,28]]},"references-count":35,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2016,1]]}},"alternative-id":["9952"],"URL":"https:\/\/doi.org\/10.1007\/s00453-014-9952-y","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,10,28]]}}}