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.