Fast-SL: an efficient algorithm to identify synthetic lethal sets in metabolic networks

作     者：Pratapa, Aditya Balachandran, Shankar Raman, Karthik 

作者机构：Indian Inst Technol Dept Biotechnol Bhupat & Jyoti Mehta Sch Biosci Madras 600036 Tamil Nadu India Indian Inst Technol Dept Comp Sci & Engn Madras 600036 Tamil Nadu India 

出 版 物：《BIOINFORMATICS》 (生物信息学)

年 卷 期：2015年第31卷第20期

页      面：3299-3305页

核心收录：

学科分类：0710[理学-生物学] 08[工学] 0714[理学-统计学（可授理学、经济学学位）] 0836[工学-生物工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：Department of Biotechnology, Government of India [BT/PR4949/BRB/10/1048/2012] IIT Madras 

主　　题：Lethal mutations Genes Escherichia coli -- Metabolism Mixed integer linear programming Salmonella enterica serovar typhimurium Mycobacterium tuberculosis -- Genetic aspects 

摘      要：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. Results: We performed synthetic reaction and gene lethality analysis, using Fast-SL, for genomescale 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.