Skip to Main content Skip to Navigation
Conference papers

RNA Bioinformatics and ensemble dynamic programming

Yann Ponty 1, 2
1 AMIB - Algorithms and Models for Integrative Biology
LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau], LRI - Laboratoire de Recherche en Informatique, UP11 - Université Paris-Sud - Paris 11, Inria Saclay - Ile de France
Abstract : RiboNucleic 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.
Document type :
Conference papers
Complete list of metadatas
Contributor : Yann Ponty <>
Submitted on : Thursday, July 27, 2017 - 5:17:15 PM
Last modification on : Thursday, March 5, 2020 - 6:35:17 PM


  • HAL Id : hal-01569852, version 1



Yann Ponty. RNA Bioinformatics and ensemble dynamic programming. 5th biennial Canadian Discrete and Algorithmic Mathematics Conference - CanaDAM 2015, Jun 2015, Saskatoon, Canada. ⟨hal-01569852⟩



Record views