Who do we work with?
Our Working Groups
Science Communication
Talks by our Members and Guests
The well-studied class of cographs can be encoded, or explained, by
rooted trees with a 0/1-labeling which, among many other things, can
guide algorithms to solve difficult problems efficiently. A reasonable
and algorithmically promising generalization is to study graphs that
can be explained by more intricate 0/1-labeled rooted networks. To
keep the complexity of such networks in check, it is reasonable to
require that every part of the network actually encodes something of
the graph it explains. In this setting, this means that every vertex
of the network should be a least common ancestor (LCA) of at least
some subset of leaves. In this talk we investigate these so-called
LCA-relevant networks and DAGs, and give a brief summary of how this
purely graph-theoretical notion can be of use in evolutionary biology.
rooted trees with a 0/1-labeling which, among many other things, can
guide algorithms to solve difficult problems efficiently. A reasonable
and algorithmically promising generalization is to study graphs that
can be explained by more intricate 0/1-labeled rooted networks. To
keep the complexity of such networks in check, it is reasonable to
require that every part of the network actually encodes something of
the graph it explains. In this setting, this means that every vertex
of the network should be a least common ancestor (LCA) of at least
some subset of leaves. In this talk we investigate these so-called
LCA-relevant networks and DAGs, and give a brief summary of how this
purely graph-theoretical notion can be of use in evolutionary biology.
https://uni-leipzig.zoom-x.de/j/68993513534?pwd=K9LZZvMm5LPY6rb88FvvdUzqMtjNkE.1
Mathematical modeling is engaged to understand the
complex interactions of bacterial species in the microbial
communities. Based on graph-theoretical approaches, chemical reaction
networks (CRNs) as well as their higher abstraction levels aid to
decipher the metabolic interactions between different microbes and
metabolic pathway usage. However, this represents a major challenge
since identical compounds produced by distinct microorganisms or
metabolic routes are chemical indistinguishable, which is routinely
addressed via isotope labeling experiments. Here, we investigate the
applicability of probabilistic approaches, utilizing especially
continuous-time Markov chains, to simulate distribution of isotopic
labelled material in metabolic networks. To this end, CRNs are
translated into simplified atom transition networks via a step-by-step
assemble of reaction-wise atom transition graphs. Subsequently,
systems of linear differential equations are employed to model
dynamics of positional enrichment, offering low computational costs
for computation of isotope steady state solutions.
complex interactions of bacterial species in the microbial
communities. Based on graph-theoretical approaches, chemical reaction
networks (CRNs) as well as their higher abstraction levels aid to
decipher the metabolic interactions between different microbes and
metabolic pathway usage. However, this represents a major challenge
since identical compounds produced by distinct microorganisms or
metabolic routes are chemical indistinguishable, which is routinely
addressed via isotope labeling experiments. Here, we investigate the
applicability of probabilistic approaches, utilizing especially
continuous-time Markov chains, to simulate distribution of isotopic
labelled material in metabolic networks. To this end, CRNs are
translated into simplified atom transition networks via a step-by-step
assemble of reaction-wise atom transition graphs. Subsequently,
systems of linear differential equations are employed to model
dynamics of positional enrichment, offering low computational costs
for computation of isotope steady state solutions.
https://uni-leipzig.zoom.us/j/62056131398?pwd=DVb6EbHolk91B1WtS4bCyXpCBbBYO6.1#success
In this talk, we explore infinite families of fullerene graphs (cubic
planar graphs containing only pentagonal and hexagonal faces) with small
diameters and symmetries such as C₃ᵥ and tetrahedral symmetry.
In 2013, Andova and Škrekovski conjectured that the diameter of a fullerene
of order *n* is at least ⌊√(5n/3)⌋ − 1, leading to the construction of a
family of fullerene graphs with full icosahedral symmetry that attains this
bound. However, in 2017, Nicodemos and Stehlík disproved the conjecture by
constructing an infinite family of fullerene graphs of order *n* and
diameter √(4n/3), the smallest of which has 300 vertices.
An exhaustive search on fullerenes up to 300 vertices has produced further
counterexamples to both bounds, the smallest of which has 118 vertices, C₃ᵥ
symmetry, and obeys the Isolated Pentagon Rule (IPR).
From such examples we construct two infinite families: one with C₃ᵥ
symmetry and one with tetrahedral symmetry.
planar graphs containing only pentagonal and hexagonal faces) with small
diameters and symmetries such as C₃ᵥ and tetrahedral symmetry.
In 2013, Andova and Škrekovski conjectured that the diameter of a fullerene
of order *n* is at least ⌊√(5n/3)⌋ − 1, leading to the construction of a
family of fullerene graphs with full icosahedral symmetry that attains this
bound. However, in 2017, Nicodemos and Stehlík disproved the conjecture by
constructing an infinite family of fullerene graphs of order *n* and
diameter √(4n/3), the smallest of which has 300 vertices.
An exhaustive search on fullerenes up to 300 vertices has produced further
counterexamples to both bounds, the smallest of which has 118 vertices, C₃ᵥ
symmetry, and obeys the Isolated Pentagon Rule (IPR).
From such examples we construct two infinite families: one with C₃ᵥ
symmetry and one with tetrahedral symmetry.
https://uni-leipzig.zoom-x.de/j/66192876787?pwd=ZUdHrbhTvYTmbP7mDNBbbGjmDjCkCF.1
In chemical networks a "chemical walk" can be defined as a sequence of chemical reactions r1, r2, r3,..., rn, that follows certain constraints. One of these constraints is that there must be a non-empty intersection between the set of products of reaction rj and the set of reactants of the subsequent reaction r(j+1). This condition is important when studying the evolution of the chemical space, as it can be used to characterize the social/collaborative aspect of chemist performance, making it a worthwhile topic of study. In this talk, I will show some of the preliminary results we have regarding this matter.
Understanding evolutionary relationships, particularly in the context of hybridization and horizontal gene transfer, requires inferring phylogenetic networks rather than traditional trees. Recent methods based on quartet concordance factors have addressed the challenges of inferring such networks, where these factors represent the probabilities of 4-taxon relationships within gene trees. Previous research has shown that certain network topologies and numerical parameters can be identified, however, gaps remain in understanding the full topology of level-1 phylogenetic networks under the network multispecies coalescent model. In this talk, we investigate what level-1 network features are identifiable by studying the ideals defined by quartet concordance factors.
We address both the identifiability of the network, as well as the numerical parameters, and will give answers to a number of identifiability problems related to the 3-cycles of the network.
Joint work with Elizabeth S. Allman, Hector Baños and John A. Rhodes
We address both the identifiability of the network, as well as the numerical parameters, and will give answers to a number of identifiability problems related to the 3-cycles of the network.
Joint work with Elizabeth S. Allman, Hector Baños and John A. Rhodes
https://uni-leipzig.zoom-x.de/j/67188613169?pwd=d1lEbzRDWjJkdmxmOW1uYTBPblM2dz09
A nut graph is a simple graph for which the adjacency matrix has a single zero eigenvalue
such that all nonzero kernel eigenvectors have no zero entry.
If the isolated vertex is excluded as trivial, nut graphs have seven or more vertices; they
are connected, non-bipartite, and have no leaves.
Nut graphs have been established in the literature for quite some time: they were
introduced in 1998 by Sciriha and Gutman. However, only recently important chemical
applications involving this class of graphs were uncovered, which makes them
quite attractive for further investigation and research.
In this talk, we present some symmetry properties of nut graphs. We show that a nut
graph $G$ always has at least one more edge orbit than it has vertex orbits. In particular,
edge-transitive nut graphs do not exist. Moreover, we give infinite families of
vertex-transitive nut graphs with two orbits of edges, and infinite families of nut graphs
with two orbits of vertices and three of edges.
Several constructions for nut graphs from smaller starting graphs are known: double subdivision
of a bridge, four-fold subdivision of an edge, a construction for extrusion of a vertex with
preservation of the degree sequence (the so-called Fowler construction). To these we add
multiplier constructions that yield nut graphs from regular graphs (that are not necessarily nut graphs).
Finally, we show by construction that every finite group can be represented as the group of
automorphisms of infinitely many nut graphs. It is further shown that these graphs may be required
to be regular; the cases where the degree is required to be $8, 12, 16, 20$ or $24$ are realised explicitly.
This is joint work with Tomaž Pisanski and Patrick W. Fowler.
such that all nonzero kernel eigenvectors have no zero entry.
If the isolated vertex is excluded as trivial, nut graphs have seven or more vertices; they
are connected, non-bipartite, and have no leaves.
Nut graphs have been established in the literature for quite some time: they were
introduced in 1998 by Sciriha and Gutman. However, only recently important chemical
applications involving this class of graphs were uncovered, which makes them
quite attractive for further investigation and research.
In this talk, we present some symmetry properties of nut graphs. We show that a nut
graph $G$ always has at least one more edge orbit than it has vertex orbits. In particular,
edge-transitive nut graphs do not exist. Moreover, we give infinite families of
vertex-transitive nut graphs with two orbits of edges, and infinite families of nut graphs
with two orbits of vertices and three of edges.
Several constructions for nut graphs from smaller starting graphs are known: double subdivision
of a bridge, four-fold subdivision of an edge, a construction for extrusion of a vertex with
preservation of the degree sequence (the so-called Fowler construction). To these we add
multiplier constructions that yield nut graphs from regular graphs (that are not necessarily nut graphs).
Finally, we show by construction that every finite group can be represented as the group of
automorphisms of infinitely many nut graphs. It is further shown that these graphs may be required
to be regular; the cases where the degree is required to be $8, 12, 16, 20$ or $24$ are realised explicitly.
This is joint work with Tomaž Pisanski and Patrick W. Fowler.
https://uni-leipzig.zoom.us/j/68659155596?pwd=ZzJWVWF1WCtqSndaNi9GVFZ4ZWx2UT09
A nut graph is a simple graph for which the adjacency matrix has a single zero eigenvalue
such that all nonzero kernel eigenvectors have no zero entry.
If the isolated vertex is excluded as trivial, nut graphs have seven or more vertices; they
are connected, non-bipartite, and have no leaves.
Nut graphs have been established in the literature for quite some time: they were
introduced in 1998 by Sciriha and Gutman. However, only recently important chemical
applications involving this class of graphs were uncovered, which makes them
quite attractive for further investigation and research.
In this talk, we present some symmetry properties of nut graphs. We show that a nut
graph $G$ always has at least one more edge orbit than it has vertex orbits. In particular,
edge-transitive nut graphs do not exist. Moreover, we give infinite families of
vertex-transitive nut graphs with two orbits of edges, and infinite families of nut graphs
with two orbits of vertices and three of edges.
Several constructions for nut graphs from smaller starting graphs are known: double subdivision
of a bridge, four-fold subdivision of an edge, a construction for extrusion of a vertex with
preservation of the degree sequence (the so-called Fowler construction). To these we add
multiplier constructions that yield nut graphs from regular graphs (that are not necessarily nut graphs).
Finally, we show by construction that every finite group can be represented as the group of
automorphisms of infinitely many nut graphs. It is further shown that these graphs may be required
to be regular; the cases where the degree is required to be $8, 12, 16, 20$ or $24$ are realised explicitly.
This is joint work with Tomaž Pisanski and Patrick W. Fowler.
such that all nonzero kernel eigenvectors have no zero entry.
If the isolated vertex is excluded as trivial, nut graphs have seven or more vertices; they
are connected, non-bipartite, and have no leaves.
Nut graphs have been established in the literature for quite some time: they were
introduced in 1998 by Sciriha and Gutman. However, only recently important chemical
applications involving this class of graphs were uncovered, which makes them
quite attractive for further investigation and research.
In this talk, we present some symmetry properties of nut graphs. We show that a nut
graph $G$ always has at least one more edge orbit than it has vertex orbits. In particular,
edge-transitive nut graphs do not exist. Moreover, we give infinite families of
vertex-transitive nut graphs with two orbits of edges, and infinite families of nut graphs
with two orbits of vertices and three of edges.
Several constructions for nut graphs from smaller starting graphs are known: double subdivision
of a bridge, four-fold subdivision of an edge, a construction for extrusion of a vertex with
preservation of the degree sequence (the so-called Fowler construction). To these we add
multiplier constructions that yield nut graphs from regular graphs (that are not necessarily nut graphs).
Finally, we show by construction that every finite group can be represented as the group of
automorphisms of infinitely many nut graphs. It is further shown that these graphs may be required
to be regular; the cases where the degree is required to be $8, 12, 16, 20$ or $24$ are realised explicitly.
This is joint work with Tomaž Pisanski and Patrick W. Fowler.
Autocatalytic chemical networks are dynamical systems whose
linearization around zero
has a positive Lyapunov exponent; this exponent gives the growth rate
of the system in the diluted regime, i.e. for near-zero
concentrations.
We prove here optimal estimates on the growth rate and on the
corresponding quasi- stationary distribution of species, yielding
their orders of magnitude as a function of kinetic time scales. The
estimates are based on a multi-time scale decomposition algorithm
inspired from field theory, and give accurate predictions for the
collective time behavior of the concentrations. Conversely, it is in
principle possible to reconstruct to a large extent the reaction
network and kinetic time scales from a series of carefully devised
experiments.
linearization around zero
has a positive Lyapunov exponent; this exponent gives the growth rate
of the system in the diluted regime, i.e. for near-zero
concentrations.
We prove here optimal estimates on the growth rate and on the
corresponding quasi- stationary distribution of species, yielding
their orders of magnitude as a function of kinetic time scales. The
estimates are based on a multi-time scale decomposition algorithm
inspired from field theory, and give accurate predictions for the
collective time behavior of the concentrations. Conversely, it is in
principle possible to reconstruct to a large extent the reaction
network and kinetic time scales from a series of carefully devised
experiments.
https://uni-leipzig.zoom.us/j/64504129528?pwd=ZmVMTnNlN2ZzK1FRUDAzVTZnZEVVdz09
Understanding genomes' evolutionary history is key to comprehending genes' role in species diversification and adaptation. Moreover, identifying ortholog and paralog genes is fundamental for comparative biology studies. Still, detecting orthology through sequence similarity remains challenging and computationally intensive for gene families containing numerous duplications and losses.
In this talk, I will first introduce REvolutionH-tl, a tool designed for orthology prediction and reconstruction of evolutionary histories free of horizontal gene transfers. Furthermore, I show how REvolutionH-tl can be used to estimate the evolution of antibiotic-resistance genes in a selected group of bacteria.
REvolutionH-tl employs a novel graph-based method to identify biologically plausible gene best-matches, as well as determine orthology and paralogy relationships. This information naturally entails knowledge about gene and species tree topology, which is further reconstructed and unified in an evolutionary scenario that explicitly delineates gene evolution across species.
The accuracy of REvolutionH-tl is comparable to competing tools at substantially reduced computational cost. It is freely available at https://pypi.org/project/revolutionhtl/. REvolutionH-tl stands as a potent addition to the toolkit of comparative genomics researchers. Its significance stands out in the age of massive genome sequencing, where efficient methods to organize and make sense of thousands of genes across numerous species are indispensable.
In this talk, I will first introduce REvolutionH-tl, a tool designed for orthology prediction and reconstruction of evolutionary histories free of horizontal gene transfers. Furthermore, I show how REvolutionH-tl can be used to estimate the evolution of antibiotic-resistance genes in a selected group of bacteria.
REvolutionH-tl employs a novel graph-based method to identify biologically plausible gene best-matches, as well as determine orthology and paralogy relationships. This information naturally entails knowledge about gene and species tree topology, which is further reconstructed and unified in an evolutionary scenario that explicitly delineates gene evolution across species.
The accuracy of REvolutionH-tl is comparable to competing tools at substantially reduced computational cost. It is freely available at https://pypi.org/project/revolutionhtl/. REvolutionH-tl stands as a potent addition to the toolkit of comparative genomics researchers. Its significance stands out in the age of massive genome sequencing, where efficient methods to organize and make sense of thousands of genes across numerous species are indispensable.
Chemical reaction networks (CRNs) play a central role in the mathematical modeling of complex systems due to their capacity to capture a wide range of nonlinear phenomena. Autocatalysis is a topological feature with essential consequences for dynamical organization in CRNs for conceptual, theoretical, and practical reasons. In this talk, I will review different definitions of autocatalysis and discuss the polyhedral geometry induced by the minimal autocatalytic subnetworks (MASs) on the stoichiometric subspace. I will discuss linear-programming algorithms for exhaustively enumerating and a scheme for visualizing the list of MASs in a generic CRN. Next, I will introduce a formal paradigm for coarse-graining realistic biochemical reactions using their conservation laws and display the ‘combinatorial explosion’ of MASs in fully connected hypergraphs of CRNs with one conservation law. Finally, I will discuss applications of autocatalysis in understanding the origins of life and economics. (For details, see https://arxiv.org/abs/2303.14238 .)
The modular decomposition (MD) of an undirected graph G is a natural
construction to capture key features of G in terms of a rooted labeled tree
(T,t) whose vertices are labeled as "series" (1), "parallel" (0) or "prime".
If a graph G does not contain prime modules, then all structural information of G
can be directly derived from its MD tree (T,t). As a consequence, many hard
problems become polynomial-time solvable on graphs without prime modules, since
the MD tree serves as a guide for algorithms to find efficient exact solutions
(e.g.\ for optimal colorings, maximum clique, isomorphism test, ... ).
However, the class of graphs without prime modules (aka cographs) is rather
restricted. We introduce here the novel concept of explicit modular decomposition
that aims at replacing "prime" vertices in the MD tree by suitable substructures
to obtain 0/1-labeled networks (N,t). Understanding which graphs can be
explained by which type of network does not only provide novel graph classes but
is crucial to understand which hard problem can be solved on which graph class
efficiently. We will mainly focus on graphs that can be explained by networks
(N,t) whose bi-connected components are simple cycles. These graphs are called
GaTEx, can be recognized in linear-time and are characterized by a set of 25
forbidden induced subgraphs. In particular, GaTEx graphs are closely related to
many other well-known graph classes such as P4-sparse and P4-reducible graphs,
weakly-chordal graphs, perfect graphs with perfect order, comparability and
permutation graphs. As a consequence, one can prove that many hard problems
become linear-time solvable on GaTEx graphs as well.
construction to capture key features of G in terms of a rooted labeled tree
(T,t) whose vertices are labeled as "series" (1), "parallel" (0) or "prime".
If a graph G does not contain prime modules, then all structural information of G
can be directly derived from its MD tree (T,t). As a consequence, many hard
problems become polynomial-time solvable on graphs without prime modules, since
the MD tree serves as a guide for algorithms to find efficient exact solutions
(e.g.\ for optimal colorings, maximum clique, isomorphism test, ... ).
However, the class of graphs without prime modules (aka cographs) is rather
restricted. We introduce here the novel concept of explicit modular decomposition
that aims at replacing "prime" vertices in the MD tree by suitable substructures
to obtain 0/1-labeled networks (N,t). Understanding which graphs can be
explained by which type of network does not only provide novel graph classes but
is crucial to understand which hard problem can be solved on which graph class
efficiently. We will mainly focus on graphs that can be explained by networks
(N,t) whose bi-connected components are simple cycles. These graphs are called
GaTEx, can be recognized in linear-time and are characterized by a set of 25
forbidden induced subgraphs. In particular, GaTEx graphs are closely related to
many other well-known graph classes such as P4-sparse and P4-reducible graphs,
weakly-chordal graphs, perfect graphs with perfect order, comparability and
permutation graphs. As a consequence, one can prove that many hard problems
become linear-time solvable on GaTEx graphs as well.
In this talk, I will give an overview on the relationship between the
structure of a reaction network and the possible dynamics of the
species concentrations. To this aim, I will focus on systems with
sufficiently nonlinear interaction functions (parameter-rich kinetic
models) and address the structure of the Jacobian matrix at a steady
state. Results are of two kinds: “existence” results that assert the
possibility of a dynamical feature for a specific choice of parameter
and “exclusion” results that assert a dynamical feature independently
from any choice of parameters. I will provide examples of both types.
structure of a reaction network and the possible dynamics of the
species concentrations. To this aim, I will focus on systems with
sufficiently nonlinear interaction functions (parameter-rich kinetic
models) and address the structure of the Jacobian matrix at a steady
state. Results are of two kinds: “existence” results that assert the
possibility of a dynamical feature for a specific choice of parameter
and “exclusion” results that assert a dynamical feature independently
from any choice of parameters. I will provide examples of both types.
*What?*
TikZ (acronym for "TikZ ist kein Zeichenprogramm")is a tool to create
graphic elements in LaTeX. Not only graphs, but all kind of figures you
might think of.
*When/Where?*
Session 1: Tuesday November 21st, 11am to 1pm, in room 109.
There might be a zoom link to attend remotely, if interest in such an
arrangement is shown. Recording of the sessions will also be considered.
*For who?*
Any LaTeX user (not only graph enthusiasts) interested in creating nice
figures for their papers, posters, presentations...
The first session will introduce the basics. No previous knowledge of TikZ
is required.
TikZ (acronym for "TikZ ist kein Zeichenprogramm")is a tool to create
graphic elements in LaTeX. Not only graphs, but all kind of figures you
might think of.
*When/Where?*
Session 1: Tuesday November 21st, 11am to 1pm, in room 109.
There might be a zoom link to attend remotely, if interest in such an
arrangement is shown. Recording of the sessions will also be considered.
*For who?*
Any LaTeX user (not only graph enthusiasts) interested in creating nice
figures for their papers, posters, presentations...
The first session will introduce the basics. No previous knowledge of TikZ
is required.
*What?*
TikZ (acronym for "TikZ ist kein Zeichenprogramm")is a tool to create
graphic elements in LaTeX. Not only graphs, but all kind of figures you
might think of.
*When/Where?*
Session 2: Tuesday November 28th, 11am to 1pm, in room 109.
There might be a zoom link to attend remotely, if interest in such an
arrangement is shown. Recording of the sessions will also be considered.
*For who?*
Any LaTeX user (not only graph enthusiasts) interested in creating nice
figures for their papers, posters, presentations...
The second session will present some advanced techniques to draw more
complex figures. Experience with TikZ, or attendance of the first session,
is expected.
TikZ (acronym for "TikZ ist kein Zeichenprogramm")is a tool to create
graphic elements in LaTeX. Not only graphs, but all kind of figures you
might think of.
*When/Where?*
Session 2: Tuesday November 28th, 11am to 1pm, in room 109.
There might be a zoom link to attend remotely, if interest in such an
arrangement is shown. Recording of the sessions will also be considered.
*For who?*
Any LaTeX user (not only graph enthusiasts) interested in creating nice
figures for their papers, posters, presentations...
The second session will present some advanced techniques to draw more
complex figures. Experience with TikZ, or attendance of the first session,
is expected.
Autocatalysis refers to the situation that a chemical
species catalyzes its own formation. A chemical reaction is
autocatalytic whenever one of its educts or reactants catalyzes its
own formation. Autocatalysis combines two features of the essence of
living systems, the ability to survive on an ambient food source and
the fact that each biochemical reaction in the system requires only
reactants and (most often) a catalyst that are provided by other
reactions in the system or are present in the food set. A chemical
reaction network, abbreviated to CRN, comprises a set of chemical
species and a set of chemical reactions. A CRN is represented as a
stoichiometric matrix S in which columns correspond to reactions and
rows correspond to chemical species. CRN can also be naturally
represented as a directed hypergraph H = (V, E) where V is the set of
chemical species and E is the set of chemical reactions.
Unfortunately, it is not easy to characterize the substructures that
define an autocatalytic process in a CRN. We will explore, and analyze
the mutual relations of five concepts regarding autocatalysis, which
are: autocatalytic cycles, Milo flows, autocatalytic cores, Nghe
flows, and strongly connected König digraphs. We will end with some
open questions about the topic and ideas for future research
species catalyzes its own formation. A chemical reaction is
autocatalytic whenever one of its educts or reactants catalyzes its
own formation. Autocatalysis combines two features of the essence of
living systems, the ability to survive on an ambient food source and
the fact that each biochemical reaction in the system requires only
reactants and (most often) a catalyst that are provided by other
reactions in the system or are present in the food set. A chemical
reaction network, abbreviated to CRN, comprises a set of chemical
species and a set of chemical reactions. A CRN is represented as a
stoichiometric matrix S in which columns correspond to reactions and
rows correspond to chemical species. CRN can also be naturally
represented as a directed hypergraph H = (V, E) where V is the set of
chemical species and E is the set of chemical reactions.
Unfortunately, it is not easy to characterize the substructures that
define an autocatalytic process in a CRN. We will explore, and analyze
the mutual relations of five concepts regarding autocatalysis, which
are: autocatalytic cycles, Milo flows, autocatalytic cores, Nghe
flows, and strongly connected König digraphs. We will end with some
open questions about the topic and ideas for future research