Bioinformatics Research Group/Artificial Intelligence Center, SRI International, 333 Ravenswood Ave, Menlo Park 94025, USA.
BMC Bioinformatics. 2014 Jun 28;15:225. doi: 10.1186/1471-2105-15-225.
Flux Balance Analysis (FBA) is a genome-scale computational technique for modeling the steady-state fluxes of an organism's reaction network. When the organism's reaction network needs to be completed to obtain growth using FBA, without relying on the genome, the completion process is called reaction gap-filling. Currently, computational techniques used to gap-fill a reaction network compute the minimum set of reactions using Mixed-Integer Linear Programming (MILP). Depending on the number of candidate reactions used to complete the model, MILP can be computationally demanding.
We present a computational technique, called FastGapFilling, that efficiently completes a reaction network by using only Linear Programming, not MILP. FastGapFilling creates a linear program with all candidate reactions, an objective function based on their weighted fluxes, and a variable weight on the biomass reaction: no integer variable is used. A binary search is performed by modifying the weight applied to the flux of the biomass reaction, and solving each corresponding linear program, to try reducing the number of candidate reactions to add to the network to generate a working model. We show that this method has proved effective on a series of incomplete E. coli and yeast models with, in some cases, a three orders of magnitude execution speedup compared with MILP. We have implemented FastGapFilling in MetaFlux as part of Pathway Tools (version 17.5), which is freely available to academic users, and for a fee to commercial users. Download from: biocyc.org/download.shtml.
The computational technique presented is very efficient allowing interactive completion of reaction networks of FBA models. Computational techniques based on MILP cannot offer such fast and interactive completion.
通量平衡分析（FBA）是一种用于对生物体反应网络的稳态通量进行建模的基因组规模的计算技术。当生物体的反应网络需要使用 FBA 完成以获得生长时，而不依赖于基因组，那么完成过程被称为反应间隙填补。目前，用于填补反应网络的计算技术使用混合整数线性规划（MILP）计算使用的最小反应集。根据用于完成模型的候选反应的数量，MILP 可能需要大量的计算资源。
我们提出了一种计算技术，称为 FastGapFilling，它通过仅使用线性规划而不是 MILP 来有效地完成反应网络。FastGapFilling 为所有候选反应创建一个线性规划，一个基于它们加权通量的目标函数，以及一个生物质反应的变量权重：不使用整数变量。通过修改应用于生物质反应通量的权重来执行二进制搜索，并解决每个对应的线性规划，尝试减少要添加到网络以生成工作模型的候选反应的数量。我们表明，该方法在一系列不完整的大肠杆菌和酵母模型上已经证明是有效的，在某些情况下，与 MILP 相比，执行速度提高了三个数量级。我们已经在 MetaFlux 中实现了 FastGapFilling，作为 Pathway Tools（版本 17.5）的一部分，该软件可供学术用户免费使用，商业用户需要付费。可从 biocyc.org/download.shtml 下载。
所提出的计算技术非常高效，允许交互式完成 FBA 模型的反应网络。基于 MILP 的计算技术无法提供如此快速和交互式的完成。
