Department of Computer Science, New Mexico State University, Las Cruces, New Mexico, United States of America.
PLoS One. 2010 Feb 24;5(2):e9331. doi: 10.1371/journal.pone.0009331.
Optimal selection of multiple regulatory genes, known as targets, for deletion to enhance or suppress the activities of downstream genes or metabolites is an important problem in genetic engineering. Such problems become more feasible to address in silico due to the availability of more realistic dynamical system models of gene regulatory and metabolic networks. The goal of the computational problem is to search for a subset of genes to knock out so that the activity of a downstream gene or a metabolite is optimized.
METHODOLOGY/PRINCIPAL FINDINGS: Based on discrete dynamical system modeling of gene regulatory networks, an integer programming problem is formulated for the optimal in silico target gene deletion problem. In the first result, the integer programming problem is proved to be NP-hard and equivalent to a nonlinear programming problem. In the second result, a heuristic algorithm, called GKONP, is designed to approximate the optimal solution, involving an approach to prune insignificant terms in the objective function, and the parallel differential evolution algorithm. In the third result, the effectiveness of the GKONP algorithm is demonstrated by applying it to a discrete dynamical system model of the yeast pheromone pathways. The empirical accuracy and time efficiency are assessed in comparison to an optimal, but exhaustive search strategy.
Although the in silico target gene deletion problem has enormous potential applications in genetic engineering, one must overcome the computational challenge due to its NP-hardness. The presented solution, which has been demonstrated to approximate the optimal solution in a practical amount of time, is among the few that address the computational challenge. In the experiment on the yeast pheromone pathways, the identified best subset of genes for deletion showed advantage over genes that were selected empirically. Once validated in vivo, the optimal target genes are expected to achieve higher genetic engineering effectiveness than a trial-and-error procedure.
选择多个调控基因（即靶点）进行删除以增强或抑制下游基因或代谢物的活性是遗传工程中的一个重要问题。由于基因调控和代谢网络的更现实动力学系统模型的可用性，这些问题在计算机上更易于解决。计算问题的目标是搜索要敲除的基因子集，以使下游基因或代谢物的活性得到优化。
方法/主要发现：基于基因调控网络的离散动力学系统建模，针对最佳计算机靶点基因删除问题，提出了一个整数规划问题。在第一个结果中，证明了整数规划问题是 NP-hard 的，并与非线性规划问题等价。在第二个结果中，设计了一种启发式算法 GKONP，用于近似最优解，涉及到修剪目标函数中不重要项的方法和并行差分进化算法。在第三个结果中，通过将其应用于酵母信息素途径的离散动力学系统模型，证明了 GKONP 算法的有效性。与最优但详尽的搜索策略相比，评估了其经验准确性和时间效率。
尽管计算机靶点基因删除问题在遗传工程中具有巨大的潜在应用，但由于其 NP-hard 性，必须克服计算挑战。所提出的解决方案已被证明可以在实际的时间内近似最优解，是解决计算挑战的少数方案之一。在酵母信息素途径的实验中，所确定的最佳基因删除子集显示出优于经验选择的基因的优势。一旦在体内得到验证，预计最优靶点基因将比试错程序实现更高的遗传工程效果。
