Binary classification of DNA motif sequences (bioinformatics)

Question

I've been working on on a method for binary classification of DNA sequences. In more detail, here is what the method does.

Given a family of DNA sequences, for example DNA sequence motifs, I try to predict whether other sequences belong to this family, by measuring their similarity to the sequences in the family. My method fits a distribution to the sequences, and then assigns a pvalue to sequences not in the family.

In the data I'm using, the sequences are all of length 28. The sequences I am analyzing are here, specifically human 12 RSS and mouse 12 RSS.

Since a comparison to existing methods is always a good thing, I am wondering what are the standard methods to beat, if any? I'm not very familiar with the available methods/algorithms.

I am in the process of trying MEME. This does not seem to do exactly what I want, and I don't know if I will be able to persuade it to. Specifically, I'm not sure if I can tell it that the sequences of 28 length are the motif. I got the impression from the documentation that it decides what the motifs are by itself, or something.

This would probably be more on-topic on a bioinformatics site, but SE does not currently have one, so I'm trying here.

I can give further details if necessary.

NOTE: I think it would be nice if a bioinformatics tag could be created and used here. This does not seem to exist currently.

UPDATE: I think my original question was poorly written and lacked sufficient detail, so I'm adding some more (hopefully useful) details.

I'm analyzed two RSS data sets, each of which is a collection of sequences, as I state above. The main purpose of the analysis is to do prediction. So, I used a cross-validation method. I divided each data set into 5 parts, and use 4 of the five parts as a training set in turn. (The number 5 here is a bit arbitrary, but since I want to include the results per training set, I don't want the number to be too large.) After fitting a model to the training set, I then used this model for prediction as follows.

The RSS data set is contained in gene segments, typically one or two RSS per gene segment. The gene segments are often much larger than the RSS. These are 12 RSS, so each RSS is of length 28. I took all the gene segments I could find that contained an RSS, and selected from them all contigous sequences of length 28. The current total number of these sequences is 449905 for one, and 624400 for the other. The corresponding number of RSS was 118 and 201. Note that these sets did not necessarily contain all distinct values.

So, I used the model derived from the training set to calculate pvalues for all these approx 500,000 sequences. (I'm leaving out some details here, but I don't think it is important how exactly I calculated the values.)

Then I ranked the sequences by order of decreasing pvalues. The idea was that the RSS sequences would rank highly in this ranking, and in the event they did.

Now, I'd like to find an algorithm which can perform a similar procedure. So far I haven't had much luck - I've been wading through a morass of confusing papers and results, mostly written by biologists, and therefore hard for me to understand. Much of the related material seems to be about de novo motif discovery, which is about magically finding motifs apparently without a training set. Also, much of the software does not seem designed to deal with sequences as long or as numerous as in my example. Someone suggested tomtom from MEME, but so far I've not got it to work.

Answer 1

Kernel methods (such as Support Vector Machines) are very popular for this sort of thing.

Basically Support Vector Machine defines a distance function between two sequences (like text, or DNA), usually based on a fancy version of edit distance. Then it translates the sequences to points in a high dimensional space and fits a hyperplane to separate the sequences in each class neatly (which is always easier to do in many dimensions). The trick to kernel methods is that you can actually sidestep the translation to higher dimensions, and work directly on the data as if you had translated to a high dimensional space, so it works very efficiently.

This is a very good book with an introduction to kernel methods for biologists and an introduction to genetics for computer scientists.