Abstract
In this paper we define a new problem, motivated by computational biology, LCSk aiming at finding the maximal number of k length substrings, matching in both input string while preserving their order of appearance in the input strings. The traditional LCS definition is a spacial case of our problem, where k = 1. We provide an algorithm, solving the general case in O(n 2) time, where n is the length of the input, equaling the time required for the special case of k = 1. The space requirement is O(kn). In order to enable backtracking of the solution O(n 2) space is needed.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Allison, L., Dix, T.I.: A bit-string Longest-Common-Subsequence. Information Processing Letters 23(5), 305–310 (1986)
Amir, A., Gotthilf, Z., Shalom, R.: Weighted LCS. J. Discrete Algorithms 8(3), 273–281 (2010)
Amir, A., Hartman, T., Kapah, O., Shalom, R., Tsur, D.: Generalized LCS. Theor. Comput. Sci. 409(3), 438–449 (2008)
Apostolico, A., Landau, G.M., Skiena, S.: Matching for run-length encoded strings. Journal of Complexity 15(1), 4–16 (1999)
Benson, G., Hernandez, Y., Loving, J.: A bit-parallel, general integer-scoring sequence alignment algorithm. In: Fischer, J., Sanders, P. (eds.) CPM 2013. LNCS, vol. 7922, pp. 50–61. Springer, Heidelberg (2013)
Bergroth, L., Hakonen, H., Raita, T.: A survey of longest common subsequence algorithms. In: Proc, 7th Symposium on String Processing and Information Retrieval (SPIRE), pp. 39–48 (2000)
Blin, G., Jiang, M., Vialette, S.: The Longest Common Subsequence Problem with Crossing-Free Arc-Annotated Sequences. In: Calderón-Benavides, L., González-Caro, C., Chávez, E., Ziviani, N. (eds.) SPIRE 2012. LNCS, vol. 7608, pp. 130–142. Springer, Heidelberg (2012)
Chen, Y.C., Chao: On the generalized constrained longest common subsequence problems. Journal of Combinatorial Optimization 21(3), 383–392 (2011)
Crochemore, M., Iliopoulos, C.S., Pinzon, Y.J., Reid, J.F.: A fast and practical bit-vector algorithm forthe longest common subsequence problem. Information Processing Letters 80(6), 279–285 (2001)
Gotthilf, Z., Hermelin, D., Landau, G.M., Lewenstein, M.: Restricted LCS. In: Chavez, E., Lonardi, S. (eds.) SPIRE 2010. LNCS, vol. 6393, pp. 250–257. Springer, Heidelberg (2010)
Hyyro, H.: Bit parallel LCS- length computation revisited. In: Proc. 15th Australasian Workshop on Combinatorial Algorithms, AWOCA (2004)
Landau, G.M., Levy, A., Newman, I.: LCS approximation via embedding into locally non-repetitive strings. Inf. Comput. 209(4), 705–716 (2011)
Landau, G.M., Myers, E.W., Ziv-Ukelson, M.: Two Algorithms for LCS Consecutive Suffix Alignment. In: Sahinalp, S.C., Muthukrishnan, S.M., Dogrusoz, U. (eds.) CPM 2004. LNCS, vol. 3109, pp. 173–193. Springer, Heidelberg (2004)
Landau, G.M., Schieber, B., Ziv-Ukelson, M.: Sparse LCS Common Substring Alignment. In: Baeza-Yates, R., Chávez, E., Crochemore, M. (eds.) CPM 2003. LNCS, vol. 2676, pp. 225–236. Springer, Heidelberg (2003)
Landau, G.M., Ziv-Ukelson, M.: On the Common Substring Alignment Problem. J. Algorithms 41(2), 338–359 (2001)
Hirschberg, D.S.: A Linear space algorithm for Computing Maximal Common Subsequences. Commun. ACM 18(6), 341–343 (1975)
Tsai, Y.T.: The constrained longest common subsequence problem. Information Processing Letters 88(4), 173–176 (2003)
Wagner, R.A., Fischer, M.J.: The string-to-string correction problem. J. ACM 21, 168–173 (1974)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Benson, G., Levy, A., Shalom, B.R. (2013). Longest Common Subsequence in k Length Substrings. In: Brisaboa, N., Pedreira, O., Zezula, P. (eds) Similarity Search and Applications. SISAP 2013. Lecture Notes in Computer Science, vol 8199. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-41062-8_26
Download citation
DOI: https://doi.org/10.1007/978-3-642-41062-8_26
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-41061-1
Online ISBN: 978-3-642-41062-8
eBook Packages: Computer ScienceComputer Science (R0)