Finding Regulatory Motifs of Genetic Networks Using Cut-Sort Algorithm

Understanding the targets of regulatory genes has become a challenging problem for bioinformaticians and biologists in systems biology. the main issue in solving this challenge consists in finding motifs that are finding short, recurring patterns in dna or in amino-acid sequences that presumably have a regulatory function. a motif is considered a signature for a protein family binding to sequence motifs in the genome. the major challenge in finding motifs arises from the fact that most of the time the motifs are not well conserved. to discover such degenerate motifs, aligning multiple sequence motifs becomes a challenge. usually, a motif discovery algorithm uses some prior information about the motifs to be discovered. in this paper, we present a novel algorithm for finding conserved sequence motifs in dna without having a priori knowledge about the motifs. however, the algorithm can be used for motifs sequence both in dna and in proteins. our algorithm mainly depends on cutting sequences that have conserved motifs into equal fragments, sorting the fragments and then extending in both fragment directions. the algorithm runs in a very short time period. it takes 5.5 seconds for a real data sequence with length n = 28,000 nucleotides to find its identical, degenerate, long and short motifs; it can be easily parallelized by implementing it on general purpose graphical processing units. the algorithm guarantees to find any globally optimal solution within a short time even for sequences with very long motifs.