No Access
A hybrid metaheuristic for Closest String Problem
Published Online:July 22, 2011pp 245-261
Abstract
The Closest String Problem (CSP) is an optimisation problem, which is to obtain a string with the minimum distance from a number of given strings. In this paper, a new metaheuristic algorithm is investigated for the problem, whose main feature is relatively high speed in obtaining good solutions, which is essential when the input size is large. The proposed algorithm is compared with four recent algorithms suggested for the problem, outperforming them in more than 98% of the cases. It is also remarkably faster than all of them, running within 1 s in most of the experimental cases.
Keywords
References
- 1. M. Babaie, S.R. Mousavi, '‘A memetic algorithm for closest string problem and farthest string problem’' (2010) Google Scholar
- 2. S. Böcker, K. Jahn, J. Mixtacki, J. Stoye, M. Vingron Ed., L. Wong Ed., '‘Computation of median gene clusters’' RECOMB (2008) Google Scholar
- 3. S. Böcker, K. Jahn, J. Mixtacki, J. Stoye, '‘Computation of median gene clusters’' Journal of Computational Biology (2009) Google Scholar
- 4. C.H. Cheng, C.C. Huang, S.Y. Hu, K. Chao, '‘Efficient algorithms for some variants of the farthest string problem’' (2004) Google Scholar
- 5. J-C. Chen, '‘Iterative rounding for the closest string problem’' CoRR (2007) Google Scholar
- 6. C.N. Meneses, Z. Lu, C.A.S. Oliveira, P.M. Pardalos, '‘Optimal solutions for the closest-string problem via integer programming’' INFORMS Journal on Computing (2004) Google Scholar
- 7. M. Dorigo, C. Blum, '‘Ant colony optimization theory: a survey’' Theor. Comput. Sci. (2005) Google Scholar
- 8. S. Faro, E. Pappalardo, J. van Leeuwen Ed., A. Muscholl Ed., D. Peleg Ed., J. Pokorný Ed., B. Rumpe Ed., '‘Ant-csp: an ant colony optimization algorithm for the closest string problem’' SOFSEM (2010) Google Scholar
- 9. P. Festa, '‘On some optimization problems in molecular biology’' Mathematical Biosciences (2007) Google Scholar
- 10. M. Frances, A. Litman, '‘On covering problems of codes’' Theory Comput. Syst. (1997) Google Scholar
- 11. M.R. Garey, D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (1979) Google Scholar
- 12. F.C. Gomes, C.N. Meneses, P.M. Pardalos, G.V.R. Viana, '‘A parallel multistart algorithm for the closest string problem’' Computers & OR (2008) Google Scholar
- 13. J. Gramm, J. Guo, R. Niedermeier, '‘On exact and approximation algorithms for distinguishing substring selection’' FCT (2003a) Google Scholar
- 14. J. Gramm, F. Hüffner, R. Niedermeier, '‘Closest strings, primer design, and motif search’' (2002) Google Scholar
- 15. J. Gramm, R. Niedermeier, P. Rossmanith, '‘Exact solutions for closest string and related problems’' ISAAC (2001) Google Scholar
- 16. J. Gramm, R. Niedermeier, P. Rossmanith, '‘Fixed-parameter algorithms for closest string and related problems’' Algorithmica (2003b) Google Scholar
- 17. J. Gramm, M-Y. Kao Ed., '‘Closest substring’' Encyclopedia of Algorithms (2008) Google Scholar
- 18. G.Z. Hertz, G.W. Hartzell, G.D. Stormo, '‘Identification of consensus patterns in unaligned dna sequences known to be functionally related’' Computer Applications in the Biosciences (1990) Google Scholar
- 19. F. Hufsky, L. Kuchenbecker, K. Jahn, J. Stoye, S. Böcker, V. Moulton Ed., M. Singh Ed., '‘Swiftly computing center strings’' WABI (2010) Google Scholar
- 20. Y. Jiao, J. Xu, M. Li, '‘On the k-closest substring and k-consensus pattern problems’' CPM (2004) Google Scholar
- 21. B.A. Julstrom, '‘A data-based coding of candidate strings in the closest string problem’' GECCO ’09: Proceedings of the 11th Annual Conference Companion on Genetic and Evolutionary Computation Conference (2009) Google Scholar
- 22. J.K. Lanctot, M. Li, B. Ma, S. Wang, L. Zhang, '‘Distinguishing string selection problems’' SODA ’99: Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics (1999) Google Scholar
- 23. J.K. Lanctot, M. Li, B. Ma, S. Wang, L. Zhang, '‘Distinguishing string selection problems’' Inf. Comput. (2003) Google Scholar
- 24. J.K. Lanctot, Some String Problems in Computational Biology (2000) Google Scholar
- 25. X. Liu, H. Mauch, G. Wu, '‘A compounded genetic and simulated annealing algorithm for the closest string problem’' ICBBE ’08: Proceedings of the 2nd International Conference on Bioinformatics and Biomedical Engineering (2008) Google Scholar
- 26. M. Li, B. Ma, L. Wang, '‘Finding similar regions in many strings’' STOC ’99: Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing (1999) Google Scholar
- 27. M. Li, B. Ma, L. Wang, '‘On the closest string and substring problem’' Journal of the ACM (2002) Google Scholar
- 28. A.J.L. Macario, E.C. de Macario, Gene Probes for Bacteria (1990) Google Scholar
- 29. H. Mauch, M.J. Melzer, J.S. Hu, '‘Genetic algorithm approach for the closest string problem’' CSB ’03: Proceedings of the IEEE Computer Society Conference on Bioinformatics (2003) Google Scholar
- 30. B. Ma, X. Sun, '‘More efficient algorithms for closest string and substring problems’' (2008) Google Scholar
- 31. C.N. Meneses, C.A.S. Oliveira, P.M. Pardalos, '‘Optimization techniques for string selection and comparison problems in genomics’' Engineering in Medicine and Biology Magazine, IEEE (2005a) Google Scholar
- 32. C.N. Meneses, P.M. Pardalos, M.G.C. Resende, A. Vazacopoulos, '‘Modeling and solving string selection problems’' (2005b) Google Scholar
- 33. S.R. Mousavi, N.N. Esfahani, '‘A GRASP algorithm for the closest string problem using a probability-based heuristic’' Computers and Operations Research (2011) Google Scholar
- 34. S.R. Mousavi, '‘A hybridization of constructive beam search with local search for far from most strings problem’' International Journal of Computational and Mathematical Sciences (2010) Google Scholar
- 35. J. Wang, J. Chen, J.M. Huang, '‘An improved lower bound on approximation algorithms for the closest substring problem’' Information Processing Letters (2008) Google Scholar
