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.
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.