Searching for synergies: matrix algebraic approaches for efficient pair screening

I have together with Sven Nelander and Rebecka Jörnsten been working on the problem of experimental design for the screening of pairs of perturbations to biological systems, be it gene knock-outs or drugs or a combination thereof. The problem that arises is that the number of possible pairs grows quadratically with the number of perturbations, and this makes it impractical to test all possible combinations. In answer to this we have developed an algorithm that searches the space of combinations in an adaptive fashion making use of information found during the screen to direct the search.

The results of this work were recently accepted for publication in PLoS ONE. Below is the abstract and here's a link to the paper (not yet available on the PLoS-site).

Abstract
Functionally interacting perturbations, such as synergistic drugs pairs or synthetic lethal gene pairs, are of key interest in both pharmacology and functional genomics. However, to find such pairs by traditional screening methods is both time consuming and costly. We present a novel computational-experimental framework for efficient identification of synergistic target pairs, applicable for screening of systems with sizes on the order of current drug, small RNA or SGA (Synthetic Genetic Array) libraries (>1000 targets). This framework exploits the fact that the response of a drug pair in a given system, or a pair of genes’ propensity to interact functionally, can be partly predicted by computational means from (i) a small set of experimentally determined target pairs, and (ii) pre-existing data (e.g. gene ontology, PPI) on the similarities between targets. Predictions are obtained by a novel matrix algebraic technique, based on cyclical projections onto convex sets. We demonstrate the efficiency of the proposed method using drug-drug interaction data from seven cancer cell lines and gene-gene interaction data from yeast SGA screens. Our protocol increases the rate of synergism discovery significantly over traditional screening, by up to 7-fold. Our method is easy to implement and could be applied to accelerate pair screening for both animal and microbial systems.