CodingMotif: exact determination of overrepresented nucleotide motifs in coding sequences

BMC Bioinformatics

Research Article

Jeffrey H Chuang¹  Yang Ding²  William A Lorenz³ 

[1] Department of Biology, Boston College, 02467, Chestnut Hill, MA, USA;Department of Biology, University of Pennsylvania, 19104, Philadelphia, PA, USA;Department of Mathematics and Computer Science, Denison University, 43023, Granville, OH, USA;

关键词: Codon;    Codon Usage;    Null Model;    Original Sequence;    Exonic Splice Enhancer;   

DOI  :  10.1186/1471-2105-13-32

 received in 2011-09-07, accepted in 2012-02-14,  发布年份 2012

来源: Springer

【 摘 要 】

BackgroundIt 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.ResultsWe 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.ConclusionsCodingMotif 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.tar

【 授权许可】

Unknown   
© Ding et al; licensee BioMed Central Ltd. 2012. This article is published under license to BioMed Central Ltd. This is an Open Access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/2.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.