moteur de recherche

Séminaire Algo - Yann Ponty
Séminaire Algo - Yann Ponty
12-Mar-2019 14:30
Age: 162 days





Yann Ponty

Complexité paramétrée pour le design d'ARN positif

Salle de séminaire (4B05R) - Bâtiment Copernic

Abstract:

Le design multiple (positif) d'ARN consiste à engendrer aléatoirement, uniformément ou dans une distribution de Boltzmann, m séquences de nucléotides sur {A,C,G,U}^n, compatibles avec k structures secondaires S=(S_1,...,S_k), chacune consistant en un ensemble de paires de bases. Ces dernières constituent les arêtes d'un graphe de compatibilité G_S, dont les sommets sont les positions dans la séquence d'ARN, et où toute paire de positions adjacentes doit se voir affecter des paires nucléotides compatibles A-U, C-G ou G-U. Cette approche, parfois couplée avec des optimisations ultérieures par recherche locale, jouit d'une popularité croissante pour le design d'ARN au paysages d'énergie complexes, tels les 'riboswitches', qui régulent l'activité d'un gène sélectivement, via l'adoption de deux structures alternatives sur présence/absence d'une petite métabolite. 

Dans un premier temps, nous considérons la complexité d'une génération uniforme de structures compatibles par une méthode dite récursive. Dans celle-ci, les probabilités d'affectation des nucléotides sont précalculées afin d'induire une distribution uniforme. La génération requière donc, a minima, le calcul du nombre de séquence compatibles avec le graphe de compatibilité. Ce nombre admet une forme close pour plusieurs familles de graphes, mais son calcul reste en général #P-difficile, du fait d'une bijection (à symétrie trivial près) entre les séquence compatibles et les stables de G_S quand celui-ci est biparti, le problème étant trivial sinon. Le comptage des stables d'un graphe biparti est un problème #P-difficile bien étudié, et constitue même une classe de complexité #BIS intermédiaire pour le comptage approché (FPRAS pour max degré <5, et #BIS complet au delà). 

Nous proposons ensuite un algorithme FPT, basé sur la décomposition arborescente, pour la génération récursive. Notre algorithme engendre m séquences en temps O(n k 2^w + m n k) pour un graphe G_S de largeur arborescente w. Il se généralise à une distribution "pondérée" de Boltzmann-Gibbs, basée sur une ou plusieurs notion(s) d'énergie définie(s) additivement sur des fonctions, chacune évaluée sur les nucléotides affectés à des sous-ensembles des positions. Il permet d'envisager un cadre général pour la génération aléatoire à partir de contraintes basée sur des fonctions d'arités supérieures, combinant décomposition arborescente, programmation dynamique et algorithmes de rejet efficaces (génération de Boltzman multi-dimensionnelle) pour la prise en charge des contraintes valuées linéairement. 

Ce travail soulève de nombreuses questions algorithmiques en lien avec : 

* la complexité paramétrée des problèmes de comptage; 

* l'incorporation des contraintes de langages exprimées par des langages formelles; 

* l'adaptation de la recherche locale dans des espaces d'états complexes; 

* une caractérisation de conditions suffisantes, algorithmiquement testables, garantissant une concentration propice à un rejet efficace dans les schémas de programmation dynamique; 

* l'existence d'algorithmes efficaces (approchés) pour la simplification des (hyper)graphes. 

Ce travail, présenté à RECOMB 2018, a été mené en collaboration avec Sebastian Will (Univ. de Vienne), Stefan Hammer (Univ. Leipzig) et Wei Wang (LIX Polytechnique et Paris-Sud). 

Manuscrit étendu (en cours d'arbitrage) : https://hal.inria.fr/hal-<wbr></wbr>01631277v2 

Implémentation dédiée au design d'ARN est disponible à : https://github.com/yannponty/<wbr></wbr>RNARedPrint 

Implémentation générale (+ librairie Python pour la définition du problème) : https://github.com/s-will/<wbr></wbr>Infrared








<- Back to: Accueil