MoSDi -- Motif Statistics and Discovery

Biological sequence analysis is often concerned with the search for structure in long strings like DNA, RNA or amino acid sequences. Frequently, "search for structure" means to look for patterns that occur very often. Here, two problems arise:

Sensibly define a measure of over-representation (i.e. a score).
Discover motifs with good (or even optimal) score.

A huge number of (often ad-hoc) score functions and (often heuristic) motif discovery algorithms have been proposed over the last years. In our research, we seek to address the motif discovery problem in an exact and statistically rigorous manner. To this end, we recently introduced probabilistic arithmetic automata, a theoretical framework allowing for fast and exact motif statistics (see [1]). In [2] we present an algorithm to discover the optimal motif with respect to its p-value.

Software

All motif statistics and motif discovery algorithms explained in [1] and [2] (and more) has been implemented in JAVA in a software package called MoSDi. This software is currently in an experimental/alpha stage. All algorithms from [1] and [2] are, however, fully usable and tested.

Download

MoSDi Revision 468 (as of 2009/01/13): JAR-File
MoSDi uses jopt-simple to parse command line options. Right now, a version prior to 3.0 must be used (interface is not backwards-compatible and we haven't ported our code yet). The last 2.x version is 2.4.1.

Source Code

A source code release is planned for the near future.

How to use MoSDi for DNA motif discovery

This example has been tried in a bash shell under Linux. It should work on any other Unix-like OS without any problems. If you use Windows, you may want to try cygwin.
MoSDi is configured to look for the file jopt-simple.jar in the directory of the MoSDi JAR-file. The easiest way to satisfy this requirement is to create a link named jopt-simple.jar in the same directory as the MoSDi JAR-file:
```
$ cd <path-to-mosdi-jar>
$ ln -s <path-to-jopt-simple>/jopt-simple-<version>.jar jopt-simple.jar
```
To test motif discovery, please download this file with (toy-)example sequences. (Format: one sequence per line, fasta format is currently not supported). For convenience, save the file in the same directory as the MoSDi JAR-file.
In our toy example, we wish to examine all IUPAC motifs of length 8 with at most 2 of the characters R, Y, W, S, K, M (two-nucleotide-wildcards) and with at most 2 Ns (four-nucleotide-wildcard). At first, we need to generate a list of abelian patterns that satisfy these conditions:
```
$ java -jar mosdi_r468.jar iupac_abelian_gen -M 8,2,0,2 8 > abelian_patterns
```
Now we examine the example sequences with respect to these abelian patterns
```
$ java -jar mosdi_r468.jar discovery -t 1e-15 -F example-sequences abelian_patterns |grep '>>' > results
```
The switch "-t 1e-15" tells the algorithm to look for motifs with a p-value below 1e-15. Grepping for >> saves us from the software's rather detailed output. Note that, in order to parallelize the computation, we may split the file abelian_patterns into chunks and process them on different cores/machines.

Sorting results by p-value gives us the winner motif (along with some statistics):

>>p_value>> 3.617957e-37 LIN >>stats>> TAARASGA 1 9 9 17 5.170981e-02 >>poisson>> 5.170981e-02 1.000000e+00 >>runtimes>> 0.000000e+00 0.000000e+00 0.000000e+00

The motif discovery process is as yet restricted to i.i.d. background models. Thus we might want to re-evaluate all returned motifs with respect to a Markovian background model. Firstly, we create a list of all returned motifs:
```
$ grep '>>p_value>' results | cut -d ' ' -f 5 > motifs
```
Then, we re-evaluate these motifs w.r.t. an third order Markov model (M3):
```
$ java -jar mosdi_r468.jar calc_scores -M3 -F example-sequences motifs |grep '>>' > results_M3
```

Contact

If you have any questions, suggestions, or comments, please feel free to contact Tobias Marschall.
E-mail: tobias.marschalltu-dortmund.de

References

[1]	Tobias Marschall and Sven Rahmann. Probabilistic arithmetic automata and their application to pattern matching statistics. In Paolo Ferragina and Gad Landau, editors, Combinatorial Pattern Matching (CPM'08), volume 5029 of LNCS, pages 95-106. Springer, 2008.
[2]	Tobias Marschall and Sven Rahmann. Efficient Exact Motif Discovery. Submitted.

Last changed 2009/06/09