RNA Bioinformatics and ensemble dynamic programming

International audienceRiboNucleic Acids (RNAs) are fascinating biomolecules which, similarly to DNA, can be encoded as sequences over a four-letter alphabet, and perform a wide array of biological functions. However, unlike DNA, the precise function of a given RNA depends critically on its structure, adopted as the outcome of a folding process. Luckily, this intricate three- dimensional conformation can be adequately abstracted as a (non-crossing) list of contacts, i.e. a discrete combinatorial object.In this talk, I will emphasize how, over the past three decades, RNA biology has benefited from a continuous and fruitful cross-talk between discrete mathematicians, computer scientists and biochemists. At the center of this conversation lies the concept of dynamic-programming, an algorithmic design technique which solves a combinatorial optimization problem efficiently by taking advantage of a well-chosen decomposition of its search space. Extensions and optimized instances of this technique now allow to address, at a genomic scale, multiple questions related to the analysis of the Boltzmann ensemble and the sequence-structure(-function) relationship. These developments also raise well-defined open questions, motivating further studies of the underlying discrete structures