Efficient RNAi-based gene family knockdown via set cover optimization

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.