Efficient sequential and parallel algorithms for planted motif search.
BACKGROUND
Motif searching is an important step in the detection of rare events occurring in a set of DNA or protein sequences. One formulation of the problem is known as (l,d)-motif search or Planted Motif Search (PMS). In PMS we are given two integers l and d and n biological sequences. We want to find all sequences of length l that appear in each of the input sequences with at most d mismatches. The PMS problem is NP-complete. PMS algorithms are typically evaluated on certain instances considered challenging. Despite ample research in the area, a considerable performance gap exists because many state of the art algorithms have large runtimes even for moderately challenging instances.


RESULTS
This paper presents a fast exact parallel PMS algorithm called PMS8. PMS8 is the first algorithm to solve the challenging (l,d) instances (25,10) and (26,11). PMS8 is also efficient on instances with larger l and d such as (50,21). We include a comparison of PMS8 with several state of the art algorithms on multiple problem instances. This paper also presents necessary and sufficient conditions for 3 l-mers to have a common d-neighbor. The program is freely available at http://engr.uconn.edu/~man09004/PMS8/.


CONCLUSIONS
We present PMS8, an efficient exact algorithm for Planted Motif Search. PMS8 introduces novel ideas for generating common neighborhoods. We have also implemented a parallel version for this algorithm. PMS8 can solve instances not solved by any previous algorithms.
Department of Computer Science and Engineering, University of Connecticut, Storrs, CT, USA. marius.nicolae@engr.uconn.edu.
Marius
M
Nicolae
Sanguthevar
S
Rajasekaran
D000465:Algorithms; D019295:Computational Biology / Q000379:methods*; D004247:DNA / Q000737:chemistry / Q000235:genetics; D011506:Proteins / Q000737:chemistry / Q000235:genetics; D017422:Sequence Analysis, DNA / Q000379:methods*; D020539:Sequence Analysis, Protein / Q000379:methods*; D012984:Software
D011506:Proteins; D004247:DNA