Synthetic lethal reaction/gene sets are sets of reactions/genes where only the simultaneous removal of all reactions/genes in the set abolishes growth of an organism. In silico, synthetic lethal sets can be identified by simulating the effect of removal of reaction/gene sets from the reconstructed genome-scale metabolic network of an organism. Previous approaches to identify synthetic lethal reactions in genome-scale metabolic networks have built on the framework of Flux Balance Analysis (FBA), extending it either to exhaustively analyse all possible combinations of reactions, or formulate the problem as a bi-level Mixed Integer Linear Programming (MILP) problem1. FAST-SL circumvents the complexity of both exhaustive enumeration and the bi-level MILP by iteratively reducing the search space and the computational time involved in identification of synthetic lethal reaction sets. FAST-SL, while considering all possible phenotypes and all parts of metabolism, efficiently identifies the targeted phenotypes. Our algorithm shows more than a 4000-fold reduction in search space over exhaustive enumeration of triple lethal sets for Escherichia coli iAF1260 model. Unlike the previous methods used for identification of lethal reaction sets, FAST-SL uses the sparsest solution obtained by solving the Flux Balance constraints of a metabolic network, which is a Linear Programming problem, to eliminate reaction combinations that do not lead to a lethal phenotype, and thereby reducing the search space for identifying lethal reaction sets.
As our algorithm finds application in the identification of combinatorial drug targets, in this study, we performed synthetic reaction and gene lethality analysis for genome-scale reconstructions of Salmonella enterica typhimurium and Mycobacterium tuberculosis. We validated the reaction lethals obtained using FAST-SL with exhaustive enumeration of reaction deletions up to the order of two for these organisms. The triple lethal reactions obtained for Escherichia coli using FAST-SL have a precise match with the results obtained with exhaustive enumeration, by performing it on a high-performance computer cluster. Our results also completely agree with those of the SL finder algorithm1; notably, our algorithm is substantially faster. Further, we also present a mathematical proof for the correctness of our algorithm.
Overall, FAST-SL is a powerful tool to identify the lethal reaction/gene sets, through a massive reduction in the search space over an exhaustive enumeration approach and the SL Finder algorithm. We believe that our algorithm presents an important advance and can enable the rapid enumeration of synthetic lethal reaction/gene sets in genome-scale metabolic networks.
Availability: The MATLAB implementation of our algorithm (compatible with the COBRA toolbox v2.0, a popular toolbox for constraint-based analysis of metabolic networks) is freely available from https://home.iitm.ac.in/kraman/lab/research/fast-sl.