title: An iterative algorithm for metabolic network-based drug target identification.
abstract: Post-genomic advances in bioinformatics have refined drug-design strategies, by focusing on the reduction of serious side-effects through the identification of enzymatic targets. We consider the problem of identifying the enzymes (i.e., drug targets), whose inhibition will stop the production of a given target set of compounds, while eliminating minimal number of non-target compounds. An exhaustive evaluation of all possible enzyme combinations to find the optimal solution subset may become computationally infeasible for very large metabolic networks. We propose a scalable iterative algorithm which computes a sub-optimal solution within reasonable time-bounds. Our algorithm is based on the intuition that we can arrive at a solution close to the optimal one by tracing backward from the target compounds. It evaluates immediate precursors of the target compounds and iteratively moves backwards to identify the enzymes whose inhibition will stop the production of the target compounds while incurring minimum side-effects. We show that our algorithm converges to a sub-optimal solution within a finite number of such iterations. Our experiments on the E. Coli metabolic network show that the average accuracy of our method deviates from that of the exhaustive search only by 0.02%. Our iterative algorithm is highly scalable. It can solve the problem for the entire metabolic network of Escherichia Coli in less than 10 seconds.
authors.affiliation: Department of Computer and Information Science and Engineering, University of Florida, Gainesville, FL 32611, USA. psridhar@cise.ufl.edu
authors.forename: Padmavati
authors.initials: P
authors.lastname: Sridhar
authors.forename: Tamer
authors.initials: T
authors.lastname: Kahveci
authors.forename: Sanjay
authors.initials: S
authors.lastname: Ranka
mesh_terms: D000465:Algorithms; D019295:Computational Biology; D015195:Drug Design; D004791:Enzyme Inhibitors / Q000737:chemistry / Q000494:pharmacology; D004926:Escherichia coli / Q000187:drug effects / Q000378:metabolism; D008660:Metabolism
chemical_list: D004791:Enzyme Inhibitors