Robert Brijder (»TUe)
Hendrik Jan Hoogeboom (Leiden NL) 

The Algebra of Ciliatesabstract. Ciliates, an ancient group of unicellular organisms, transform genes from their micronuclear (storage) form into their macronuclear (expressible) form. This process is called gene assembly. The DNA processing involved is interesting from both the biological and the computational point of view.There are various equivalent ways to formally model gene assembly (at the level of genes). Two of these were extensively studied in the book «Computation in living cells: gene assembly in ciliates» by Ehrenfeucht, Harju et al (Springer, 2004). However, one additional viewpoint is particularly enlightening: the process may be seen as (partial) matrix inversion. We show that on the one hand this leads to a number of significant consequences for the model and on the other hand it enriches general theory. Turku, Unconventional Computation UC2011, Workshop on Language Theory in Biocomputing, 9 June 2011. (invited) (presentation) Tampa, 1079th AMS Meeting, special session on Discrete Models in Molecular Biology, 10 march 2012. (slightly more math than version above) (presentation) Hasselt, DNA Computing & Molecular Programming Symposium, 15 May 2013 

References
BackgroundPrescott, D.: Genome gymnastics: Unique modes of DNA evolution and processing in ciliates. Nature Reviews 1 (2000) 191199. doi: 10.1038/35042057 


Graph PolynomialsCiE 2014 (Computability in Europe) Budapest, Hungary, June 2327, 2014. Special Session on Bioinspired Computation. (presentation)"Graph polynomials motivated by Gene Assembly", Math colloquium University South Florida, Tampa, 29 Jan 2016. (presentation). Also Math colloquium UNF, Jacksonville.
abstract. DNA rearrangement is a process often found in biology on both developmental and evolutionary scale. While many models have considered abstract operations involved in the rearrangement, the process itself can be directly modeled through fourregular graphs, as presented here. We describe ways to explain DNA rearrangements through fourregular graphs and double occurrence words. These models are illustrated through the rearrangement processes in a wellstudied ciliate species where DNA recombination is observed on a massive scale. The number of resulting molecules and the intermediate molecules throughout this process can be counted as terms in graph polynomials, closely related to the wellknown Tutte polynomial. We present two such polynomials in the last section. Keywords: DNA recombination, Ciliates, Fourregular graphs, Double occurrence words, Eulerian circuits, Graph polynomials
abstract. Gene rearrangements within the process of gene assembly in ciliates can be represented using a 4regular graph. Based on this observation, Burns et al. [Discrete Appl. Math., 2013] propose a graph polynomial abstracting basic features of the assembly process, like the number of segments excised. We show that this assembly polynomial is essentially (i) a single variable case of the transition polynomial by Jaeger and (ii) a special case of the bracket polynomial introduced for simple graphs by Traldi and Zulli. 
Interlace polynomials
abstract. We provide a unified framework in which the interlace polynomial and several related graph polynomials are defined more generally for multimatroids and deltamatroids. Using combinatorial properties of multimatroids rather than graphtheoretical arguments, we find that various known results about these polynomials, including their recursive relations, are both more efficiently and more generally obtained. In addition, we obtain several interrelationships and results for polynomials on multimatroids and deltamatroids that correspond to new interrelationships and results for the corresponding graph polynomials. As a tool we prove the equivalence of tight 3matroids and deltamatroids closed under the operations of twist and loop complementation, called vfsafe deltamatroids. This result is of independent interest and related to the equivalence between tight 2matroids and even deltamatroids observed by Bouchet.
Introduction. The interlace polynomial was discovered by Arratia, Bollobás, and Sorkin by studying DNA sequencing methods. Its definition can be traced from 4regular graphs (or 2in, 2out digraphs), to circle graphs and finally to arbitrary graphs (multiple edges are not allowed). We take the same route. In Section 2 we consider the theory of circuit partitions in 4regular graphs as initiated by the seminal paper of Kotzig, and consider the Martin polynomial for 4regular graphs (and 2in, 2out digraphs), which counts, for any k, the number a_{k} of circuit partitions of cardinality k. In Section 3 we associate a circle graph to any Eulerian circuit of a 4regular graph, and we invoke a theorem by CohnLempelTraldi to recover a_{k} from its circle graph. This leads naturally to the definition of the interlace polynomial for arbitrary graphs. [...] London, Royal Holloway University of London, Workshop on New Directions for the Tutte Polynomial: Extensions, Interrelations, and Applications, 11th14th July 2015. (abstract) (presentation) 

Pivot and Loop Complementation on Graphs and Set SystemsPrague, Theory and Applications of Models of Computation TAMC2010. (presentation)abstract. We study the interplay between principal pivot transform (pivot) and loop complementation for graphs. This is done by generalizing loop complementation (in addition to pivot) to set systems. We show that the operations together, when restricted to single vertices, form the permutation group S 3. This leads, e.g., to a normal form for sequences of pivots and loop complementation on graphs. The results have consequences for the operations of local complementation and edge complementation on simple graphs: an alternative proof of a classic result involving local and edge complementation is obtained, and the effect of sequences of local complementations on simple graphs is characterized. 

References
BackgroundA. Ehrenfeucht, T. Harju, I. Petre, D. Prescott, G. Rozenberg, Computation in Living Cells: Gene Assembly in Ciliates, Natural Computing Series, Springer (2004)Greslin, Prescott etal. Reordering of nine exons is necessary to form a functional actin gene in Oxytrichanova. PNAS 86, 62646268, Aug 1989. 
