Article ID Journal Published Year Pages File Type
428927 Information Processing Letters 2014 5 Pages PDF
Abstract

•Four new algorithms for the longest common subsequence in k-length substrings.•Non-trivial adaptation of the approaches known for the LCS problem.•Application in similarity of biological sequences.

Finding the longest common subsequence in k-length substrings (LCSk) is a recently proposed problem motivated by computational biology. This is a generalization of the well-known LCS problem in which matching symbols from two sequences A and B are replaced with matching non-overlapping substrings of length k from A and B. We propose several algorithms for LCSk, being non-trivial incarnations of the major concepts known from LCS research (dynamic programming, sparse dynamic programming, tabulation). Our algorithms make use of a linear-time and linear-space preprocessing finding the occurrences of all the substrings of length k from one sequence in the other sequence.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, ,