Constraint programming approaches for finding conserved metabolic and genomic patterns
本文针对代谢网络与基因组关系这一NP难问题，提出基于约束规划的方法，识别代谢网络中由邻近基因产物催化的反应链，用于不同物种间的比较。
Systems biology is a relatively new field of science that studies living organisms as they are found in nature. This approach differs from previous approaches by combining information from different fields (biology, physiology, biochemistry, etc.) to understand the functions of these organisms, requiring the use of specialized and efficient treatment and analysis algorithms. Many approaches for comparing biological networks are based on graph models in which the vertices represent biological components and the edges or arcs represent interactions between components. This paper focuses on an NP -hard problem related to heterogeneous biological networks. The main objective is to study the relationship between metabolism and genome. The metabolic network is modeled by a directed graph D and gene proximity is modeled by an undirected graph G ( D and G are built on the same set of vertices). The proposed approaches (based on constraint programming) identify paths or trails in D whose vertices induce a connected component in G . The paths represent reaction chains in the metabolic network catalyzed by products of neighboring genes in the genome. These biologically significant patterns allow different species to be compared.