EFFICIENT DIGITAL SIGNAL PROCESSING BASED ALGORITHM FOR GENOMIC PROBLEM

Abstract

In our work, we introduce a digital signal processing (DSP) based approach for motif finding problem. We design a correlation based mathematical model, referred as DACalculator, to detect unknown motif in a given set of DNA sequences. We use divide and conquer policy to solve motif problem in m2N2 time-complexity; where m is the total number of DNA sequences present in a given set and N is the average length of the DNA sequences. Our method can efficiently detect both exact and inexact motifs in DNA sequences. The algorithm yields all the best motifs in one pass as compared to multiple passes required in Gibbs sampling algorithm. The output file includes all the binding sites corresponding to the motif. The complete algorithm encompasses three different phases: 1) segregation and format conversion, 2) correlation calculation using DACalculator, and 3) clustering. The cluster that exhibits maximum consensus score is declared as the motif of the DNA set. For convenience, we define motifs in terms of a canonical sequence and a set of sequences that have a small number of differences compared to the canonical sequence. Such motifs are referred to as (1, d)-motifs where 1 is the length of the motif and d indicates how many mismatches are allowed between an instance of the motif and the canonical motif sequence. Experiments are performed over G-Box & E-coli dataset, and over a set of random sequences. The accuracy of the algorithm is validated with the help of experimental results. iii