Chemical transformation motifs: modelling pathways as integer hyperflows

Jakob L. Andersen, Christoph Flamm, Daniel Merkle, Peter F. Stadler

Research output: Contribution to journalJournal articleResearchpeer-review

119 Downloads (Pure)

Abstract

We present an elaborate framework for formally modelling pathways in chemical reaction networks on a mechanistic level. Networks are modelled mathematically as directed multi-hypergraphs, with vertices corresponding to molecules and hyperedges to reactions. Pathways are modelled as integer hyperflows and we expand the network model by detailed routing constraints. In contrast to the more traditional approaches like Flux Balance Analysis or Elementary Mode analysis we insist on integer-valued flows. While this choice makes it necessary to solve possibly hard integer linear programs, it has the advantage that more detailed mechanistic questions can be formulated. It is thus possible to query networks for general transformation motifs, and to automatically enumerate optimal and near-optimal pathways. Similarities and differences between our work and traditional approaches in metabolic network analysis are discussed in detail. To demonstrate the applicability of the mathematical framework to real-life problems we first explore the design space of possible non-oxidative glycolysis pathways and show that recent manually designed pathways can be further optimized. We then use a model of sugar chemistry to investigate pathways in the autocatalytic formose process. A graph transformation-based approach is used to automatically generate the reaction networks of interest.

Original languageEnglish
JournalIEEE/ACM Transactions on Computational Biology and Bioinformatics
Volume16
Issue number2
Pages (from-to)510-523
ISSN1545-5963
DOIs
Publication statusPublished - 1. Mar 2019

Fingerprint

Glycolysis
Metabolic Networks and Pathways
Pathway
Integer
Electric network analysis
Modeling
Sugars
Chemical reactions
Fluxes
Molecules
Chemical Reaction Networks
Reaction Network
Graph Transformation
Metabolic Network
Integer Program
Network Analysis
Hypergraph
Linear Program
Chemistry
Network Model

Keywords

  • autocatalysis
  • Biological system modeling
  • Chemicals
  • chemistry
  • Computational modeling
  • Computer science
  • formose
  • hyperflow
  • integer linear programming
  • Mathematical model
  • network flow
  • non-oxidative glycolysis pathway
  • Pathway
  • reaction network
  • Visualization

Cite this

@article{b5d5e0636de24e8a84d9c05fd977ade6,
title = "Chemical transformation motifs: modelling pathways as integer hyperflows",
abstract = "We present an elaborate framework for formally modelling pathways in chemical reaction networks on a mechanistic level. Networks are modelled mathematically as directed multi-hypergraphs, with vertices corresponding to molecules and hyperedges to reactions. Pathways are modelled as integer hyperflows and we expand the network model by detailed routing constraints. In contrast to the more traditional approaches like Flux Balance Analysis or Elementary Mode analysis we insist on integer-valued flows. While this choice makes it necessary to solve possibly hard integer linear programs, it has the advantage that more detailed mechanistic questions can be formulated. It is thus possible to query networks for general transformation motifs, and to automatically enumerate optimal and near-optimal pathways. Similarities and differences between our work and traditional approaches in metabolic network analysis are discussed in detail. To demonstrate the applicability of the mathematical framework to real-life problems we first explore the design space of possible non-oxidative glycolysis pathways and show that recent manually designed pathways can be further optimized. We then use a model of sugar chemistry to investigate pathways in the autocatalytic formose process. A graph transformation-based approach is used to automatically generate the reaction networks of interest.",
keywords = "autocatalysis, Biological system modeling, Chemicals, chemistry, Computational modeling, Computer science, formose, hyperflow, integer linear programming, Mathematical model, network flow, non-oxidative glycolysis pathway, Pathway, reaction network, Visualization",
author = "Andersen, {Jakob L.} and Christoph Flamm and Daniel Merkle and Stadler, {Peter F.}",
year = "2019",
month = "3",
day = "1",
doi = "10.1109/TCBB.2017.2781724",
language = "English",
volume = "16",
pages = "510--523",
journal = "I E E E - A C M Transactions on Computational Biology and Bioinformatics",
issn = "1545-5963",
publisher = "I E E E",
number = "2",

}

Chemical transformation motifs : modelling pathways as integer hyperflows. / Andersen, Jakob L.; Flamm, Christoph; Merkle, Daniel; Stadler, Peter F.

In: IEEE/ACM Transactions on Computational Biology and Bioinformatics, Vol. 16, No. 2, 01.03.2019, p. 510-523.

Research output: Contribution to journalJournal articleResearchpeer-review

TY - JOUR

T1 - Chemical transformation motifs

T2 - modelling pathways as integer hyperflows

AU - Andersen, Jakob L.

AU - Flamm, Christoph

AU - Merkle, Daniel

AU - Stadler, Peter F.

PY - 2019/3/1

Y1 - 2019/3/1

N2 - We present an elaborate framework for formally modelling pathways in chemical reaction networks on a mechanistic level. Networks are modelled mathematically as directed multi-hypergraphs, with vertices corresponding to molecules and hyperedges to reactions. Pathways are modelled as integer hyperflows and we expand the network model by detailed routing constraints. In contrast to the more traditional approaches like Flux Balance Analysis or Elementary Mode analysis we insist on integer-valued flows. While this choice makes it necessary to solve possibly hard integer linear programs, it has the advantage that more detailed mechanistic questions can be formulated. It is thus possible to query networks for general transformation motifs, and to automatically enumerate optimal and near-optimal pathways. Similarities and differences between our work and traditional approaches in metabolic network analysis are discussed in detail. To demonstrate the applicability of the mathematical framework to real-life problems we first explore the design space of possible non-oxidative glycolysis pathways and show that recent manually designed pathways can be further optimized. We then use a model of sugar chemistry to investigate pathways in the autocatalytic formose process. A graph transformation-based approach is used to automatically generate the reaction networks of interest.

AB - We present an elaborate framework for formally modelling pathways in chemical reaction networks on a mechanistic level. Networks are modelled mathematically as directed multi-hypergraphs, with vertices corresponding to molecules and hyperedges to reactions. Pathways are modelled as integer hyperflows and we expand the network model by detailed routing constraints. In contrast to the more traditional approaches like Flux Balance Analysis or Elementary Mode analysis we insist on integer-valued flows. While this choice makes it necessary to solve possibly hard integer linear programs, it has the advantage that more detailed mechanistic questions can be formulated. It is thus possible to query networks for general transformation motifs, and to automatically enumerate optimal and near-optimal pathways. Similarities and differences between our work and traditional approaches in metabolic network analysis are discussed in detail. To demonstrate the applicability of the mathematical framework to real-life problems we first explore the design space of possible non-oxidative glycolysis pathways and show that recent manually designed pathways can be further optimized. We then use a model of sugar chemistry to investigate pathways in the autocatalytic formose process. A graph transformation-based approach is used to automatically generate the reaction networks of interest.

KW - autocatalysis

KW - Biological system modeling

KW - Chemicals

KW - chemistry

KW - Computational modeling

KW - Computer science

KW - formose

KW - hyperflow

KW - integer linear programming

KW - Mathematical model

KW - network flow

KW - non-oxidative glycolysis pathway

KW - Pathway

KW - reaction network

KW - Visualization

U2 - 10.1109/TCBB.2017.2781724

DO - 10.1109/TCBB.2017.2781724

M3 - Journal article

C2 - 29990045

AN - SCOPUS:85039800502

VL - 16

SP - 510

EP - 523

JO - I E E E - A C M Transactions on Computational Biology and Bioinformatics

JF - I E E E - A C M Transactions on Computational Biology and Bioinformatics

SN - 1545-5963

IS - 2

ER -