# Finding the best features in interaction models

I have list of proteins with their feature values. A sample table looks like this:

...............Feature1...Feature2...Feature3...Feature4
Protein1
Protein2
Protein3
Protein4


Rows are proteins and columns are features.

I also have a list of proteins which interact as well; for example

Protein3, Protein4
Protein1, Protein2
Protein4, Protein1


Problem: For a preliminary analysis I want to know which features contribute the most for protein interactions.

My understanding is that normally decision trees could be used for obtaining the most important feature based on entropy, but I'm not sure how to extend it to protein pairs (i.e., interactions). Is there a method for such purpose?

-
Tell me if I understand you correctly: you have an interaction strength for any pair of proteins (which for example, is zero if the proteins don't interact), and then you want to have a vector of features whose value will be highly correlated with the interaction strength? Or, in other words, which will allow you to predict interaction strength between the proteins? –  dsign Jun 21 '12 at 7:05

Actual recipe for solving the presented problem (one possible solution)

It is straight-forward to solve this problem using my favorite machine-learning tool, vowpal wabbit which supports quadratic (cross) features via its -q option.

vowpal wabbit background

Before we jump into usage details. vowpal wabbit is a linear + bilinear fast and scalable online machine-learning software for both classification and regression. I get learning (training) rates of about 5 million features per second on my desktop with no limit on data-size (number of examples) since as an online learning tool it doesn't require loading the full data into memory. It has many other attractive features: support for different learning algorithms, multiple loss functions, sparse features, mixed feature types, and more, which are beyond the scope of this question.

Here are the 3 steps to solving the problem with commentary:

Step 0: Download and build vowpal wabbit from github (see note at bottom on supported environments)

Step 1: Prepare a training-set where each line looks like this:

1.0 protein1/protein2|A p1_feature1 p1_feature2 ... |B p2_feature1 ...
...


explanation of the training-set format:

The leftmost number, 1.0, is the label (interaction strength, which can be any numeric value), the second string 'protein1/protein2' is a tag to give the line an identity, IOW: "this line represents the interaction between protein1 and protein2"; It is optional, and you may think of it as a comment. This tag-string is also echoed in predictions from models to identify which prediction belongs to which example, but we're not predicting here, we're just modeling and studying our model. Next comes the input feature name space for the first protein '|A' (we need to define a name-space so we can cross between different name-spaces, it doesn't have to be 'A', can be any word in fact, but the first letter has to differ between name spaces so we can cross them in the command call) followed by the list of input features for the 1st protein p1. Last comes the name-space for protein2: '|B' followed by the feature-names of protein2.

One of the beauties of vowpal wabbit is that you can use arbitrary strings for feature names (it'll hash them internally, but you don't care). The only special chars in the training set are:

• spaces (obviously)
• '|', to prefix input features and name-spaces, and
• ':' to separate feature-names from their values

The ':' is not used here, because we assume every protein feature name represents a boolean (existence) so their values default to '1' and they don't need explicit values.

Now you may run vowpal_wabbit (the executable name is vw) with '-q AB' to create cross-features between all the possible pairs of features where one feature is selected from protein1 (name space starting with 'A') and the other from protein2 (name-space starting with 'B'). vowpal_wabbit will read the data, learn and create a model with weights for every feature combination that results in some interaction between the pair of proteins. Here, instead of running vw directly, we'll run it through the vw-varinfo wrapper utility, which comes with vowpal wabbit, as our last step. vw-varinfo runs vw to create the model, and dumps the model in human-readable form.

Step 3: call vw-varinfo like this:

vw-varinfo -q AB -c --passes 20 your_data_set_file


vw-varinfo will pass all options (-q ... -c --passes ...) as-is to vw. Only the '-q AB' for crossing the two feature name-spaces is essential. I added one more options above (multiple passes), which I believe would give better results.

This command will call vowpal wabbit (vw) to train on the data set, and print the output I believe you're looking for: all the feature interactions in order of strength and their relative weights.

Example input and output

Suppose your input (prot.dat) includes a 3-way interaction between 3 proteins:

1.0 protein1/protein2|A a b |B k m
0.6 protein2/protein3|A k m |B b c d
2.2 protein1/protein3|A a b |B b c d


This is deliberately a very minimalistic example. vw shouldn't have any issue with much larger data-sets (e.g. millions of rows, hundreds of features), also, I varied the interaction-strength labels in the examples. If in your case interaction is a boolean "yes" or "no", simply use 0 (no interaction) or 1 (interaction exists) as the 1st field in each line.

Running:

vw-varinfo -q AB -c --passes 20 prot.dat


Would yield all the possible interactions (ignore the name-spaces 'A' and 'B' in the output) and their weights:

FeatureName        HashVal   MinVal   MaxVal    Weight   RelScore
A^k                 220268     0.00     1.00   +0.3804    100.00%
A^k^B^k             254241     0.00     0.00   +0.3804    100.00%
A^k^B^m              93047     0.00     0.00   +0.3804    100.00%
B^k                 178789     0.00     1.00   +0.1011     26.58%
B^m                  17595     0.00     1.00   +0.1011     26.58%
[... trimmed for brevity ...]
A^m^B^m             141879     0.00     0.00   +0.0000      0.00%
Constant            116060     0.00     0.00   +0.1515      0.00%
A^b                 139167     0.00     1.00   -0.0641    -16.86%
A^b^B^k             204424     0.00     0.00   -0.1233    -32.43%
A^b^B^m              43230     0.00     0.00   -0.1233    -32.43%


Showing that in this data the strongest contributors to any interactions in general are 1) the mere presence of the 'k' feature, 2) the 'k' feature interacting with itself (assuming both proteins have it), and 3) 'k' interacting with 'm'. while the weakest (negative contribution to protein interaction) are the 'b' feature paired with 'm' feature.

Here's a HOWTO page on vw-varinfo

vowpal wabbit builds from source (see link above) and runs on Linux (and possibly other unixes), Mac OS-X, and Windows.

HTH

-