title: High-performance exact algorithms for motif search.
abstract: OBJECTIVE
  The human genome project has resulted in the generation of voluminous biological data. Novel computational techniques are called for to extract useful information from this data. One such technique is that of finding patterns that are repeated over many sequences (and possibly over many species). In this paper we study the problem of identifying meaningful patterns (i.e., motifs) from biological data, the motif search problem.
  
  
  METHODS
  The general version of the motif search problem is NP-hard. Numerous algorithms have been proposed in the literature to solve this problem. Many of these algorithms fall under the category of heuristics. We concentrate on exact algorithms in this paper. In particular, we concentrate on two different versions of the motif search problem and offer exact algorithms for them.
  
  
  RESULTS
  In this paper we present algorithms for two versions of the motif search problem. All of our algorithms are elegant and use only such simple data structures as arrays. For the first version of the problem described as Problem 1 in the paper, we present a simple sorting based algorithm, SMS (Simple Motif Search). This algorithm has been coded and experimental results have been obtained. For the second version of the problem (described in the paper as Problem 2), we present two different algorithms--a deterministic algorithm (called DMS) and a randomized algorithm (Monte Carlo algorithm). We also show how these algorithms can be parallelized.
  
  
  CONCLUSIONS
  All the algorithms proposed in this paper are improvements over existing algorithms for these versions of motif search in biological sequence data. The algorithms presented have the potential of performing well in practice.
authors.affiliation: Department of CSE, University of Connecticut, Storrs, CT 06269, USA. rajasek@engr.uconn.edu
authors.forename: Sanguthevar
authors.initials: S
authors.lastname: Rajasekaran
authors.forename: Sudha
authors.initials: S
authors.lastname: Balla
authors.forename: Chun-Hsi
authors.initials: CH
authors.lastname: Huang
authors.forename: Vishal
authors.initials: V
authors.lastname: Thapar
authors.forename: Michael
authors.initials: M
authors.lastname: Gryk
authors.forename: Mark
authors.initials: M
authors.lastname: Maciejewski
authors.forename: Martin
authors.initials: M
authors.lastname: Schiller
mesh_terms: D000465:Algorithms; D020816:Amino Acid Motifs; D019295:Computational Biology; D006801:Humans; D016247:Information Storage and Retrieval; D010363:Pattern Recognition, Automated