Sequence Classification via LCS

Computing a longest common subsequence of two given sequences is a fundamental problem in several fields of computer science. While there exist dynamic programming algorithms that can solve the problem in polynomial-time, their running time is considered too high for some practical applications. In this contribution we propose a method for comparing two sequences that is based on (1) a combinatorial algorithm that computes a window constrained longest common subsequence and (2) a genetic algorithm. We present experiments on synthetic datasets that show that the method is able to return solutions close to the length of a longest compute common subsequence. Moreover, the method is faster than the dynamic programming algorithm for the longest common subsequence problem.