MAB: Méthodes et algorithmes pour la bio informatique

À la croisée de la biologie et de l’informatique, la bioinformatique cherche à résoudre des questions biologiques par le calcul. Celles-ci couvrent un large spectre, de la biologie fondamentale à l’agronomie en passant par la santé et l’environnement. La chute des coûts expérimentaux, du séquençage notamment, induit un nombre croissant d’applications à fort enjeux sociétal, en médecine personnalisée et inventaire de la biodiversité, par exemple. Le défi majeur est lié à l’augmentation exponentielle du volume des données, qui impose de revoir les méthodes et d’en concevoir de nouvelles. Dans ce contexte, l’équipe MAB poursuit des travaux méthodologiques (algorithmique du texte et des arbres, combinatoire, optimisation, modélisation probabiliste, apprentissage statistique) pour répondre à des questions biologiques essentielles (évolution, phylogénie, génomique comparative, annotation fonctionnelle des gènes et des protéines, paludisme, HIV, cancer).

Membres

Permanents

Non permanents

Thématiques de recherche

Dans l’ensemble de nos travaux nous essayons de combiner des résultats théoriques solides avec la résolution de questions biologiques essentielles. Cette approche est illustrée ci-dessous au travers de certains de nos résultats récents (liste non-exhaustive) :

Algorithmique et combinatoire

Les problèmes en bioinformatique relèvent souvent de l’algorithmique du texte (la représentation naturelle des séquences d’ADN et de protéines) et des arbres (représentant communément l’évolution d’un ensemble d'espèces ou de gènes). En algorithmique du texte, nous avons exhibé des algorithmes efficaces et capables d'analyser des dizaines de millions de séquences simultanément: MPSCAN recherche des mots dans un texte en une passe avec une complexité optimale en moyenne [Rivals et al 2009]. Nous avons obtenu des résultats importants pour deux problèmes combinatoires liés aux arbres: (i) un algorithme d'approximation à facteur constant avec une complexité optimale pour le problème du sous-arbre d’accord maximum [Berry et al 2009]; (ii) accélération d’un ordre de grandeur d’un algorithme de réconciliation d’arbres [Doyon et al 2010]. Nous avons aussi poursuivi l’étude des algorithmes pour reconstruire un arbre valué à partir des distances estimées entre ses feuilles: pour une classe très vaste de méthodes (présentes et potentielles), nous avons démontré l’existence d’importantes propriétés statistiques et algorithmiques [Pardi et Gascuel 2012]. Des travaux ont également été menés autour des réarrangements génomiques et des similarités combinatoires entre génomes [Bérard et al 2009].

Modélisation probabiliste et statistique

La bioinformatique fait appel à de nombreux modèles probabilistes dont les paramètres sont appris sur de vastes jeux de données par des méthodes statistiques. Nous avons en particulier modélisé les mécanismes de substitution à l’œuvre dans l’évolution des protéines. Ces modèles sont au cœur de la reconstruction phylogénétique par maximum de vraisemblance, et ils interviennent dans d’autres champs de la bioinformatique comme l’alignement. Le modèle standard est Markovien à temps continu et homogène le long des séquences et dans le temps. Nous avons proposé [Le et Gascuel Mol Biol Evol 2008] une nouvelle approche pour en estimer très précisément les paramètres, en se basant sur une très grande base de données contenant des milliers d’alignements. Le modèle correspondant (LG) est nettement plus performant que ses concurrents, déjà intégré dans de nombreux logiciels de phylogénie et largement cité (>300). Nous avons aussi proposé des alternatives performantes au modèle standard, en relaxant la contrainte d’homogénéité le long des séquences par l’utilisation de modèles de mélange, notamment pour prendre en compte la structure secondaire des protéines [Le et al Proc Roy Soc 2008, Le et Gascuel Syst Biol 2010, Le et Gascuel Mol Biol Evol 2012].

Analyses de séquences haut-débit (HD)

Le volume de séquences à traiter croît exponentiellement grâce au HD. Les analyses bioinformatiques requièrent des algorithmes nouveaux qui passent à l'échelle. Nous avons conçu de nouvelles structures de données d'index de séquences qui respectent ces exigences [Philippe et al. 2011] tout en permettant des requêtes pertinentes. Nous exploitons ces index dans l’ensemble de nos logiciels bioinformatiques. Pour analyser les lectures d'ARN (read), nous avons conçu et implanté le programme CRAC [Philippe et al. 2013]. Comparativement aux autres logiciels, CRAC offre la capacité de prédire des mutations, des jonctions d'épissage et des ARN de fusion en une seule analyse. Les ARN de fusion servent de marqueurs dans le diagnostic des cancers. Egalement, pour une formulation souple de la comparaison de génomes complets, nous avons proposé un algorithme quasi linéaire et développé le logiciel QOD (dépôt APP). Il a permis la découverte de 92 gènes nouveaux chez une bactérie pathogène des ruminants africains [Mancheron et al. 2011].

Phylogénomique

Dans le projet ANR Phylariane et un projet Chercheur d’Avenir (Région LR) nous avons coordonné des recherches sur l’histoire évolutive de familles de gènes. Nous avons amélioré les pipelines de programmes classant les centaines de milliers de gènes connus pour 600 organismes en familles de séquences homologues [Penel et al. 2009]. Puis nous avons accéléré d’un ordre de grandeur les méthodes inférant les événements évolutifs majeurs ayant façonné les phylogénies de ces gènes, à savoir les duplications, les transferts et les pertes de gènes [Doyon et al 2010]. La prise en compte de ces événements permet aussi de corriger les arbres de gènes construits depuis le seul signal des séquences [Nguyen et al 2013]. Plus récemment nous avons proposé une structure décrivant en un espace de taille polynomiale un nombre exponentiel de réconciliations entre arbres d’espèces et arbres de gènes [Scornavacca et al 2013]. Cette structure est la base pour obtenir, pour la première fois dans ce domaine, des mesures de confiance. Une base de données d’histoires évolutives permet d’interroger les nombreuses familles de gènes traitées sur les actinobactéries et les mammifères.

Annotation des protéomes

L'annotation fonctionnelle d'un organisme vise à identifier la ou les fonctions cellulaires de chacune de ses protéines. Chez les organismes pathogènes, c'est une étape clef pour l'identification de cibles thérapeutiques. Nos travaux dans ce cadre s'articulent autour de deux axes. Un premier axe a pour objectif l'amélioration de la sensibilité des outils d'annotation basés sur les HMMs (Hidden Markov Models). Plusieurs travaux ont été réalisés dans ce cadre : apprentissage de HMMs adaptés à un organisme particulier [Terrapon et al 2012], utilisation de propriétés de co-occurence pour améliorer la détection [Terrapon et al 2009]. Ces travaux ont donnés lieu à une base de données d'annotations dédiée aux pathogènes eukaryotes (EuPathDomains), qui intègre les annotations existantes aux annotations prédites par nos outils [Ghouila et al 2011]. Le second axe de recherche est le développement d'outils d'annotations basés sur des mesures du niveau d'expression de chaque protéine (données issues des techniques NGS par exemple). Dans ce cadre, nous avons développé une méthode et un logiciel (RED2) permettant d'identifier les signaux génomiques (les motifs) responsables de la régulation des protéines au niveau cellulaire suite à un certain traitement [Lajoie et al. 2012].

Plateforme, logiciels

La diffusion de nos travaux en bioinformatique est assurée par la plate-forme ATGC labellisée par IBiSA en 2010 et coordinatrice des activités de services en bioinformatique sur le sud de la France (de Nice à Perpignan) pour l'Institut Français de Bioinformatique (PIA, appel Infrastructures Nationales en Biologie-Santé). La principale vocation d'ATGC est la diffusion de logiciels, qui peuvent être utilisés en ligne et/ou téléchargés gratuitement. Les outils développés localement et distribués sur ATGC ont une très grande visibilité internationale. En phylogénie, le logiciel PhyML (Guindon et Gascuel, 2003) a été cité plus de 6000 fois. Le nombre d'analyses réalisées est en constante augmentation : 25000 analyses en 2009 soit 115000 heures de calcul ; 40000 analyses en 2012 soit 180000 heures de calcul. Nous recevons des requêtes de 900 utilisateurs uniques chaque mois, dont la répartition géographique est indiquée ci-dessous. La plateforme assure aussi une aide directe aux biologistes et des cours de formation permanente (CNRS Formation).

Faits Marquants

  • L’équipe MAB a un niveau élevé de publication, avec une soixantaine d’articles publiés dans des revues internationales sur la période 2008-2013. Ces articles ont déjà été cités plus de 2500 fois (Web of Science). Nous sommes également associés à un brevet sur la purification de l’ADN, déposé en 2010.
  • Nous sommes à l’origine de l’Institut de Biologie Computationnelle (IBC) soutenu par les Investissement d’Avenir (PIA). Nous sommes fortement impliqués (porteurs d’axes ou de work-packages) dans trois autres PIA : le Labex NUMEV, l’Institut Français de Bioinformatique (RENABI-IFB) et France Génomique (FG).
  • La plateforme de bioinformatique ATGC a été labellisée IBISA en 2010 :
    • elle coordonne les activités de services en bioinformatique pour RENABI-IFB sur le sud de la France
    • les logiciels qu’elle distribue et dont MAB est à l’origine ont été cités plus de 12000 fois.
  • Huit conférences organisées en 2008-2013 :
  • Prix et distinctions :
    • Prix Hélène Starck de l’Association pour la Recherche contre le Cancer (ARC) pour son projet post-doctoral (N. Philippe 2012).
    • Chercheurs d’Avenir de la Region Languedoc-Roussillon (V. Berry 2009 et E. Rivals 2010).
    • Prix “Dortmunder Gambrinus" décerné par l'université de Dortmund à un scientifique reconnu en science ou humanités (E. Rivals 2009).
    • Médaille d’Argent du CNRS (O. Gascuel 2009).

Collaborations

  • University of Helsinski (Finlande) : Algorithmique du texte haute performance, PICS 2009-2012.
  • University of Canterbury (Christchurch, Nouvelle Zélande) : projet “Genetic Jigsaws with Missing Pieces” sur la phylogénétique mathématique, financé par le Marsden fund (NZ).
  • Simon Fraser University (Vancouver, Canada) : aspects combinatoires en génomique comparative, phylogénie et assemblage.
  • Laboratoire de Biométrie et Biologie Evolutive (Lyon) et Institut des Sciences de l’Evolution (Montpellier) : phylogénomique et reconstructions ancestrales.
  • CEA Grenoble : genomique fonctionnelle de Plasmodium falciparum ; 8 publications en revue, dont une dans Nature Chemical Biology (IF 14.7).

Publications de l'équipe à partir de 2008

Mots-clés

Algorithmique du texte et des arbres, Combinatoire, Optimisation, Modélisation probabiliste et statistique, Classification, Phylogénie, Séquençage haut debit, Génomes, Transcriptomes, Protéomes, Cancer, Paludisme, VIH

Dernière mise à jour le 22/11/2013