A parallel multistart algorithm for the closest string problem

In this paper we describe and implement a parallel algorithm to find approximate solutions for the Closest String Problem (CSP). The CSP, also known as Motif Finding problem, has applications in Coding Theory and Computational Biology. The CSP is NP-hard which motivates us to think about heuristics...

Full description

Saved in:
Bibliographic Details
Published in:Computers & operations research 2008-11, Vol.35 (11), p.3636-3643
Main Authors: Gomes, Fernando C., Meneses, Cláudio N., Pardalos, Panos M., Viana, Gerardo Valdisio R.
Format: Article
Language:English
Subjects:
Algorithmics. Computability. Computer arithmetics
Algorithms
Applied sciences
Approximation
Biological and medical sciences
Closest String Problem
Computer science
control theory
systems
Exact sciences and technology
Fundamental and applied biological sciences. Psychology
General aspects
Heuristic
Integer programming
Mathematics in biology. Statistical analysis. Models. Metrology. Data processing in biology (general aspects)
Parallel algorithms
Problem solving
Sequence analysis
Solutions
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:In this paper we describe and implement a parallel algorithm to find approximate solutions for the Closest String Problem (CSP). The CSP, also known as Motif Finding problem, has applications in Coding Theory and Computational Biology. The CSP is NP-hard which motivates us to think about heuristics to solve large instances. Several approximation algorithms have been designed for the CSP, but all of them have a poor performance guarantee. Recently some researchers have shown empirically that integer programming techniques can be successfully used to solve moderate-size instances (10–30 strings each of which is 300–800 characters long) of the CSP. However, real-world instances are larger than those tested. In this paper we show how a simple heuristic can be used to find near-optimal solutions to that problem. We implemented a parallel version of this heuristic and report computational experiments on large-scale instances. These results show the effectiveness of our approach.
ISSN:0305-0548
1873-765X
0305-0548
DOI:10.1016/j.cor.2007.04.002