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.