COMPUTER SCIENCE COLLOQUIUM

Declarative approaches to hypergraph reconstruction

Philipp Peters Department of Mathematics and Computer Science University of Southern Denmark, Denmark

Tuesday, 05 February, 2013 at 14:15 IMADA's Seminar Room

ABSTRACT

In a living cell, metabolic and physical processes constantly convert chemical compounds, e.g. to provide energy or to regulate the cells behavior. This metabolism is often denoted the cell's metabolic network and comprises its chemical reactions and their regulation.

The analysis of naturally occurring metabolic networks is of significant interest. Such a metabolic network can be described as a directed hypergraph. From any hypergraph, two directed graphs \emph{S} and \emph{R} can be derived. The so called \emph{Species Graph S} contains the transitions of chemical species into other species, determined by the given reaction mechanism; the \emph{Reaction Graph R} contains the transitions from one reaction to another.

Looking in the other direction, a natural question arises: given instances of \emph{S} and \emph{R}, does a hypergraph (i.e., a metabolic network) exist from which these two matrices can be derived? We called this problem the \emph{Compound-Reaction-Reconstruction-Problem (CRRP(\emph{S},\emph{R}))}. We could show, that the general binary case is \emph{NP-complete} and present these result and furthermore empirical studies. We compare different solving methods for this problem and give an outline to near future plans.

Host:

---

SDU HOME | IMADA HOME | Previous Page

---

Daniel Merkle