ET-Motif: Solving the Exact (l, d)-Planted Motif Problem Using Error Tree Structure
Anas Al-okaily, Chun-Hsi Huang · Journal of Computational Biology · 2016
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 $$\Sigma$$, 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 $$\le d$$ of m. In this article, we propose ET-Motif, an algorithm that can solve the PMS problem in $$O \left( {n{m^2} \sum olimits_{j = 0}^d \left( {l \atop j } \right) } \right)$$ time and $$O \left( {nml} \right)$$ space. The time bound can be further reduced by a factor of m with $$O \left( {m \sum olimits_{j = 0}^d \left( {{ l \atop j} } \right) {{ \left( { \Sigma - 1} \right) }^j}} \right)$$ space. In case the suffix tree that is built for the input sequences is balanced, the problem can be solved in $$O \left( {n{m^2} \sum olimits_{j = 0}^d \left( {{ {lo{g_ \Sigma }nm} \atop j} } \right) } \right)$$ time and $$O \left( {nml} \right)$$ space. Similarly, the time bound can be reduced by a factor of m using $$O \left( {m \sum olimits_{j = 0}^d \left( { { l\atop j} } \right) {{ \left( { \Sigma - 1} \right) }^j}} \right)$$ 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 $${O ( {{ \rm{3}}^d} ) }$$, while for edited PMS the increase will be of $${ ( n - q + { \rm{1}} ) }$$ in the time bound.