5
$\begingroup$

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.

$\endgroup$

migrated from cs.stackexchange.com Jan 18 '13 at 13:02

This question came from our site for students, researchers and practitioners of computer science.

  • $\begingroup$ What do you use for measuring similarity? They are many methods. Are you aware of (multiple) sequence alignments? $\endgroup$ – Raphael Jan 14 '13 at 11:42
  • $\begingroup$ There is a SE-style bioinformatics site called biostar. PMS is a combinatorial search method for de-novo sequencing of motifs. It seems to allow for some length parameters as well. $\endgroup$ – Nicholas Mancuso Jan 14 '13 at 14:59
  • $\begingroup$ @Raphael : I'm putting a distribution on the known sequences, and then using pvalues for the others. The details are a little involved. I could send you a copy of the paper if you like. I'm not sure what you mean about ` (multiple) sequence alignments`. Can you give more details or a reference? Thanks. $\endgroup$ – Faheem Mitha Jan 14 '13 at 15:53
  • $\begingroup$ @NicholasMancuso Thanks for the link. Yes, I'm already aware of biostar, but I've had difficulty finding information about this, so I'm asking in multiple places. I've taken a look at PMS. Do you have experience using it? Is it considered a standard method, assuming there are such things in this area? $\endgroup$ – Faheem Mitha Jan 14 '13 at 15:55
  • $\begingroup$ You can find a load of information on Wikipedia. What you describe is too general to compare it with anything, I'm afraid. $\endgroup$ – Raphael Jan 14 '13 at 15:57
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Hi Peter, Thanks for the reply and the link. I do have a rough idea of what Support Vector Machines are, but have never actually used them for anything. Regardless, I'm looking for ready-to-methods with a usable software implementation, which I can just apply. If you are aware of any such project(s), please let me know. Unfortunately this area has a huge number of possibly related publications, with little order, so it is difficult to make sense of it. $\endgroup$ – Faheem Mitha Jan 17 '13 at 8:19
  • $\begingroup$ Most people I know who work with Kernel methods use MATLAB. They have a bio-informatics toolbox, so most of the work will be done already, although you will have to spend some time to tie it all together. If you don't have access to matlab, python is probably the best alternative (specifically SciPy). You may want to look at biopython.org/wiki/Main_Page $\endgroup$ – Peter Jan 17 '13 at 10:18
  • $\begingroup$ Hi Peter. Thanks for the comments. No, I don't have easy access to MATLAB, and generally try to avoid proprietary languages anyway. I've actually looked at biopython already, but it does not have anything relevant. Scipy does not have anything as specialist as this. I think I'll try asking Bioconductor next. I think it is a relatively large bioinformatics community. $\endgroup$ – Faheem Mitha Jan 17 '13 at 11:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.