Abstract
In this paper we propose a Beam-ACO approach for a combinatorial optimization problem known as the repetition-free longest common subsequence problem. Given two input sequences \(x\) and \(y\) over a finite alphabet \(\varSigma \), this problem concerns to find a longest common subsequence of \(x\) and \(y\) in which no letter is repeated. Beam-ACO algorithms are combinations between the metaheuristic ant colony optimization and a deterministic tree search technique called beam search. The algorithm that we present is an adaptation of a previously published Beam-ACO algorithm for the classical longest common subsequence problem. The results of the proposed algorithm outperform existing heuristics from the literature.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Adi, S.S., Braga, M.D.V., Fernandes, C.G., Ferreira, C.E., Martinez, F.V., Sagot, M.F., Stefanes, M.A., Tjandraatmadja, C., Wakabayashi, Y.: Repetition-free longest common subsquence. Disc. Appl. Math. 158, 1315–1324 (2010)
Aho, A., Hopcroft, J., Ullman, J.: Data structures and algorithms. Addison-Wesley, Reading (1983)
Blum, C.: Beam-ACO for the longest common subsequence problem. In: Fogel, G., et al. (eds.) Proceedings of CEC 2010 - Congress on Evolutionary Computation, vol. 2. IEEE Press, Piscataway (2010)
Blum, C., Dorigo, M.: The hyper-cube framework for ant colony optimization. IEEE Trans. Man Syst. Cybern. - Part B 34(2), 1161–1172 (2004)
Bonizzoni, P., Della Vedova, G.: Variants of constrained longest common subsequence. Inf. Process. Lett. 110(20), 877–881 (2010)
Easton, T., Singireddy, A.: A large neighborhood search heuristic for the longest common subsequence problem. J. Heuristics 14(3), 271–283 (2008)
Gusfield, D.: Algorithms on Strings, Trees, and Sequences. Computer Science and Computational Biology, Cambridge University Press, Cambridge (1997)
Jiang, T., Lin, G., Ma, B., Zhang, K.: A general edit distance between RNA structures. J. Comput. Biol. 9(2), 371–388 (2002)
Julstrom, B.A., Hinkemeyer, B.: Starting from scratch: growing longest common subsequences with evolution. In: Runarsson, T.P., Beyer, H.-G., Burke, E.K., Merelo-Guervós, J.J., Whitley, L.D., Yao, X. (eds.) PPSN 2006. LNCS, vol. 4193, pp. 930–938. Springer, Heidelberg (2006)
Maier, D.: The complexity of some problems on subsequences and supersequences. J. ACM 25, 322–336 (1978)
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)
Smith, T., Waterman, M.: Identification of common molecular subsequences. J. Mol. Biol. 147(1), 195–197 (1981)
Storer, J.: Data Compression: Methods and Theory. Computer Science Press, Rockville (1988)
Acknowledgments
This work was supported by grants TIN2012-37930, TIN2010-14931 and TIN2007-66523 of the Spanish Government, and project 2009-SGR1137 of the Generalitat de Catalunya. In addition, support is acknowledged from IKERBASQUE (Basque Foundation for Science) and the Basque Saiotek and Research Groups 2013-2018 (IT-609-13) programs.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Blum, C., Blesa, M.J., Calvo, B. (2014). Beam-ACO for the Repetition-Free Longest Common Subsequence Problem. In: Legrand, P., Corsini, MM., Hao, JK., Monmarché, N., Lutton, E., Schoenauer, M. (eds) Artificial Evolution. EA 2013. Lecture Notes in Computer Science(), vol 8752. Springer, Cham. https://doi.org/10.1007/978-3-319-11683-9_7
Download citation
DOI: https://doi.org/10.1007/978-3-319-11683-9_7
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-11682-2
Online ISBN: 978-3-319-11683-9
eBook Packages: Computer ScienceComputer Science (R0)