An improved algorithm for the longest common subsequence problem

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 solution...

Full description

Saved in:
Bibliographic Details
Published in:Computers & operations research 2012-03, Vol.39 (3), p.512-520
Main Authors: Mousavi, Sayyed Rasoul, Tabataba, Farzaneh
Format: Article
Language:English
Subjects:
Algorithmics. Computability. Computer arithmetics
Algorithms
Applied sciences
Approximation
Beam search
Bioinformatics
Biological and medical sciences
Computer science
control theory
systems
Data compression
Dynamic programming
Exact sciences and technology
Exact solutions
Fundamental and applied biological sciences. Psychology
General aspects
Heuristic
Heuristic function
LCS
Longest common subsequence
Mathematical analysis
Mathematical models
Mathematical programming
Mathematics in biology. Statistical analysis. Models. Metrology. Data processing in biology (general aspects)
Operational research and scientific management
Operational research. Management science
Optimization
Optimization algorithms
Search methods
State of the art
Strings
Studies
Theoretical computing
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0305-0548
1873-765X
0305-0548
DOI:10.1016/j.cor.2011.02.026