Exact parameterized algorithmics for structural RNAbioinformatics

Algorithmique paramétrée exacte pour la bioinformatique structurale des ARNs Les ARNs (Acides Ribo-Nucléiques) constituent, avec l’ADN et les protéines, l’un des blocs élémentaires sur lesquels sont construits tous les systèmes biologiques. Si ils sont surtout connus comme étant de simples intermédiaires dans la synthèse de protéines (ARNs messagers), ils peuvent aussi agir directement en tant qu’ARN, et remplir alors des rôles très variés (catalyse, régulation de l’expression de gènes…). Pour ces ARNs dits non-codants, la structure de repliement qu’ils adoptent est cruciale.À la fois les séquences et les structures d’ARN présentent un aspect intrinsèquement combinatoire: les séquences sont des mots sur l’alphabet A,U,G,C, tandis que les structures sont principalement constituées de paires de bases A-U, G-C et G-U. Plusieurs problèmes fondamentaux impliquant les ARNs non-codant sont par conséquent naturellement exprimés dans le language des mathématiques discrètes. Ces problèmes incluent le repliement (Quelle est la structure préférentielle d’une séquence donnée ?), le design d’ARN (Comment trouver une séquence se repliant selon une structure spécifiée en entrée ?) ou le calcul de barrières d’énergie (Y’a-t-il une transition entre deux structures susceptible de survenir spontanément ?). Certains de ces problèmes fondamentaux sont NP-difficile, mais ls bioinformaticiens de l’ARN doivent tout de même les résoudre quotidiennement, soit pour mieux comprendre les systèmes biologiques naturels, soit pour le développement de thérapies à base d’ARN (dont les vaccins contre le COVID19 sont un exemple). Étant donné également les quantités toujours plus grandes de données de séquençage à traiter, il y a un besoin croissant de méthodes algorithmiques efficaces pour les problèmes mentionnés ci-dessus.La philosophie de cette thèse de doctorat est d’explorer les possibilités d’application de l’algorithmie paramétrée, un domaine relativement récent et très dynamique de la recherche algorithmique, à des problèmes difficiles de bioinformatique des ARNs. Une attention particulière est donnée aux formulations en termes de graphes, et à des paramètres de largeurs de graphes.