OAMD: OPTIMIZED APPROACH FOR MOTIF DETECTION IN DNA SEQUENCES

Abstract

Discovering approximate repeated patterns, or motifs, in genomic sequences is an important problem in computational molecular biology. Motif finding applications arise when identifying shared regulatory signals within DNA sequences or shared functional and structural elements within protein sequences. In this dissertation work, a combined approach program named OAMD (Optimized Approach for Motif Detection in DNA sequences) is presented. The proposed algorithm works for planted (L, d)-motif problem and takes advantage of both pattern driven algorithms (highly accurate) and sample driven algorithms (less time consuming). The key concept is to get expected motifs (patterns) as early as possible and then confirm their validity. The complete OAMD algorithm encompasses three different phases: (1) Segregation and format conversion, (2) Expected motif generation, and (3) motif confirmation. The expected motif generation phase is based on pattern driven approach but it is highly efficient than many existing pattern driven algorithms. Motif confirmation phase is based on sample driven approach, which enables to detect motif faster without loss of the accuracy. Application of our algorithm to several DNA datasets shows that it performs very well, identifying either known motifs or motifs of high conservation. The key advantages of our algorithm are its consistent performance with increase in the number of sequences increases, less memory requirements, good accuracy and lesser computational than existing algorithms