Send to

Choose Destination
Pac Symp Biocomput. 2008:291-302.

Mining metabolic networks for optimal drug targets.

Author information

Computer and Information Science and Engineering, University of Florida, Gainesville, FL 32611, USA.


Recent advances in bioinformatics promote drug-design methods that aim to reduce side-effects. Efficient computational methods are required to identify the optimal enzyme-combination (i.e., drug targets) whose inhibition, will achieve the required effect of eliminating a given target set of compounds, while incurring minimal side-effects. We formulate the optimal enzyme-combination identification problem as an optimization problem on metabolic networks. We define a graph based computational damage model that encapsulates the impact of enzymes onto compounds in metabolic networks. We develop a branch-and-bound algorithm, named OPMET, to explore the search space dynamically. We also develop two filtering strategies to prune the search space while still guaranteeing an optimal solution. They compute an upper bound to the number of target compounds eliminated and a lower bound to the side-effect respectively. Our experiments on the human metabolic network demonstrate that the proposed algorithm can accurately identify the target enzymes for known successful drugs in the literature. Our experiments also show that OPMET can reduce the total search time by several orders of magnitude as compared to the exhaustive search.

[Indexed for MEDLINE]
Free full text

Supplemental Content

Full text links

Icon for Pacific Sympsium On Biocomputing
Loading ...
Support Center