Space and Time Efficient Algorithms for Planted Motif Search

Abstract. We consider the (l, d) Planted Motif Search Problem, a prob-lem that arises from the need to find transcription factor-binding sites in genomic information. We propose the algorithms PMSi and PMSP which are based on ideas considered in PMS1 [6]. These algorithms are exact, make use of less space than the known exact algorithms such as PMS and are able to tackle instances with large values of d. In particular algorithm PMSP is able to solve the challenge instance (17, 6), which has not reported solved before in the literature.