Enhanced Regulatory Sequence Prediction Using Gapped k-mer Features

Mahmoud Ghandi*, Dongwon Lee*, Morteza Mohammad-Noori, Michael A. Beer

* These authors contributed equally to the work

Oligomers of length k, or k-mers, are convenient and widely used features for modeling the properties and functions of DNA and protein sequences. However, k-mers suffer from the inherent limitation that if the parameter k is increased to resolve longer features, the probability of observing any specific k-mer becomes very small, and k-mer counts approach a binary variable, with most k-mers absent and a few present once. Thus, any statistical learning approach using k-mers as features becomes susceptible to noisy training set k-mer frequencies once k becomes large. To address this problem, we introduce alternative feature sets using gapped k-mers, a new classifier, gkm-SVM, and a general method for robust estimation of k-mer frequencies. To make the method applicable to large-scale genome wide applications, we develop an efficient tree data structure for computing the kernel matrix. We show that compared to our original kmer-SVM and alternative approaches, our gkm-SVM predicts functional genomic regulatory elements and tissue specific enhancers with significantly improved accuracy, increasing the precision by up to a factor of two. We then show that gkm-SVM consistently outperforms kmer-SVM on human ENCODE ChIP-seq datasets, and further demonstrate the general utility of our method using a Naive-Bayes classifier. Although developed for regulatory sequence analysis, these methods can be applied to any sequence classification problem.

New Software

We have released new gkm-SVM software: (Application Notes under review)
For ~20000 training sequences, the easiest and fastest new kernel implementation is our new R package:
For Linux or mac: gkmSVM-R
Windows users should use the CRAN library

If you have larger sequence sets we recommend our large scale software which does not pre-compute the kernel matrix: LS-GKM


If you use gkm-SVM, please cite as:
Ghandi M, Lee D, Mohammad-Noori M, Beer MA. 2014. Enhanced Regulatory Sequence Prediction Using Gapped k-mer Features. PLoS Comput Biol 10: e1003711. pubmed


previous version: gkmsvm-1.3.tar.gz


Training Data Sets

All sequence data sets in FASTA format: sequences_gkmsvm.tar.gz (~325Mb)

If you have any questions, please contact Mahmoud Ghandi at ghandi AT jhmi DOT edu.