Exploiting balanced trees in the computation of elementary flux modes via breadth-first search

[摘要] In order to rationally design bacteria to produce large quantities of their precious metabolic by-products, we must first understand the metabolic pathways that lead from a starting material (e.g., glucose) to a metabolic product (e.g., hydrogen). Given a set of reactions, elementary flux modes can be used to mathematically define all metabolic pathways that are stoichiometrically and thermodynamically feasible. The elementary flux modes are the intersections of positive halfspaces, or the vertices of a convex polyhedron. Although linear programing has long been used to examine polyhedra, biologists have yet to use linear programming's full functionality to rationally design bacteria. The simplex method is one relevant linear programming function that pivots from one vertex of a polyhedron to another. The breadth-first search uses a simplex-like pivot to list every possible vertex of a polyhedron. When listing a polyhedron's vertices, it is important not to repeat vertices and thus a robust search algorithm is needed. I have employed balanced trees to speed up the breadth-first search. Specific examples, including the maximization of succinate production, will be investigated and the vertices of the mixed acid fermentation process in E. coli will be enumerated. The open source Matlab code along with a GUI will be provided, as well as links to m-files, which are available on the Internet.

[发布机构] Rice University

[效力级别] research