HAMMER Algorithm: Hashing with Arithmetic Modulo-4 for Motif Extraction of Regulatory Elements

摘要

A new algorithm, HAMMER, discovers cis-elements in promoter regions of the co-regulated genes. We show that HAMMER is faster and more accurate than well-known tools currently in use to identify cis-elements. Given input sequences that represent promoter regions of genes, this algorithm searches for subsequences of desired length w whose frequency of occurrence is relatively high, while accounting for slightly corrupted variants (with up to d substitutions). Various w-mers are numerically encoded and represented in a hash table, and d-neighbors are efficiently discovered using a modulo-4 arithmetic operation. Profile matrices are constructed and evaluated using a high-order Markov model based on background data (from a gene database). HAMMER discovers the most frequently occurring w-mers (permitting corruption in at most d positions). Experiment results show that HAMMER is significantly faster and discovers more motifs present in the test sequences, when compared with two well-known motif-discovery tools (MDScan and AlignACE).