Discovering Motifs in DNA Sequences: A Candidate Motifs Based Approach

摘要

Motif finding is a classical combinatorial problem in the domain of bioinformatics. Motifs are the small set of immunity gene present in the DNA sequences as a binding site and turn on whenever the organism gets infected. Hence, to identify these motifs for transcription factors is of great biological importance. Recently, this field of bio-informatics has grown significantly and many algorithms have been proposed to solve this problem. However, high complexity is the most challenging aspect of this problem which still grabs the attention of many researchers. This paper presents a proficient algorithm that extracts binding sites in a set of DNA sequences for transcription factors using some operations on the DNA sequences. The motif we work on is of known length, un-gapped and non-mutated. The proposed algorithm does some preprocessing and formulates an adjacency list for finding such sites. Although any two randomly selected sequences can be used for preprocessing, we have used first two sequences as a base for constructing the adjacency lists which is later used for fast detection of common l-mers from both of them. These l-mers are considered as candidate motifs and then checked for its existence in all of the remaining DNA sequences using a sliding window approach. The proposed algorithm CMMF is experimentally validated on millions of DNA sequences. Additionally, the formulation of motif finding algorithm is also applicable to related problems in the field of data mining, pattern detection, etc.