CodingMotif: exact determination of overrepresented nucleotide motifs in coding sequences
Open Access
- 14 February 2012
- journal article
- Published by Springer Nature in BMC Bioinformatics
- Vol. 13 (1) , 32
Abstract
Background: It has been increasingly appreciated that coding sequences harbor regulatory sequence motifs in addition to encoding for protein. These sequence motifs are expected to be overrepresented in nucleotide sequences bound by a common protein or small RNA. However, detecting overrepresented motifs has been difficult because of interference by constraints at the protein level. Sampling-based approaches to solve this problem based on codon-shuffling have been limited to exploring only an infinitesimal fraction of the sequence space and by their use of parametric approximations. Results: We present a novel O(N(log N)2)-time algorithm, CodingMotif, to identify nucleotide-level motifs of unusual copy number in protein-coding regions. Using a new dynamic programming algorithm we are able to exhaustively calculate the distribution of the number of occurrences of a motif over all possible coding sequences that encode the same amino acid sequence, given a background model for codon usage and dinucleotide biases. Our method takes advantage of the sparseness of loci where a given motif can occur, greatly speeding up the required convolution calculations. Knowledge of the distribution allows one to assess the exact non-parametric p-value of whether a given motif is over- or under- represented. We demonstrate that our method identifies known functional motifs more accurately than sampling and parametric-based approaches in a variety of coding datasets of various size, including ChIP-seq data for the transcription factors NRSF and GABP. Conclusions: CodingMotif provides a theoretically and empirically-demonstrated advance for the detection of motifs overrepresented in coding sequences. We expect CodingMotif to be useful for identifying motifs in functional genomic datasets such as DNA-protein binding, RNA-protein binding, or microRNA-RNA binding within coding regions. A software implementation is available at http://bioinformatics.bc.edu/chuanglab/codingmotif.tarKeywords
This publication has 34 references indexed in Scilit:
- Diverse RNA-Binding Proteins Interact with Functionally Related Sets of RNAs, Suggesting an Extensive Regulatory SystemPLOS Biology, 2008
- Identification and measurement of neighbor-dependent nucleotide substitution processesBioinformatics, 2005
- Comparative context analysis of codon pairs on an ORFeome scaleGenome Biology, 2005
- Protein length in eukaryotic and prokaryotic proteomesNucleic Acids Research, 2005
- Effect of 3' Terminal Codon Pairs with Different Frequency of Occurrence on the Expression of cat Gene in Escherichia coliCurrent Microbiology, 2004
- Widespread Selection for Local RNA Secondary Structure in Coding Regions of Bacterial GenesGenome Research, 2003
- Predictive Identification of Exonic Splicing Enhancers in Human GenesScience, 2002
- Prediction of complete gene structures in human genomic DNAJournal of Molecular Biology, 1997
- Fitting a mixture model by expectation maximization to discover motifs in biopolymers.1994
- The codon adaptation index-a measure of directional synonymous codon usage bias, and its potential applicationsNucleic Acids Research, 1987