HAMMER algorithm: Hashing with arithmetic modulo-4 for motif extraction of regulatory elements

Huitao Sheng, Kishan Mehrotra, Chilukuri Mohan, Ramesh Raina

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Scopus citations

Abstract

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).

Original languageEnglish (US)
Title of host publicationProceedings of the 7th IEEE International Conference on Bioinformatics and Bioengineering, BIBE
Pages753-758
Number of pages6
DOIs
StatePublished - Dec 1 2007
Event7th IEEE International Conference on Bioinformatics and Bioengineering, BIBE - Boston, MA, United States
Duration: Jan 14 2007Jan 17 2007

Publication series

NameProceedings of the 7th IEEE International Conference on Bioinformatics and Bioengineering, BIBE

Other

Other7th IEEE International Conference on Bioinformatics and Bioengineering, BIBE
CountryUnited States
CityBoston, MA
Period1/14/071/17/07

ASJC Scopus subject areas

  • Biotechnology
  • Genetics
  • Bioengineering

Fingerprint Dive into the research topics of 'HAMMER algorithm: Hashing with arithmetic modulo-4 for motif extraction of regulatory elements'. Together they form a unique fingerprint.

  • Cite this

    Sheng, H., Mehrotra, K., Mohan, C., & Raina, R. (2007). HAMMER algorithm: Hashing with arithmetic modulo-4 for motif extraction of regulatory elements. In Proceedings of the 7th IEEE International Conference on Bioinformatics and Bioengineering, BIBE (pp. 753-758). [4375645] (Proceedings of the 7th IEEE International Conference on Bioinformatics and Bioengineering, BIBE). https://doi.org/10.1109/BIBE.2007.4375645