This page is devoted to the FWO Postdoctoral Projects "Feasible self-assembly models" and "Fault tolerance in self-assembly models" with me, Robert Brijder, as postdoctoral fellow. This research is performed at Hasselt University.

Duration of project "Feasible self-assembly models": Oct. 1, 2013 - Sept. 30, 2016.

Duration of project "Fault tolerance in self-assembly models": Oct. 1, 2016 - Sept. 30, 2019.


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 talks are provided as well. See here for all my publications.

  • R. Brijder, F. Geerts, J. Van den Bussche, and T. Weerwag, On the expressive power of query languages for matrices, 21th International Conference on Database Theory, ICDT 2018 (B. Kimelfeld and Y. Amsterdamer, eds.), Leibniz International Proceedings in Informatics (LIPIcs), v. 98, 10:1-10:17, 2018. arXiv preprint 1709.08359.

    Abstract
    We investigate the expressive power of MATLANG, a formal language for matrix manipulation based on common matrix operations and linear algebra. The language can be extended with the operation inv of inverting a matrix. In MATLANG + inv we can compute the transitive closure of directed graphs, whereas we show that this is not possible without inversion. Indeed we show that the basic language can be simulated in the relational algebra with arithmetic operations, grouping, and summation. We also consider an operation eigen for diagonalizing a matrix, which is defined so that different eigenvectors returned for a same eigenvalue are orthogonal. We show that inv can be expressed in MATLANG + eigen. We put forward the open question whether there are boolean queries about matrices, or generic queries about graphs, expressible in MATLANG + eigen but not in MATLANG + inv. The evaluation problem for MATLANG + eigen is shown to be complete for the complexity class Exists R.

  • R. Brijder, D. Doty, and D. Soloveichik, Democratic, Existential, and Consensus-Based Output Conventions in Stable Computation by Chemical Reaction Networks, Natural Computing, v. 17, 97-108, 2018. arXiv preprint 1604.03687.

    Abstract
    We show that some natural output conventions for error-free computation in chemical reaction networks (CRN) lead to a common level of computational expressivity. Our main results are that the standard consensus-based output convention have equivalent computational power to (1) existence-based and (2) democracy-based output conventions. The CRNs using the former output convention have only “yes” voters, with the interpretation that the CRN’s output is yes if any voters are present and no otherwise. The CRNs using the latter output convention define output by majority vote among “yes” and “no” voters. Both results are proven via a generalized framework that simultaneously captures several definitions, directly inspired by a Petri net result of Esparza, Ganty, Leroux, and Majumder [CONCUR 2015]. These results support the thesis that the computational expressivity of error-free CRNs is intrinsic, not sensitive to arbitrary definitional choices.

  • M.D. Johnston, D.F. Anderson, G. Craciun, and R. Brijder, Conditions for Extinction Events in Chemical Reaction Networks with Discrete State Spaces, Journal of Mathematical Biology, v. 76, 1535-1558, 2018. arXiv preprint 1701.02012

    Abstract
    We study chemical reaction networks with discrete state spaces and present sufficient conditions on the structure of the network that guarantee the system exhibits an extinction event. The conditions we derive involve creating a modified chemical reaction network called a domination-expanded reaction network and then checking properties of this network. Unlike previous results, our analysis allows algorithmic implementation via systems of equalities and inequalities and suggests sequences of reactions which may lead to extinction events. We apply the results to several networks including an EnvZ-OmpR signaling pathway in Escherichia coli.

  • R. Brijder, Orienting Transversals and Transition Polynomials of Multimatroids, Advances in Applied Mathematics, v. 94, 120-155, 2018. arXiv preprint 1605.04244.

    Abstract
    Multimatroids generalize matroids, delta-matroids, and isotropic systems, and transition polynomials of multimatroids subsume various polynomials for these latter combinatorial structures, such as the interlace polynomial and the Tutte–Martin polynomial. We prove evaluations of the Tutte–Martin polynomial of isotropic systems from Bouchet directly and more efficiently in the context of transition polynomials of multimatroids. Moreover, we generalize some related evaluations of the transition polynomial of 4-regular graphs from Jaeger to multimatroids. These evaluations are obtained in a uniform and matroid-theoretic way. We also translate the evaluations in terms of the interlace polynomial of graphs. Finally, we give an excluded-minor theorem for the class of binary tight 3-matroids (a subclass of multimatroids) based on the excluded-minor theorem for the class of binary delta-matroids from Bouchet.

  • R. Brijder, Sorting by Reversals and the Theory of 4-Regular Graphs, Theoretical Computer Science, v. 701, 40-53, 2017. arXiv preprint 1701.07463.

    Abstract
    We show that the theory of sorting by reversals fits into the well-established theory of circuit partitions of 4-regular multigraphs (which also involves the combinatorial structures of circle graphs and delta-matroids). In this way, we expose strong connections between the two theories that have not been fully appreciated before. We also discuss a generalization of sorting by reversals involving the double-cut-and-join (DCJ) operation. Finally, we also show that the theory of sorting by reversals is closely related to that of gene assembly in ciliates.

  • R. Brijder, Dominance and Deficiency for Petri Nets and Chemical Reaction Networks, Natural Computing, v. 16, 285-294, 2017. 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 and Lorenzo Traldi, Isotropic matroids III: Connectivity, Electronic Journal of Combinatorics, v. 24, P2.49, 2017. arXiv preprint 1602.03899.

    Abstract
    The isotropic matroid M[IAS(G)] of a graph G is a binary matroid, which is equivalent to the isotropic system introduced by Bouchet. In this paper we discuss four notions of connectivity related to isotropic matroids and isotropic systems. We show that the isotropic system connectivity defined by Bouchet is equivalent to vertical connectivity of M[IAS(G)], and if G has at least four vertices, then M[IAS(G)] is vertically 5-connected if and only if G is prime (in the sense of Cunningham's split decomposition). We also show that MIAS(G)] is 3-connected if and only if G is connected and has neither a pendant vertex nor a pair of twin vertices. Our most interesting theorem is that if G has n >= 7 vertices then M[IAS(G)] is not vertically n-connected. This abstract-seeming result is equivalent to the more concrete assertion that G is locally equivalent to a graph with a vertex of degree < n-1/2.

  • R. Brijder, D. Doty, and D. Soloveichik, Robustness of Expressivity in Chemical Reaction Networks, DNA Computing and Molecular Programming - 22th International Conference (DNA 22) (Y. Rondelez and D. Woods, eds.), Lecture Notes in Computer Science, v. 9818, 52-66, 2016.

    Abstract
    We show that some natural output conventions for error-free computation in chemical reaction networks (CRN) lead to a common level of computational expressivity. Our main results are that the standard definition of error-free CRNs have equivalent computational power to (1) asymmetric and (2) democratic CRNs. The former have only “yes” voters, with the interpretation that the CRN’s output is yes if any voters are present and no otherwise. The latter define output by majority vote among “yes” and “no” voters. Both results are proven via a generalized framework that simultaneously captures several definitions, directly inspired by a recent Petri net result of Esparza, Ganty, Leroux, and Majumder [CONCUR 2015]. These results support the thesis that the computational expressivity of error-free CRNs is intrinsic, not sensitive to arbitrary definitional choices.

  • R. Brijder, Minimal Output Unstable Configurations in Chemical Reaction Networks and Deciders, Natural Computing, v. 15, 235-244, 2016. 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, Theoretical Computer Science, v. 608, 27-35, 2015.. 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, Electronic Journal of Combinatorics, v. 23, P4.2, 2016. 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, Electronic Journal of Combinatorics, v. 23, P4.1, 2016. 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 some invited talks belonging to this project. See above for slides of conference talks belonging to contributed papers.