title: Efficient algorithms for biological stems search.
abstract: BACKGROUND
  Motifs are significant patterns in DNA, RNA, and protein sequences, which play an important role in biological processes and functions, like identification of open reading frames, RNA transcription, protein binding, etc. Several versions of the motif search problem have been studied in the literature. One such version is called the Planted Motif Search (PMS)or (l, d)-motif Search. PMS is known to be NP complete. The time complexities of most of the planted motif search algorithms depend exponentially on the alphabet size. Recently a new version of the motif search problem has been introduced by Kuksa and Pavlovic. We call this version as the Motif Stems Search (MSS) problem. A motif stem is an l-mer (for some relevant value of l)with some wildcard characters and hence corresponds to a set of l-mers (without wildcards), some of which are (l, d)-motifs. Kuksa and Pavlovic have presented an efficient algorithm to find motif stems for inputs from large alphabets. Ideally, the number of stems output should be as small as possible since the stems form a superset of the motifs.
  
  
  RESULTS
  In this paper we propose an efficient algorithm for MSS and evaluate it on both synthetic and real data. This evaluation reveals that our algorithm is much faster than Kuksa and Pavlovic's algorithm.
  
  
  CONCLUSIONS
  Our MSS algorithm outperforms the algorithm of Kuksa and Pavlovic in terms of the run time as well as the number of stems output. Specifically, the stems output by our algorithm form a proper (and much smaller)subset of the stems output by Kuksa and Pavlovic's algorithm.
authors.affiliation: Department of Computer Science and Engineering, University of Connecticut, Storrs, CT, USA. rajasek@engr.uconn.edu
authors.forename: Tian
authors.initials: T
authors.lastname: Mi
authors.forename: Sanguthevar
authors.initials: S
authors.lastname: Rajasekaran
mesh_terms: D000465:Algorithms; D020816:Amino Acid Motifs; D004247:DNA / Q000737:chemistry; D059372:Nucleotide Motifs; D012313:RNA / Q000737:chemistry; D017422:Sequence Analysis, DNA; D020539:Sequence Analysis, Protein
chemical_list: D012313:RNA; D004247:DNA