title: Fast-SL: an efficient algorithm to identify synthetic lethal sets in metabolic networks.
abstract: BACKGROUND
  Synthetic lethal sets are sets of reactions/genes where only the simultaneous removal of all reactions/genes in the set abolishes growth of an organism. Previous approaches to identify synthetic lethal genes in genome-scale metabolic networks have built on the framework of flux balance analysis (FBA), extending it either to exhaustively analyze all possible combinations of genes or formulate the problem as a bi-level mixed integer linear programming (MILP) problem. We here propose an algorithm, Fast-SL, which surmounts the computational complexity of previous approaches by iteratively reducing the search space for synthetic lethals, resulting in a substantial reduction in running time, even for higher order synthetic lethals.
  
  
  RESULTS
  We performed synthetic reaction and gene lethality analysis, using Fast-SL, for genome-scale metabolic networks of Escherichia coli, Salmonella enterica Typhimurium and Mycobacterium tuberculosis. Fast-SL also rigorously identifies synthetic lethal gene deletions, uncovering synthetic lethal triplets that were not reported previously. We confirm that the triple lethal gene sets obtained for the three organisms have a precise match with the results obtained through exhaustive enumeration of lethals performed on a computer cluster. We also parallelized our algorithm, enabling the identification of synthetic lethal gene quadruplets for all three organisms in under 6 h. Overall, Fast-SL enables an efficient enumeration of higher order synthetic lethals in metabolic networks, which may help uncover previously unknown genetic interactions and combinatorial drug targets.
  
  
  METHODS
  The MATLAB implementation of the algorithm, compatible with COBRA toolbox v2.0, is available at https://github.com/RamanLab/FastSL CONTACT: kraman@iitm.ac.in
  
  
  BACKGROUND
  Supplementary data are available at Bioinformatics online.
authors.affiliation: Department of Biotechnology, Bhupat and Jyoti Mehta School of Biosciences and.
authors.forename: Aditya
authors.initials: A
authors.lastname: Pratapa
authors.affiliation: Department of Computer Science and Engineering, Indian Institute of Technology Madras, Chennai 600 036, India.
authors.forename: Shankar
authors.initials: S
authors.lastname: Balachandran
authors.affiliation: Department of Biotechnology, Bhupat and Jyoti Mehta School of Biosciences and.
authors.forename: Karthik
authors.initials: K
authors.lastname: Raman
mesh_terms: D000465:Algorithms; D005804:Genes, Lethal; D016680:Genome, Bacterial; D053858:Metabolic Networks and Pathways / Q000235:genetics*; D011382:Programming, Linear