TY - GEN
T1 - Longest common subsequence in k length substrings
AU - Benson, Gary
AU - Levy, Avivit
AU - Shalom, B. Riva
PY - 2013
Y1 - 2013
N2 - 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(n2) 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(n2) space is needed.
AB - 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(n2) 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(n2) space is needed.
KW - Dynamic Programming
KW - Longest Common Subsequence
KW - Similarity of strings
UR - http://www.scopus.com/inward/record.url?scp=84886418823&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-41062-8_26
DO - 10.1007/978-3-642-41062-8_26
M3 - Conference contribution
AN - SCOPUS:84886418823
SN - 9783642410611
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 257
EP - 265
BT - Similarity Search and Applications - 6th International Conference, SISAP 2013, Proceedings
T2 - 6th International Conference on Similarity Search and Applications, SISAP 2013
Y2 - 2 October 2013 through 4 October 2013
ER -