An improved algorithm for the longest common subsequence problem

Seyed Rasoul Mousavi, Farzaneh Tabataba

Research output: Contribution to journalArticle

21 Citations (Scopus)

Abstract

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
Volume39
Issue number3
DOIs
Publication statusPublished - Mar 2012

Keywords

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

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

  • Cite this