title: ET-Motif: Solving the Exact (l, d)-Planted Motif Problem Using Error Tree Structure.
abstract: Motif finding is an important and a challenging problem in many biological applications such as discovering promoters, enhancers, locus control regions, transcription factors, and more. The (l, d)-planted motif search, PMS, is one of several variations of the problem. In this problem, there are n given sequences over alphabets of size [Formula: see text], each of length m, and two given integers l and d. The problem is to find a motif m of length l, where in each sequence there is at least an l-mer at a Hamming distance of [Formula: see text] of m. In this article, we propose ET-Motif, an algorithm that can solve the PMS problem in [Formula: see text] time and [Formula: see text] space. The time bound can be further reduced by a factor of m with [Formula: see text] space. In case the suffix tree that is built for the input sequences is balanced, the problem can be solved in [Formula: see text] time and [Formula: see text] space. Similarly, the time bound can be reduced by a factor of m using [Formula: see text] space. Moreover, the variations of the problem, namely the edit distance PMS and edited PMS (Quorum), can be solved using ET-Motif with simple modifications but upper bands of space and time. For edit distance PMS, the time and space bounds will be increased by [Formula: see text], while for edited PMS the increase will be of [Formula: see text] in the time bound.
authors.affiliation: Computer Science & Engineering Department, University of Connecticut , Storrs, Connecticut.
authors.forename: Anas
authors.initials: A
authors.lastname: Al-Okaily
authors.affiliation: Computer Science & Engineering Department, University of Connecticut , Storrs, Connecticut.
authors.forename: Chun-Hsi
authors.initials: CH
authors.lastname: Huang
mesh_terms: D000465:Algorithms; D019295:Computational Biology / Q000379:methods; D017422:Sequence Analysis, DNA / Q000379:methods*
keywords: common neighbor.; genome informatics; motif search