ARCHIVE Snapshot of the Rätsch lab website (Tübingen, then New York) as of February 2016: preserved, not maintained. The group today: bmi.inf.ethz.ch
Personal tools
Home → Rätsch Lab → People → Research Topics → Machine Learning → Extracting Discriminative Motifs Based on SVM Detectors
 
Document Actions

Extracting Discriminative Motifs Based on SVM Detectors

At the heart of many important bioinformatics problems, such as gene finding and function prediction, is the classification of biological sequences. Frequently the most accurate classifiers are obtained by training support vector machines (SVMs) with complex sequence kernels. However, a cumbersome shortcoming of SVMs is that their learned decision rules are very hard to understand for humans and cannot easily be related to biological facts. In this project we aim to develop new techniques to improve the interpretability of predictive methods including SVMs.

Positional Oligomer Importances

Many genomic signal detectors [cf. our gene finder mGene] work by inspecting the sequence at hand for the incidence of certain oligomers at certain positions. Implicitly, an accurate signal detector must "know" which of these positional oligomers (POs) are relevant to the corresponding signal. We extract this information in order to enable a more in-depth understanding of the related cellular processes.

We define the importance of any PO to be the expected increase of the signal detector's confidence in the classification:

importance of PO := average detector score of sequence with this PO - average detector score of sequence without this PO

The importances of all possible POs of a given length are collected in a *positional oligomer importance matrix* (POIM). We devised recursions to efficiently compute POIMs and implemented them in Shogun. We now work on summarizing the resulting POIMs by a small set of motifs that are more readily understandable to humans by a model-based clustering of the POIMs.

POIM project webpage

Feature Importance Ranking Measure

The Feature Importance Ranking Measure (FIRM) is a generalization of the concept underlying POIMs from sequence classification to more general learning machines (classification, regression, ranking, etc) on more general input data (most importantly, real numbers).

In contrast to feature selection, which often decreases the predictive accuracy, this type of retrospective analysis of trained learning machines allows to achieve both excellent predictive performance and superior interpretation. In contrast to standard raw feature weighting, FIRM takes the underlying correlation structure of the features into account. Thereby, it is able to discover the most relevant features, even if their appearance in the training data is entirely prevented by noise.

Regulatory Modules Kernel

We develop methods to predict the regulation of genes through transcription factors (TF) from the euchromatic sequence of co-regulated genes in eukaryotes. We look for overrepresented, putative binding motifs of TFs, exploiting the facts that (i) many eukaryotic genes have a homolog in related species and binding motifs are thus conserved; (ii) many transcription factors exhibit a positional preference when binding in a regulatory region; and (iii) most genes are controlled by a combination of factors with their corresponding binding sites forming homotypic or heterotypic clusters known as cis-regulatory modules.

The Regulatory Modules kernel captures these three points and is able to classify genes (based on information from their regulatory sequence).

People specializing in this area

Group Leader

Gunnar Rätsch, Ph.D.

Gunnar Rätsch, Ph.D.

Together with Sören Sonnenburg, I invented the very first version of the the Positional Importance Matrix for visualizing complex decision boundaries of string classifiers (published in PLoS Comp. Bio)
More about Gunnar Rätsch, Ph.D....

Alumnae and Alumni

Petra Philips, Ph.D./The Australian National University

Petra Philips, Ph.D./The Australian National University

More about Petra Philips, Ph.D./The Australian National University...
Sebastian J. Schultheiss

Sebastian J. Schultheiss

I have developed a processing pipeline for regulatory sequences of genes that are thought to be co-regulated. KIRMES incorporates the Regulatory Modules kernel which is used to model degenerate, position-specific modules of regulatory elements in non-coding DNA sequences of organisms.
More about Sebastian J. Schultheiss...
Sören Sonnenburg, Ph.D.

Sören Sonnenburg, Ph.D.

With Gunnar Raetsch I had the idea to visualize the importance of positional k-mer in a matrix like shape. Since string kernels often use large k-mer lengths and employ overlapping weights the idea was to visualize importances of shorter k-mers while taking into account all contributions from overlapping k-mers. This lead to the development of POIMs (formalized by Alexander Zien). Together with Alexander Zien and Petra Philips I implemented an efficient algorithm to compute POIMs in shogun and performed extensive experiments on artificial and real-world splice site prediction, transsplicing and TSS recognition data sets.

More about Sören Sonnenburg, Ph.D....
Alexander Zien, Ph.D.

Alexander Zien, Ph.D.

Given highly accurate sequence classification, it is of high interest to find the relevant subsequences (->motifs). I contrived a formal model of the importance of any positional oligomer (PO) for the classification: the expected SVM score increase due to its incidence in any sequence. This was inspired by an earlier algorithm by Sören Sonnenburg and Gunnar Rätsch. The importance definition implies an exponential sum, which I reduced to tractable recursions that Sören Sonnenburg, Petra Philips, and me implemented in Shogun. Now I work with Sebastian Schultheiss on summarizing the resulting POIMs by a small set of motifs that are more readily understandable to humans.

More about Alexander Zien, Ph.D....

Publications