Page 310 - 8th European Congress of Mathematics ∙ 20-26 June 2021 ∙ Portorož, Slovenia ∙ Book of Abstracts
P. 310
GRAPHS, POLYNOMIALS, SURFACES, AND KNOTS (MS-49)
(8n + 1)/9. This is a broad generalization of results for regular tournaments due to Bonnington
et al. (2002) and Griggs, McCourt and Širánˇ (2020).
Embeddings with Eulerian faces I: context and parities
Joanna Ellis-Monaghan, jellismonaghan@gmail.com
University of Amsterdam, Netherlands
Coauthor: Mark Ellingham
Closed walks that cover all the edges of a graph arise in many settings. In DNA self-assembly
experiments, they give a route for a special strand of DNA through the assembled molecule. A
reporter strand walk covers all the edges of a graph at least once, and if twice then in opposite
directions, without doubling back on any edge. A graph is edge-outer embeddable if it has an
orientable embedding with a special face whose boundary uses every edge at least once. Thus
a reporter strand walk is a facial walk around an outer face of such an edge-outer embedding.
While every graph has such an edge-outer embedding, finding one with a minimum size outer
face is NP-hard. Furthermore, genus-related questions naturally arise in this new edge-outer
embeddability setting. Here we focus on a min-max question: What graphs have edge-outer
embeddings with both a minimum size outer face and maximum genus? This question is partic-
ularly interesting in the case of Eulerian graphs. Does there always exist an oriented embedding
of a given Eulerian graph with two faces, each bounded by an Euler circuit, possibly even with
one circuit specified in advance? We answer this by addressing the cases, in order, of yes, no,
sometimes, and (at the time of writing) we have a conjecture.
Formal grammar modeling three-stranded DNA:RNA braids
Margherita Maria Ferrari, mmferrari@usf.edu
University of South Florida, United States
Coauthors: Manda Riehl, Mariel Vazquez, Svetlana Poznanovic´, Nataša Jonoska
A formal grammar is a system to generate words; it consists of a set of symbols, partitioned into
terminals and non-terminals, and a set of production rules. The production rules specify how to
rewrite non-terminal symbols, so that successive applications of those rules yield words formed
by only terminals. Adding probabilities to the production rules defines stochastic grammars,
which can be used for biological sequence analysis. In this talk, we focus on a “braid gram-
mar” to model R-loops, that are three-stranded structures formed by a DNA:RNA hybrid plus a
single strand of DNA, often appearing during transcription. R-loops are described as strings of
terminal symbols representing the braiding of the strands in the structure, where each symbol
corresponds to a different state of the braided structure. We discuss approaches to develop a
stochastic grammar and a probabilistic model for R-loop prediction, as well as refinements of
the model by incorporating the effect of DNA topology on R-loop formation.
308
(8n + 1)/9. This is a broad generalization of results for regular tournaments due to Bonnington
et al. (2002) and Griggs, McCourt and Širánˇ (2020).
Embeddings with Eulerian faces I: context and parities
Joanna Ellis-Monaghan, jellismonaghan@gmail.com
University of Amsterdam, Netherlands
Coauthor: Mark Ellingham
Closed walks that cover all the edges of a graph arise in many settings. In DNA self-assembly
experiments, they give a route for a special strand of DNA through the assembled molecule. A
reporter strand walk covers all the edges of a graph at least once, and if twice then in opposite
directions, without doubling back on any edge. A graph is edge-outer embeddable if it has an
orientable embedding with a special face whose boundary uses every edge at least once. Thus
a reporter strand walk is a facial walk around an outer face of such an edge-outer embedding.
While every graph has such an edge-outer embedding, finding one with a minimum size outer
face is NP-hard. Furthermore, genus-related questions naturally arise in this new edge-outer
embeddability setting. Here we focus on a min-max question: What graphs have edge-outer
embeddings with both a minimum size outer face and maximum genus? This question is partic-
ularly interesting in the case of Eulerian graphs. Does there always exist an oriented embedding
of a given Eulerian graph with two faces, each bounded by an Euler circuit, possibly even with
one circuit specified in advance? We answer this by addressing the cases, in order, of yes, no,
sometimes, and (at the time of writing) we have a conjecture.
Formal grammar modeling three-stranded DNA:RNA braids
Margherita Maria Ferrari, mmferrari@usf.edu
University of South Florida, United States
Coauthors: Manda Riehl, Mariel Vazquez, Svetlana Poznanovic´, Nataša Jonoska
A formal grammar is a system to generate words; it consists of a set of symbols, partitioned into
terminals and non-terminals, and a set of production rules. The production rules specify how to
rewrite non-terminal symbols, so that successive applications of those rules yield words formed
by only terminals. Adding probabilities to the production rules defines stochastic grammars,
which can be used for biological sequence analysis. In this talk, we focus on a “braid gram-
mar” to model R-loops, that are three-stranded structures formed by a DNA:RNA hybrid plus a
single strand of DNA, often appearing during transcription. R-loops are described as strings of
terminal symbols representing the braiding of the strands in the structure, where each symbol
corresponds to a different state of the braided structure. We discuss approaches to develop a
stochastic grammar and a probabilistic model for R-loop prediction, as well as refinements of
the model by incorporating the effect of DNA topology on R-loop formation.
308
