An Identical String Motif Finding Algorithm Through Dynamic Programming

摘要

Gene expression regulation is a major challenge in biology. One aspect of such a challenge is the binding sites in DNA, called motifs. DNA motif finding still poses a great challenge for computer scientists and biologists. As a result, a large number of motif finding algorithms are already implemented. However, literature has proven this task to be complex. The present paper tends to find a solution for the motif finding problem through rearranging data in a manner that can help obtain the targeted motif easily by adopting the dynamic programming concept. It proposes an efficient algorithm called Pattern Position Motif Finding (PPMF), aiming at finding all identical string motifs, which appear in a single sequence or multi sequences at least twice or a specified times. The proposed algorithm is compared with the Encoded Expansion (EE) algorithm to evaluate the execution time and size of processed sequences, PPMF takes less execution time than the corresponding one and processed large size sequences than EE processed. This denotes that when the biologist needs to find the identical string motifs in a big sequence, our proposed algorithm will be the better solution than the EE algorithm.