Prague Stringology Conference 2018
Filip Pavetić, Ivan Katanić, Gustav Matula, Goran Žužić and Mile Šikić
Fast and Simple Algorithms for Computing both LCSk and LCSk+
| Abstract: |
| Longest Common Subsequence (LCS) deals with the problem of measuring similarity of two strings. While this problem has been analyzed for decades, the recent interest stems from a practical observation that considering single characters is often too simplistic. Therefore, recent works introduce the variants of LCS based on shared substrings of length exactly or at least k (LCSK and LCSKP respectively). The main drawback of the state-of-the-art algorithms for computing LCSK and LCSKP is that they work well only in a limited setting: they either solve the average case well while being suboptimal in the pathological situations or they achieve a good worst-case performance, but fail to exploit the input data properties to speed up the computation. Furthermore, these algorithms are based on non-trivial data structures which is not ideal from a practitioner's point of view. We present a single algorithm to compute both LCSK and LCSKP which outperforms the state-of-the art algorithms in terms of runtime complexity and requires only basic data structures. In addition, we implement an algorithm to reconstruct the solution which offers significant improvement in terms of memory consumption. Our empirical validation shows that we save several orders of magnitude of memory on human genome data. The C++ implementation of our algorithms. |
| Download paper: |  |
 |
 |
| PostScript | BibTeX reference |