In this blog post we consider the following problem:
Gene Sequence Classification Problem (GSCP): Given two genes, G1 and G2, and a (relatively short) subsequence S from one of them tell from which gene the subsequence S is part of.
One way to derive a solution for this problem is to model each gene with an ngram model and classify the subsequences according to the risk ratio statistic or odds ratio statistic based on the Markov chain state transition probabilities. We are going to make classification experiments for different n’s of the ngram model and use a type of Receiver Operating Characteristic (ROC) plot to judge which n is the best.
This approach can be also applied to text classification. I consider genes for conciseness and clarity.
The full article with Mathematica code for the experiments described in the post can be downloaded from here.
The computations for the plots shown below were done with the Mathematica package for ngram Markov chain models NGramMarkovChains.m provided by the MathematicaForPrediction project at GitHub.
Data and models
Mathematica has the function GenomeData that gives the DNA sequences for specified genes.
I made classification experiments for the following pairs of genes:
1. F2 and ETS1
The classification is done for sequences like this:
In[812]:= StringTake[GenomeData["F2", "FullSequence"], {11200, 11200 + 100}]
Out[812]= "AGCAGGCATATCTAGGGGAGGAGCACCGCAGGCTGGGGGCATGGCAGGCACTAAGGCCCTGAGGTGGGA\
GCACTCTTGGCTTGTCTGGGGAGCAGTAGGGA"
Approach
Let us provide more details for the approach outlined at the beginning of the post.
First we define the classification algorithm NGramClassifier(k):
(I was too lazy to type the algorithm in here so I used a screenshot of the description I wrote in Mathematica.)
In order to find the best k for NGramClassifier(k) we make the following sets of experiments:
 For each k, 1<=k<=10 calculate kgram models for G1 and G2. For these models use only the first 80% of the gene sequences. (In other words, for each Gi the training set is only 80% of Gi’s length.)

Using the last 20% of G1 and G2 derive a set of test sequences T by randomly picking Gi and the subsequence length within the range {minLen, maxLen}.

For each k, 1<=k<=10 calculate the classifications of the elements of T using NGramClassifier(k) with the models calculated in step 1.

Calculate the True Positive Rate (TPR) and False Positive Rate (FPR) for each k in step 3.

Plot the points with coordinates {{TPR(k),TPR(k)}}, k in [1 10] and select the best k.
ROC
With the classification results of the tuning experiments we make the following ROC point plots
1. F2 vs. ETS1
Conclusions and extensions
From the ROC plots we can see that the best classification results for GSCP with the genes “F2” and “ETS1” are obtained with Markov chain order 3 (or with 4grams). Using order 2 (or 3grams) is almost as good.
The experiments for the genes “F2” and “PAH” showed that using 3grams gives best results for GSCP.
A natural extension of the experiments described is to repeat them for other pairs of genes and across different lengths of subsequences. In this way we can derive more general conclusions for the best ngram length in the algorithm NGramClassifier.
Pingback: Markov chains ngram model implementation  Mathematica for prediction algorithms