Georgia Institute of Technology College of Sciences

RiboNucleic Acids (RNAs) are ubiquitous, versatile, and overall fascinating, biomolecules which play central roles in modern molecular biology. They also represent a largely untapped potential for biotechnology and health, substantiated by recent disruptive developments (mRNA vaccines, RNA silencing therapies, guide-RNAs of CRISPR-Cas9 systems...). To address those challenges, one must effectively  perform RNA design, generally defined as the determination of an RNA sequence achieving a predefined biological function.

I will focus in this talk on algorithmic results and enumerative properties stemming from the inverse folding, the problem of designing a sequence of nucleotides that fold preferentially and uniquely (with respect to base-pair maximization) into a target secondary structure. Despite the NP-hardness of the problem (+ absence of a Fixed Parameter-Tractable algorithm) we showed that it can be solved in polynomial time for restricted families of structures. Such families are dense in the space of designable 2D structures, so that any structure that admits a solution for the inverse folding can be efficiently designed in an approximated sense.

We show that any 2D structure avoiding two forbidden motifs can be modified into a designable structure  by adding at most one extra base-pair per helix. Moreover, both the modification and the design of a sequence for the modified structure can be computed in linear time. Finally, if time allows, I will discuss combinatorial consequences of the existence of undesignable motifs. In particular, it implies an exponentially decreasing density of designable structures amongst secondary structures. Those results extend to virtually any design objectives and energy models.

This is joint work with Cédric Chauve, Jozef Hales, Jan Manuch, Ladislav Stacho (SFU, Canada), Alice Héliou, Mireille Régnier, and Hua-Ting Yao (Ecole Polytechnique, France).

Frieze showed that the expected weight of the minimum spanning tree (MST) of the uniformly weighted graph converges to ζ(3). Recently, this result was extended to a uniformly weighted simplicial complex, where the role of the MST is played by its higher-dimensional analogue -- the Minimum Spanning Acycle (MSA). In this work, we go beyond and look at the histogram of the weights in this random MSA -- both in the bulk and in the extremes. In particular, we focus on the `incomplete' setting, where one has access only to a fraction of the potential face weights. Our first result is that the empirical distribution of the MSA weights asymptotically converges to a measure based on the shadow -- the complement of graph components in higher dimensions. As far as we know, this result is the first to explore the connection between the MSA weights and the shadow. Our second result is that the extremal weights converge to an inhomogeneous Poisson point process. A interesting consequence of our two results is that we can also state the distribution of the death times in the persistence diagram corresponding to the above weighted complex, a result of interest in applied topology.

Based on joint work with Nicolas Fraiman and Gugan Thoppe, see https://arxiv.org/abs/2012.14122

Bestvina--Brady groups are subgroups of right-angled Artin groups, and their Dehn functions are bounded above by quartic functions. There are examples of Bestvina--Brady groups whose Dehn functions are linear, quadratic, cubic, and quartic. In this talk, I will give a class of Bestvina--Brady groups that have polynomial Dehn functions, and we can identify the Dehn functions by the defining graphs of those Bestvina--Brady groups. 

The asymptotic dimension of metric spaces is an important notion in geometric group theory. The metric spaces considered in this talk are the ones whose underlying spaces are the vertex-sets of (edge-)weighted graphs and whose metrics are the distance function in weighted graphs. A standard compactness argument shows that it suffices to consider the asymptotic dimension of classes of finite weighted graphs. We prove that the asymptotic dimension of any minor-closed family of weighted graphs, any class of weighted graphs of bounded tree-width, and any class of graphs of bounded layered tree-width are at most 2, 1,and 2, respectively. The first result solves a question of Fujiwara and Papasoglu; the second and third results solve a number of questions of Bonamy, Bousquet, Esperet, Groenland, Pirot and Scott. These bounds for asymptotic dimension are optimal and generalize and improve some results in the literature, including results for Riemannian surfaces and Cayley graphs of groups with a forbidden minor.