Towards a Better Algorithm for Discovering the Transcription Factor Binding Sites in the DNA Sequences

Discovering Transcription Factor Binding Sites (TFBSs) or Motifs in DNA sequences is a challenging problem in both computer science and molecular biology. Discovering such motifs is very important to treat diseases. Many techniques were proposed to solve this problem. All these techniques did not solve the problem accurately and efficiently. The main reason behind this problem is the misunderstanding of the regulatory mechanisms, and the mutations that may occur for the motif occurrences. Computationally this problem is NP-complete problem which means hard for all practical purposes. We developed a linear algorithm to discover the string motifs in the DNA sequences with all possible lengths automatically where the previous algorithm was quadratic. Our linear algorithm is very fast and can manipulate very large sequences in few minutes. We also adapted our linear algorithm to discover motifs with mismatches. We benchmarked our algorithm on Sandve et al. suites where it achieved higher accuracy to detect real motifs. We also proposed new significant motifs for Mycobacterium tuberculosis, unreported by other works