Abstract
In this paper, we consider the problem of finding a minimum common partition of two strings. The problem has its application in Genome Comparison. As it is an NP-hard, discrete combinatorial optimization problem, we employ a metaheuristic technique, namely, MAX–MIN ant system to solve this problem. To achieve better efficiency we first map the problem instance into a special kind of graph. Subsequently, we employ a MAX–MIN ant system to achieve high quality solutions for the problem. Experimental results show the superiority of our algorithm in comparison with the state of art algorithms in the literature. The improvement achieved is also justified by a standard statistical test.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles and news from researchers in related subjects, suggested using machine learning.Avoid common mistakes on your manuscript.
References
Blum, C.: Beam-ACO for the longest common subsequence problem. In: IEEE Congress on Evolutionary Computation, pp. 1–8. IEEE (2010)
Blum, C., Lozano, J., Davidson, P.P.: Iterative probabilistic tree search for the minimum common string partition problem. In: Blesa, M., Blum, C., Voß, S. (eds.) Hybrid Metaheuristics, pp. 145–154. Springer, Berlin (2014)
Blum, C., Lozano, J., Davidson, P.P.: Mathematical programming strategies for solving the minimum common string partition problem. Eur. J. Oper. Res. 242, 769–777 (2015)
Blum, C., Vallès, M.Y., Blesa, M.J.: An ant colony optimization algorithm for dna sequencing by hybridization. Comput. Oper. Res. 35(11), 3620–3635 (2008)
Chen, X., Zheng, J., Fu, Z., Nan, P., Zhong, Y., Lonardi, S., Jiang, T.: Assignment of orthologous genes via genome rearrangement. IEEE/ACM Trans. Comput. Biol. Bioinform. 2(4), 302–315 (2005)
Chrobak, M., Kolman, P., Sgall, J.: The greedy algorithm for the minimum common string partition problem. ACM Trans. Algorithms 1(2), 350–366 (2005)
Damaschke, P.: Minimum common string partition parameterized. In: Crandall, K., Lagergren, J. (eds.) Algorithms in Bioinformatics. Lecture Notes in Computer Science, vol. 5251, pp. 87–98. Springer, Berlin (2008)
Dorigo, M.: Optimization, learning and natural algorithms. PhD thesis, Politecnico di Milano, Milan (1992)
Dorigo, M., Colorni, A., Maniezzo, V.: Positive feedback as a search strategy. Technical report 91-016, Dipartimento di Elettronica, Politecnico di Milano, Milan (1991)
Dorigo, M., Di Caro, G., Gambardella, L.M.: Ant algorithms for discrete optimization. Artif. Life 5(2), 137–172 (1999)
Dorigo, M., Gambardella, L.M.: Ant colony system: a cooperative learning approach to the traveling salesman problem. Trans. Evol. Comput. 1(1), 53–66 (1997)
Dorigo, M., Maniezzo, V., Colorni, A.: The ant system: optimization by a colony of cooperating agents. IEEE Trans. Syst. Man Cybern. B 26(1), 29–41 (1996)
Dorigo, M., Stützle, T.: Ant Colony Optimization. Bradford Company, Scituate (2004)
Dorigo, M., Stützle, T.: Ant colony optimization: overview and recent advances. In: Gendreau, M., Potvin, J.-Y. (eds.) Handbook of Metaheuristics. International Series in Operations Research & Management Science, vol. 146, pp. 227–263. Springer, New York (2010)
Ferdous, S., Das, A., Rahman, M., Rahman, M.: Ant colony optimization approach to solve the minimum string cover problem. In: International Conference on Informatics, Electronics and Vision (ICIEV), pp. 741–746. IEEE (2012)
Ferdous, S., Rahman, M.: Solving the minimum common string partition problem with the help of ants. In: Tan, Y., Shi, Y., Mo, H. (eds.) Advances in Swarm Intelligence. Lecture Notes in Computer Science, vol. 7928, pp. 306–313. Springer, Berlin (2013)
Ferdous, S.M., Rahman, M.S.: An integer programming formulation of the minimum common string partition problem. PLoS ONE 10, e0130266 (2015)
Gambardella, L., Dorigo, M.: Ant-q: a reinforcement learning approach to the traveling salesman problem, pp. 252–260. Morgan Kaufmann, Los Altos (1995)
Goldstein, A., Kolman, P., Zheng, J.: Minimum common string partitioning problem: hardness and approximations. Electron. J. Comb. 12(R50) (2005)
Jiang, H., Zhu, B., Zhu, D., Zhu, H.: Minimum common string partition revisited. In: Proceedings of the 4th International Conference on Frontiers in Algorithmics, FAW’10, pp. 45–52. Springer, Berlin (2010)
Shyu, S.J., Tsai, C.-Y.: Finding the longest common subsequence for multiple biological sequences by ant colony optimization. Comput. Oper. Res. 36(1), 73–91 (2009)
Stothard, P.: The sequence manipulation suite: Javascript programs for analyzing and formatting protein and DNA sequences. Biotechniques 28(6), 1102 (2000)
Stützle, T., Hoos, H.: Improving the ant system: a detailed report on the max–min ant system. Technical report (1996)
Stützle, T., Hoos, H.: Max–min ant system and local search for the traveling salesman problem. In: IEEE International Conference on Evolutionary Computation (ICEC’97), pp. 309–314. IEEE Press (1997)
Stützle, T., Hoos, H.H.: Max–min ant system. Future Gener. Comput. Syst. 16(9), 889–914 (2000)
Villesen, P.: Fabox: an online FASTA sequence toolbox (2007)
Watterson, G., Ewens, W., Hall, T., Morgan, A.: The chromosome inversion problem. J. Theor. Biol. 99(1), 1–7 (1982)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Ferdous, S.M., Rahman, M.S. Solving the Minimum Common String Partition Problem with the Help of Ants. Math.Comput.Sci. 11, 233–249 (2017). http://doi.org/10.1007/s11786-017-0293-5
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: http://doi.org/10.1007/s11786-017-0293-5