Fast-SL: An efficient algorithm to identify synthetic lethals

On 1 July, 2014
DoE_Ecoli_Web

A representative image of `Degree of Essentiality’ of reactions identified using Fast-SL in E. coli core metabolism.                    (Image credits: Escher)

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 analyse 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. 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 parallelised our algorithm, enabling the identification of synthetic lethal gene quadruplets for all three organisms in under six hours. 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.

Availability: The MATLAB implementation of the algorithm, compatible with COBRA toolbox v2.0 is available at GitHub.

Original Paper:

  • [DOI] A. Pratapa, S. Balachandran, and K. Raman, “Fast-SL: an efficient algorithm to identify synthetic lethal sets in metabolic networks,” Bioinformatics, vol. 31, iss. 20, pp. 3299-3305, 2015.
    [bibtex]
    @article{Pratapa2015FastSL,
      abstract = {Motivation: 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.},
      added-at = {2018-12-02T16:09:07.000+0100},
      author = {Pratapa, A. and Balachandran, S. and Raman, K.},
      biburl = {https://www.bibsonomy.org/bibtex/2c6d35c9c94986676e22b1fd132d7475b/karthikraman},
      citeulike-article-id = {13648461},
      citeulike-linkout-0 = {http://www.ncbi.nlm.nih.gov/pubmed/26085504},
      citeulike-linkout-1 = {http://dx.doi.org/10.1093/bioinformatics/btv352},
      citeulike-linkout-2 = {http://bioinformatics.oxfordjournals.org/content/early/2015/06/16/bioinformatics.btv352.abstract},
      citeulike-linkout-3 = {http://bioinformatics.oxfordjournals.org/content/early/2015/06/16/bioinformatics.btv352.full.pdf},
      citeulike-linkout-4 = {http://bioinformatics.oxfordjournals.org/cgi/content/abstract/31/20/3299},
      citeulike-linkout-5 = {http://view.ncbi.nlm.nih.gov/pubmed/26085504},
      citeulike-linkout-6 = {http://www.hubmed.org/display.cgi?uids=26085504},
      day = 15,
      doi = {10.1093/bioinformatics/btv352},
      interhash = {417235ec10ac24def5c5e2cc4a920517},
      intrahash = {c6d35c9c94986676e22b1fd132d7475b},
      issn = {1460-2059},
      journal = {Bioinformatics},
      keywords = {flux-analysis myown synthetic-lethality},
      month = oct,
      number = 20,
      pages = {3299--3305},
      pmid = {26085504},
      posted-at = {2015-06-18 08:56:24},
      priority = {2},
      publisher = {Oxford University Press},
      timestamp = {2019-04-17T12:59:47.000+0200},
      title = {{Fast-SL}: an efficient algorithm to identify synthetic lethal sets in metabolic networks},
      url = {http://www.ncbi.nlm.nih.gov/pubmed/26085504},
      volume = 31,
      year = 2015
    }

A preprint of the manuscript, including the algorithm is available from arXiv.

Comments are closed.