NIBBS-Search for Fast and Accurate Prediction of Phenotype-Biased Metabolic Systems

Understanding of genotype-phenotype associations is important not only for furthering our knowledge on internal cellular processes, but also essential for providing the foundation necessary for genetic engineering of microorganisms for industrial use (e.g., production of bioenergy or biofuels). However, genotype-phenotype associations alone do not provide enough information to alter an organism's genome to either suppress or exhibit a phenotype. It is important to look at the phenotype-related genes in the context of the genome-scale network to understand how the genes interact with other genes in the organism. Identification of metabolic subsystems involved in the expression of the phenotype is one way of placing the phenotype-related genes in the context of the entire network. A metabolic system refers to a metabolic network subgraph; nodes are compounds and edges labels are the enzymes that catalyze the reaction. The metabolic subsystem could be part of a single metabolic pathway or span parts of multiple pathways. Arguably, comparative genome-scale metabolic network analysis is a promising strategy to identify these phenotype-related metabolic subsystems. Network Instance-Based Biased Subgraph Search (NIBBS) is a graph-theoretic method for genome-scale metabolic network comparative analysis that can identify metabolic systems that are statistically biased toward phenotype-expressing organismal networks. We set up experiments with target phenotypes like hydrogen production, TCA expression, and acid-tolerance. We show via extensive literature search that some of the resulting metabolic subsystems are indeed phenotype-related and formulate hypotheses for other systems in terms of their role in phenotype expression. NIBBS is also orders of magnitude faster than MULE, one of the most efficient maximal frequent subgraph mining algorithms that could be adjusted for this problem. Also, the set of phenotype-biased metabolic systems output by NIBBS comes very close to the set of phenotype-biased subgraphs output by an exact maximally-biased subgraph enumeration algorithm ( MBS-Enum ). The code (NIBBS and the module to visualize the identified subsystems) is available at http://freescience.org/cs/NIBBS.对基因型-表型关联（genotype-phenotype associations）的解析，不仅有助于深化我们对细胞内部生理过程的认知，更为工业用微生物的基因工程（例如生物能源或生物燃料生产）提供了不可或缺的基础支撑。然而，仅依靠基因型-表型关联信息，不足以对生物体基因组进行改造以实现表型的抑制或表达。需将表型相关基因置于基因组规模网络的语境中进行分析，才能明晰这些基因与生物体内其他基因的相互作用机制。鉴定参与表型表达的代谢子系统，正是将表型相关基因纳入整个网络语境进行分析的有效途径之一。代谢系统指代谢网络子图：其中节点代表化合物，边的标签为催化对应反应的酶。代谢子系统既可以隶属于单条代谢通路，也可以横跨多条通路的部分片段。可以说，比较基因组规模代谢网络分析是鉴定此类表型相关代谢子系统的极具前景的研究策略。基于网络实例的偏向性子图搜索算法（Network Instance-Based Biased Subgraph Search, NIBBS）是一种用于基因组规模代谢网络比较分析的图论方法，可识别出在表达目标表型的生物体网络中呈现统计偏向性的代谢系统。我们以产氢、三羧酸（TCA）循环表达以及耐酸性等为目标表型开展了实验。经大量文献检索验证，部分得到的代谢子系统确实与对应表型相关；同时针对其余子系统，我们就其在表型表达中的潜在作用提出了相关假说。相较于可针对该问题进行适配调整的当前主流高效最大频繁子图挖掘算法之一MULE，NIBBS的运行速度快数个数量级。此外，NIBBS输出的表型偏向性代谢系统集合，与精确最大偏向子图枚举算法（MBS-Enum）所得到的表型偏向性子图集合高度吻合。本研究的相关代码（包含NIBBS算法及已鉴定子系统的可视化模块）可于http://freescience.org/cs/NIBBS获取。