Title: A motif extraction algorithm based on hashing and modulo-4 arithmetic

Authors: Huitao Sheng, Kishan Mehrotra, Chilukuri Mohan, Ramesh Raina

Addresses: Department of Electrical Engineering and Computer Science, Syracuse University, Syracuse, NY 13244, USA. ' Department of Electrical Engineering and Computer Science, Syracuse University, Syracuse, NY 13244, USA. ' Department of Electrical Engineering and Computer Science, Syracuse University, Syracuse, NY 13244, USA. ' Department of Biology, Syracuse University, Syracuse, NY 13244, USA

Abstract: We develop an algorithm to identify cis-elements in promoter regions of coregulated genes. This algorithm searches for subsequences of desired length whose frequency of occurrence is relatively high, while accounting for slightly perturbed variants using hash table and modulo arithmetic. Motifs are evaluated using profile matrices and higher-order Markov background model. Simulation results show that our algorithm discovers more motifs present in the test sequences, when compared with two well-known motif-discovery tools (MDScan and AlignACE). The algorithm produces very promising results on real data set; the output of the algorithm contained many known motifs.

Keywords: cis-elements; motif extraction; gene expression; gene regulation; functional genomics; coregulated genes; simulation; hashing; motif discovery.

DOI: 10.1504/IJCBDD.2008.020209

International Journal of Computational Biology and Drug Design, 2008 Vol.1 No.2, pp.185 - 199

Published online: 08 Sep 2008 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article