Hendrik Jan Hoogeboom (Leiden NL)
The Algebra of Ciliates
Turku, Unconventional Computation UC2011, Workshop on Language Theory in Biocomputing, 9 June 2011. (invited)Tampa, 1079th AMS Meeting, special session on Discrete Models in Molecular Biology, 10 march 2012. (slightly more math than version above)
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.
Pivot and Loop Complementation on Graphs and Set Systems
Prague, Theory and Applications of Models of Computation TAMC2010.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
-
R. Brijder, H.J. Hoogeboom.
The Group Structure of Pivot and Loop Complementation on Graphs and Set Systems.
European Journal of Combinatorics 32 (2011) 1353-1367.
doi: 10.1016/j.ejc.2011.03.002
[arXiv:0909.4004]
also: Pivot and Loop Complementation on Graphs and Set Systems, TAMC 2010, LNCS 6108 (2010) 151-162, doi: 10.1007/978-3-642-13562-0_15 - R. Brijder, H.J. Hoogeboom. Maximal Pivots on Graphs with an Application to Gene Assembly. Discr.Appl.Math. 158 (2010) 1977-1985. doi: 10.1016/j.dam.2010.08.030
- R. Brijder, H.J. Hoogeboom. Reality-and-Desire in Ciliates. In: Algorithmic Bioprocesses (Condon etal, eds.), Natural Computing Series, Springer (2009) pp.99-115.
- R. Brijder, T. Harju, H.J. Hoogeboom, Pivots, determinants, and perfect matchings of graphs (2008) To appear in TCS (2012) doi: 10.1016/j.tcs.2012.02.031" [arXiv:0811.3500]
- A. 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, 6264-6268, Aug 1989.
