Department of Computer and Information Science and Engineering, University of Florida, CSE Building, Room E436, Gainesville, FL 32611-6125, USA.
IEEE/ACM Trans Comput Biol Bioinform. 2011 May-Jun;8(3):732-47. doi: 10.1109/TCBB.2010.41.
Metabolic pathways show the complex interactions among enzymes that transform chemical compounds. The state of a metabolic pathway can be expressed as a vector, which denotes the yield of the compounds or the flux in that pathway at a given time. The steady state is a state that remains unchanged over time. Altering the state of the metabolism is very important for many applications such as biomedicine, biofuels, food industry, and cosmetics. The goal of the enzymatic target identification problem is to identify the set of enzymes whose knockouts lead the metabolism to a state that is close to a given goal state. Given that the size of the search space is exponential in the number of enzymes, the target identification problem is very computationally intensive. We develop efficient algorithms to solve the enzymatic target identification problem in this paper. Unlike existing algorithms, our method works for a broad set of metabolic network models. We measure the effect of the knockouts of a set of enzymes as a function of the deviation of the steady state of the pathway after their knockouts from the goal state. We develop two algorithms to find the enzyme set with minimal deviation from the goal state. The first one is a traversal approach that explores possible solutions in a systematic way using a branch and bound method. The second one uses genetic algorithms to derive good solutions from a set of alternative solutions iteratively. Unlike the former one, this one can run for very large pathways. Our experiments show that our algorithms' results follow those obtained in vitro in the literature from a number of applications. They also show that the traversal method is a good approximation of the exhaustive search algorithm and it is up to 11 times faster than the exhaustive one. This algorithm runs efficiently for pathways with up to 30 enzymes. For large pathways, our genetic algorithm can find good solutions in less than 10 minutes.
代谢途径展示了酶之间复杂的相互作用，这些酶可以转化化合物。代谢途径的状态可以表示为一个向量，表示在给定时间内化合物的产量或该途径中的通量。稳态是指随时间保持不变的状态。改变代谢状态对于许多应用非常重要，如生物医学、生物燃料、食品工业和化妆品。酶靶标识别问题的目标是确定一组酶，其敲除会导致代谢状态接近给定的目标状态。由于搜索空间的大小在酶的数量上呈指数增长，因此靶标识别问题计算量非常大。在本文中，我们开发了有效的算法来解决酶靶标识别问题。与现有算法不同，我们的方法适用于广泛的代谢网络模型。我们将一组酶的敲除效果衡量为其敲除后途径的稳态与目标状态之间的偏差的函数。我们开发了两种算法来找到与目标状态偏差最小的酶集。第一种是遍历方法，它使用分支定界法以系统的方式探索可能的解决方案。第二种使用遗传算法从一组替代解决方案中迭代地得到好的解决方案。与前者不同的是，这种方法可以适用于非常大的途径。我们的实验表明，我们的算法的结果与文献中从许多应用中获得的体外结果相吻合。它们还表明，遍历方法是穷举搜索算法的良好近似，其速度比穷举搜索算法快 11 倍。该算法可高效运行，最多可达 30 种酶的途径。对于大型途径，我们的遗传算法可以在不到 10 分钟内找到好的解决方案。
