title: Fast and practical algorithms for planted (l, d) motif search.
abstract: We consider the planted (l, d) motif search problem, which consists of finding a substring of length l that occurs in a set of input sequences {s1, . . . , sn} with up to d errors, a problem that arises from the need to find transcription factor-binding sites in genomic information. We propose a sequence of practical algorithms, which start based on the ideas considered in PMS1. These algorithms are exact, have little space requirements, and are able to tackle challenging instances with bigger d, taking less time in the instances reported solved by exact algorithms. In particular, one of the proposed algorithms, PMSprune, is able to solve the challenging instances, such as (17, 6) and (19, 7), which were not previously reported as solved in the literature.
authors.affiliation: Department of Computer Science and Engineering, University of Connecticut, Storrs, CT 06269-3155, USA. jdavila@engr.uconn.edu
authors.forename: Jaime
authors.initials: J
authors.lastname: Davila
authors.forename: Sudha
authors.initials: S
authors.lastname: Balla
authors.forename: Sanguthevar
authors.initials: S
authors.lastname: Rajasekaran
mesh_terms: D000465:Algorithms; D020816:Amino Acid Motifs; D001665:Binding Sites; D019295:Computational Biology / Q000379:methods*; D015233:Models, Statistical; D008962:Models, Theoretical; D010363:Pattern Recognition, Automated; D011485:Protein Binding; D016415:Sequence Alignment; D014157:Transcription Factors / Q000378:metabolism
chemical_list: D014157:Transcription Factors