This page is devoted to the FWO Postdoctoral Project "Feasible self-assembly models" with me, Robert Brijder, as postdoctoral fellow. This research is performed at Hasselt University. Project duration: Oct. 1, 2013 - Sept. 30, 2016.

Project summary for the layman

This is an extended version of the official project summary for the layman.

Self-assembly

Self-assembly is the process in which intricate structures are obtained by spontaneous assembly of smaller building blocks. Self-assembly is present in a wide range of processes, and appears at various scales in nature. For example, the spontaneous formation of a molecular crystal and even the development of a single cell to a full-grown multicellular organism may be seen as (highly-involved) self-assembly processes. Self-assembly techniques are fundamental for the development of nanotechnology.

Want to know more about self-assembly?

Great! As always, wikipedia provides a nice starting point. There are cool videos available on a web site from the MIT self-assembly lab, and also from Harvard. More is explained in this nice video.

This project

The computing potential of self-assembly has recently been studied and partially experimentally verified. While there are now various self-assembly models available, their computational power is often too large to be either physically implementable or successfully analyzable. We often need only small computational power. So, why not compromise some of this power to obtain models that are more easy to implement or to analyze? Therefore, in this project, I aim to consider distinctly less powerful models in order to obtain models having some of these other attractive properties.

Results

See the publications and slides listed below. Stay tuned for an explanation for the layman of some of these results.


Publications

Below are the publications belonging to this project. Slides of the talks are provided as well. See here for all my publications.

  • R. Brijder, Dominance and Deficiency for Petri Nets and Chemical Reaction Networks. arXiv preprint 1503.04005. Journal version of DNA21 paper.

    Abstract
    Inspired by Anderson et al. [J. R. Soc. Interface, 2014] we study the long-term behavior of discrete chemical reaction networks (CRNs). In particular, using techniques from both Petri net theory and CRN theory, we provide a powerful sufficient condition for a structurally-bounded CRN to have the property that none of the non-terminal reactions can fire for all its recurrent configurations. We compare this result and its proof with a related result of Anderson et al. and show its consequences for the case of CRNs with deficiency one.

  • R. Brijder, Minimal Output Unstable Configurations in Chemical Reaction Networks and Deciders, To appear in Natural Computing, 2015. arXiv preprint 1404.3166. Journal version of DNA20 paper.

    Abstract
    We study the set of output stable configurations of chemical reaction deciders (CRDs). It turns out that CRDs with only bimolecular reactions (which are almost equivalent to population protocols) have a special structure that allows for an algorithm to efficiently compute their finite set of minimal output unstable configurations. As a consequence, a relatively large set of configurations may be efficiently checked for output stability. We also provide a number of observations regarding the semilinearity result of Angluin et al. (Distrib Comput 20(4):279–304, 2007) from the context of population protocols (which is a central result for output stable CRDs). In particular, we observe that the computation-friendly class of totally stable CRDs has equal expressive power as the larger class of output stable CRDs.

  • R. Brijder, Dominance and T-invariants for Petri Nets and Chemical Reaction Networks, DNA Computing and Molecular Programming - 21th International Conference (DNA 21) (A. Philips and P. Yin, eds.), Lecture Notes in Computer Science, v. 9211, 1-15, 2015. Local copy. Slides.

    Abstract
    Inspired by Anderson et al. [J. R. Soc. Interface, 2014] we study the long-term behavior of discrete chemical reaction networks (CRNs). In particular, using techniques from both Petri net theory and CRN theory, we provide a powerful sufficient condition for a structurallybounded CRN to have the property that none of the non-terminal reactions can fire for all its recurrent configurations. We compare this result and its proof with a related result of Anderson et al. and show its consequences for the case of CRNs with deficiency one.

  • R. Brijder, Recombination Faults in Gene Assembly in Ciliates Modeled Using Multimatroids, To appear in Theoretical Computer Science. Local copy.

    Abstract
    We formally model the process of gene assembly in ciliates on the level of individual genes using the notion of multimatroids introduced by Bouchet. Gene assembly involves heavy splicing and recombination, and it turns out that multimatroids form a suitable abstract model that captures essential features of this process. We use this abstract model to study the effect of faulty recombinations during the gene assembly process.

  • R. Brijder and Lorenzo Traldi, Isotropic matroids. II. Circle graphs. arXiv preprint 1504.04299.

    Abstract
    We present several characterizations of circle graphs, which follow from Bouchet's circle graph obstructions theorem.

  • R. Brijder and Lorenzo Traldi, Isotropic matroids. I. Multimatroids and neighborhoods. arXiv preprint 1503.04406.

    Abstract
    We discuss the connections between two kinds of combinatorial structures associated with looped simple graphs: isotropic matroids and binary multimatroids. In addition, we detail the connection between isotropic matroids and vertex neighborhoods in families of locally equivalent graphs.

  • R. Brijder, Output Stability and Semilinear Sets in Chemical Reaction Networks and Deciders, DNA Computing and Molecular Programming - 20th International Conference (DNA 20) (S. Murata and S. Kobayashi, eds.), Lecture Notes in Computer Science, v. 8727, 100-113, 2014. Local copy. Slides.

    Abstract
    We study the set of output stable configurations of chemical reaction deciders (CRDs). It turns out that CRDs with only bimolecular reactions (which are almost equivalent to population protocols) have a special structure that allows for an algorithm to efficiently calculate the (finite) set of minimal output stable configurations. As a consequence, a relatively large sequence of configurations may be efficiently checked for output stability.
    We also provide a number of observations regarding the semilinearity result of Angluin et al. [Distrib. Comput., 2007] from the context of population protocols (which is a central result for output stable CRDs). In particular, we observe that the computation-friendly class of totally stable CRDs has equal expressive power as the larger class of output stable CRDs.

  • R. Brijder and H.J. Hoogeboom, Graph Polynomials Motivated by Gene Rearrangements in Ciliates, 10th Conference on Computability in Europe (CiE 2014), Lecture Notes in Computer Science, v. 8493, 63-72, 2014. Local copy. Slides.

    Abstract
    Gene rearrangements within the process of gene assembly in ciliates can be represented using a 4-regular 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.

  • R. Brijder and H.J. Hoogeboom, Interlace Polynomials for Multimatroids and Delta-Matroids, European Journal of Combinatorics, v. 40, 142-167, 2014. arXiv preprint 1010.4678.

    Abstract
    We provide a unified framework in which the interlace polynomial and several related graph polynomials are defined more generally for multimatroids and delta-matroids. Using combinatorial properties of multimatroids rather than graph-theoretical 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 delta-matroids that correspond to new interrelationships and results for the corresponding graph polynomials. As a tool we prove the equivalence of tight 3-matroids and delta-matroids closed under the operations of twist and loop complementation, called vf-safe delta-matroids. This result is of independent interest and related to the equivalence between tight 2-matroids and even delta-matroids observed by Bouchet.


Slides of invited talks

Below are the slides of invited talks belonging to this project. See above for slides of conference talks belonging to contributed papers.