An improved algorithm for the longest common subsequence problem

Seyed Rasoul Mousavi, Farzaneh Tabataba

    Research output: Contribution to journalArticlepeer-review

    30 Citations (Scopus)


    The Longest Common Subsequence problem seeks a longest subsequence of every member of a given set of strings. It has applications, among others, in data compression, FPGA circuit minimization, and bioinformatics. The problem is NP-hard for more than two input strings, and the existing exact solutions are impractical for large input sizes. Therefore, several approximation and (meta) heuristic algorithms have been proposed which aim at finding good, but not necessarily optimal, solutions to the problem. In this paper, we propose a new algorithm based on the constructive beam search method. We have devised a novel heuristic, inspired by the probability theory, intended for domains where the input strings are assumed to be independent. Special data structures and dynamic programming methods are developed to reduce the time complexity of the algorithm. The proposed algorithm is compared with the state-of-the-art over several standard benchmarks including random and real biological sequences. Extensive experimental results show that the proposed algorithm outperforms the state-of-the-art by giving higher quality solutions with less computation time for most of the experimental cases.
    Original languageEnglish
    Pages (from-to)512-520
    Number of pages9
    JournalComputers & Operations Research
    Issue number3
    Publication statusPublished - Mar 2012


    • Longest common subsequence
    • LCS
    • Beam search
    • Heuristic function
    • Algorithms
    • Bioinformatics


    Dive into the research topics of 'An improved algorithm for the longest common subsequence problem'. Together they form a unique fingerprint.

    Cite this