Finding Motifs Based on Suffix Trie
Fatemeh Zare‐Mirakabad, Pooya Davoodi, H. Ahrabian, Abbas Nowzari-Dalini, M. Sadeghi, Bahram Goliaei · 2009
Pattern discovery or motif finding is one of the most challenging problems in both molecular biology and computer science. In this paper we present an exact exhaustive method, for finding motifs of length l in a set of t sequences of length n with a limited number of mutations d. The algorithm is based on the Depth First Search on a suffix trie with maximum nodesO(tn) and is performed in O(t 2 n 2 l 2 ) time complexity. The proposed algorithm is tested on yeast and human transcription factor binding site data sets and the obtained results are compared to the other well-known algorithms. The experimental results demonstrate that the proposed method is working analogous to them algorithms.