Efficient RNAi-based gene family knockdown via set cover optimization

We address the problem of selecting an efficient set of initiator molecules (siRNAs) for RNA interference (RNAi)-based gene family knockdown experiments. Our goal is to select a minimal set of siRNAs that (a) cover a targeted gene family or a specified subset of it, (b) do not cover any untargeted genes, and (c) are individually highly effective at inducing knockdown.

We give two formalizations of the gene family knockdown problem. First, we show that the problem, minimizing the number of siRNAs required to knock down a family of genes, is NP-Hard via a reduction to the set cover problem. Second, we generalize the basic problem to incorporate additional biological constraints and optimality criteria. To solve the resulting set-cover variants, we modify the classical branch-and-bound algorithm to include some of these biological criteria. We find that in many typical cases these constraints reduce the search space enough that we are able to compute exact minimal siRNA covers within reasonable time. For larger cases, we propose a probabilistic greedy algorithm for finding minimal siRNA covers efficiently. We apply our methods to two different gene families, the FREP genes from Biomphalaria glabrata and the olfactory genes from Caenorhabditis elegans.

Our computational results on real biological data show that the probabilistic greedy algorithm produces siRNA covers as good as the branch-and-bound algorithm in most cases. Both algorithms return minimal siRNA covers with high predicted probability that the selected siRNAs will be effective at inducing knockdown. We also examine the role of "off-target" interactions: the constraint of avoiding covering untargeted genes can, in some cases, substantially increase the complexity of the resulting solution. Overall, we find that in many common cases our approach significantly reduces the number of siRNAs required in gene family knockdown experiments, as compared to knocking down genes independently.