m

F Nous contacter


0
     
Multi angle

H 1 Comptage et design multiple d'ARN

Auteurs : Ponty, Yann (Auteur de la Conférence)
CIRM (Editeur )

    Loading the player...

    Résumé : Les Acides RiboNucléiques (ARN) sont des biopolymères linéaires omniprésents dans notre organisme, pouvant être codés comme des séquences sur un alphabet A,C,G,U. Ces molécules se replient sur elles-mêmes, établissant des liaisons hydrogènes d'où découlent l'appariement de certaines des positions, selon des règles de compatibilité des lettres n'autorisant que les paires dans l'ensemble A,U,C,G,G,U. De ce mécanisme d'appariements résulte l'adoption d'une ou plusieurs conformations, appelées structures secondaires, au passage bijectif avec les mots de Motzkin sans-pic. De nombreuses applications, en nanotechnologie, médecine, ou biostatistique, nécessitent de compter, ou encore engendrer aléatoirement, des séquences d'ARN simultanément compatibles avec un ensemble donné de structures secondaires. Un algorithme exponentiel, basé sur une décomposition (ear decomposition) du graphe de dépendance induit par l'union des paires, a ainsi été proposé par Höner zu Siederdissen et al [A]. Cet algorithme utilise la méthode récursive/programmation dynamique pour précalculer les nombres d'affectations compatibles avant/après chacun des choix locaux. Une phase de génération utilise ensuite ces nombres pour garantir l'uniformité de la génération. Cependant, cet algorithme ne permettait pas la prise en compte de critères énergétiques plus complexes, nécessitant l'utilisation d'un formalisme plus expressif que les graphes de dépendance (hypergraphes). De plus, la complexité de l'algorithme, théoriquement exponentielle sur un paramètre non-borné et parfois élevée en pratique, soulevait la question de la complexité du problème de comptage.
    Dans un travail récent avec Hammer, Wang et Will [B], nous établissons la #P complétude, et la complexité d'approximation, du problème de comptage des séquences compatibles. Notre preuve repose sur une bijection simple entre les séquences compatibles et les stables du graphes de dépendance. Nous proposons une approche alternative, basée sur la décomposition arborescente, pour contrôler de façon probabiliste [C] l'énergie moyenne des séquences pour les différentes structures, ou la composition en les différentes lettres. Ces résultats fournissent un cadre flexible et expressif pour le design d'ARN, et soulèvent des questions sur l'utilisation de stratégies alternatives (génération de Boltzmann, simulation parfaite) pour la génération aléatoire, ainsi sur le concept d'analyse en moyenne dans un contexte où la donnée en entrée est plus complexe que la taille de l'objet engendré.

    Keywords : random generation; Boltzmann sampling; context-free languages; multi-target RNA design; counting complexity

    Codes MSC :
    05A05 - Permutations, words, matrices
    05B45 - Tessellation and tiling problems
    60C05 - Combinatorial probability
    68Q45 - Formal languages and automata
    68R05 - Combinatorics in connection with computer science
    90C27 - Combinatorial optimization
    92D20 - Protein sequences, DNA sequences
    68Q87 - Probability in computer science (algorithm analysis, random structures, phase transitions, etc.)
    68W32 - Algorithms on strings

    Ressources complémentaires :
    https://www.cirm-math.fr/ProgWeebly/Renc1776/Ponty.pdf

      Informations sur la Vidéo

      Réalisateur : Hennenfent, Guillaume
      Langue : Français
      Date de publication : 22/03/2018
      Date de captation : 15/03/2018
      Collection : Research School ; Combinatorics ; Computer Science ; Mathematics in Science and Technology ; Probability and Statistics
      Format : MP4
      Durée : 00:26:05
      Domaine : Computer Science ; Combinatorics ; Probability & Statistics ; Mathematics in Science & Technology
      Audience : Chercheurs ; Doctorants , Post - Doctorants ; Etudiants Science Cycle 2
      Download : https://videos.cirm-math.fr/2018-03-15_Ponty.mp4

    Informations sur la rencontre

    Nom de la rencontre : ALEA Days / Journées ALEA
    Organisateurs de la rencontre : Busic, Ana ; Genitrini, Antoine ; Mairesse, Jean ; Martin, James
    Dates : 12/03/2018 - 16/03/2018
    Année de la rencontre : 2018
    URL Congrès : https://conferences.cirm-math.fr/1776.html

    Citation Data

    DOI : 10.24350/CIRM.V.19374103
    Cite this video as: Ponty, Yann (2018). Comptage et design multiple d'ARN. CIRM. Audiovisual resource. doi:10.24350/CIRM.V.19374103
    URI : http://dx.doi.org/10.24350/CIRM.V.19374103


    Voir aussi

    Bibliographie

    1. [A] Höner zu Siederdissen, C., Hammer, S., Abfalter, I., Hofacker, I.L., Flamm, C., & Stadler, P.F. (2013). Computational design of RNAs with complex energy landscapes. Biopolymers, 99(12), 1124-1136 - http://dx.doi.org/10.1002/bip.22337

    2. [B] Hammer, S., Ponty, Y., Wang, W., & Will, S. (2018). Fixed-parameter tractable sampling for RNA design with multiple target structures. RECOMB 2018 – 22nd Annual International Conference on Research in Computational Molecular Biology, Apr 2018, Paris, France. - https://hal.inria.fr/hal-01631277

    3. [C] Bodini, O., & Ponty, Y. (2010). Multi-dimensional Boltzmann sampling of languages. In
      M. Drmota, & B. Gittenberger (Eds.), Proceeding of the 21st international meeting on probabilistic, combinatorial, and asymptotic methods in the analysis of algorithms (pp.49-64). - https://hal.inria.fr/hal-00450763v4

Z