Graph models and algorithms in (co-)evolutionary contexts

Résumé : Cette thèse s’inscrit dans le cadre de la bioinformatique. Les outils mathématiques les plus utilisés dans ce travail relèvent de la théorie des graphes, des statistiques, de la théorie des ensembles et des mathématiques discrètes. Ces mathématiques ont permis de développer des modèles de systèmes biologiques ainsi que des algorithmes efficaces dans l’étude concrète de ces modèles. La nécessité d’analyses de jeux de données de très grande taille a rendu critique dans notre démarche cette notion d’efficacité des algorithmes. Il faut enfin remarquer que le champ biologique qui a servi de support à cette thèse nous a conduit à explorer un domaine particulier au sein de la théorie de la complexité, à savoir le développement et l’analyse des algorithmes d’énumération.Le texte se compose de deux parties qui regroupent des résultats qui dérivent du même problème biologique. Dans chaque partie est présentée une introduction mathématique et une biologique, ainsi qu’une exposition détaillée des résultats que nous avons obtenus.Dans la première partie, la théorie des graphes est utilisée afin de modéliser l’information phylogénétique ainsi que les relations symbiotiques entre organismes. Cela conduit à l’analyse simultanée de plusieurs arbres, désignée sour le terme de co-phylogénie. Ces analyses sont importantes sur le plan fondamental par leur apport à la connaissance des mécanismes évolutifs mais aussi sur le plan plus appliqué dans le cadre des relations hôtes/pathogènes (la course aux armements), voire dans celui de l’émergence des pathologies nouvelles.Dans le premier chapitre, nous fournissons les principes mathématiques et biologiques nécessaires pour comprendre les résultats obtenus. En plus, nous donnons des informations sur l’état de la recherche dans le domaine de la reconstruction co-phylogénétique. En particulier, nous nous sommes intéressés à l’aspect énumératif de son coté énumératif centré autour de la possibilité d’expliciter toutes les solutions optimales pour une question donnée.Ce problème avait été déjà abondamment traité dans la littérature au moment où nous avons commencé ce travail. Cependant nous nous sommes très tôt rendu compte que non seulement aucun logiciel ne l’abordait d’une façon efficace et correcte, mais que de plus les limites, pratiques et théoriques, de cette approche étaient mal connues.C’est avec ce double objectif que nous avons développé et amélioré un nouvel algorithme, appelé Eucalypt, qui, n’étant pas seulement un outil efficace et innovant pour la reconstruction phylogénétique , nous a permis d’étudier le comportement du modèle basé sur les évènements, en termes de nombre et qualité des solutions sur des données réelles. Nous avons largement comparé notre méthode avec les logiciels qui étaient disponibles. Les résultats de l’expérimentation conduite sur Eucalypt, nous ont permis de mettre en évidence les avantages et les difficultés d’une des approches classiques de la co-phylogénie. Le logiciel développé est accessible à l’addresse: http://eucalypt.gforge.inria.fr/.La méthode et les résultats correspondants sont présentés dans le deuxième chapitre.Cette partie de nos études est présentée dans l’article : “B. Donati, C. Baudet, B. Sinaimeri, P. Crescenzi, and M.-F. Sagot. Eucalypt: Efficient tree reconciliation enumerator”, accepté par la revue Algorithms for Molecular Biology.Les études conduites avec Eucalypt, montrent que l’approche du scénario le plus parcimonieux présente des limites, qui ne peuvent pas être ignorés et dont un est constitué par la façon arbitraire avec laquelle on assigne des coûts aux différents événements ce qui influence profondément les résultats.Un deuxième point faible demeure le fait que sur des jeux de donnés réels d’une certaine ampleur, le nombre de solutions équivalentes est tellement élevé que toute réconciliation est absolument non justifiée.Pour répondre, au moins en partie à certains aspects négatifs emergés de notre analyse, nous avons avant tout défini, une nouvelle version du problème, dans laquelle les transferts ont une distance maximale fixée : le « k-bounded-All-MPR ».Eucalypt donne des solutions a cette version du problème en les énumérant avec un délai polynomial.Le deuxième pas pour éviter les faiblesses de la technique dite basée sur les évènements, a été le développement d’un deuxième algorithme, nommé Coala, basé sur un modèle Bayésien approximé.Les bénéfices de cette méthode sont doubles : il permet à la fois d’inférer un ensemble de coûts ad hoc pour un certain jeu de données, et de fournir une estimation de la fréquence de chaque évènement.Cela est particulièrement utile lorsqu’il n’est pas possible d’appliquer la règle de la parsimonie.Cette partie de nos études est présentée dans l’article : “C. Baudet, B. Donati, B. Sinaimeri, P. Crescenzi, C. Gautier, C. Matias, and M.-F. Sagot. Co-phylogeny reconstruction via an Approximate Bayesian Computation, article en révision dans Systematic Biology.Dans la partie 2, l’application biologique change, même si les outils mathématiques utilisés restent toujours la théorie des graphes et l’optimisation combinatoire. Le problème biologique que nous avons traité se situe dans le domaine du séquençage génomique. Plus spécifiquement, il s’agit d’ordonner et d’orienter un ensemble de fragments de même longueur, appelés contigs. On appelle ce processus effectuer un scaffolding. Celui-ci est introduit dans le quatrième chapitre, avec le pré-requis mathématiques nécessaire pour l’aborder.Le développement des méthodes de séquençage massives (NGS) a conduit à la nécessité du développement d’algorithmes et d’approches expérimentales pour terminer le séquençage complet d’un génome.Nous avons développé une nouvelle méthode avec le logiciel Medusa. Cet algorithme présenté dans le cinquième chapitre, résout efficacement le problème du scaffolding en utilisant beaucoup moins de mémoire que les procédures les plus utilisées. En fait, si la majorité des logiciels de scaffolding nécessite d’une grande quantité d’informations, provenant des démarches précédentes du processus du séquençage, Medusa exploite la comparaison avec un nombre variable d’organismes similaires, ce qui permet de séparer complètement la phase du scaffolding de l’assemblage et de travailler avec des files d’entrée sensiblement plus légeress.Avec Medusa, le problème du scaffolding est formalisé en terme d’optimisation combinatoire sur descgraphes et résolu grâce à un algorithme d’approximation avec un facteur constant.Contrairement aux autres méthodes actuellement utilisées, il ne nécessite ni d’une connaissance « a priori » des relations phylogénétiques qui existent entre l’organisme cible et les organismes de comparaison, ni de librairires de reads provenant d’un assembleur. Tout cela implique facilité d’utilisation et vitesse sont deux caractéristiques importantes de notre méthode.Benchmark et tests montrent aussi que Medusa est précis, et obtient souvent une meilleure performance que les scaffolders traditionnels. Medusa peut être utilisé localement ou à travers une interface web: http://combo.dbe.unifi.it/medusa/, et est présenté dans l'article « E. Bosi, B. Donati, M. Galardini, S. Brunetti, M.-F. Sagot, P. Lio, P. Crescenzi, R. Fani, et M. Fondi. Medusa: a multi-draft based scaffolder », en révision pour la revue Bioinformatics.Durant le développement de ce dernier algorithme nous avons rencontré un ensemble très intéressant de problèmes, purement mathématiques. En particulier, nous nous sommes intéressés a à un problème appelé Implicit Hitting Set qui n'a jamais été étudié en termes de complexité d’énumération.Ce problème a trouvé sa première application dans le cadre de la biologie computationnelle. Cependant, nous croyons qu'il est également intéressant d'un point de vue théorique parce que, grâce à son caractère très abstrait, il peut être considéré comme un cadre à l’intérieur duquel on peut redéfinir la plupart des problèmes combinatoires.Puisque le problème peut être formulé de différentes façons, nous proposons d'abord un ensemble de définitions et ensuite une démonstration de NP-complétude pour la plus générale de ces définitions. De nombreuses questions restent encore ouvertes et, en fait, nous aimerions étudier le problème dans deux directions: Top-bottom, d'identifier les conditions dans lesquelles le problème d'énumérer les solutions cesse d'être difficile; et bottom-top en définissant un ensemble de conditions pour lesquelles le problème est résoluble efficacement. Nous savons que certains de ses sous-problèmes sont polynomialement résolubles, ce qui garantit que cette condition existe. Les résultats et les lignes de recherche actuellement ouvertes sont présentées dans le chapitre 6.
Type de document :
Thèse
Bioinformatics [q-bio.QM]. Université Claude Bernard - Lyon I, 2014. English. 〈NNT : 2014LYO10235〉
Liste complète des métadonnées

Littérature citée [98 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/tel-01095298
Contributeur : Abes Star <>
Soumis le : vendredi 2 février 2018 - 16:58:07
Dernière modification le : jeudi 28 juin 2018 - 14:38:35
Document(s) archivé(s) le : jeudi 3 mai 2018 - 05:22:21

Fichier

TH2014DonatiBeatrice.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : tel-01095298, version 2

Citation

Beatrice Donati. Graph models and algorithms in (co-)evolutionary contexts. Bioinformatics [q-bio.QM]. Université Claude Bernard - Lyon I, 2014. English. 〈NNT : 2014LYO10235〉. 〈tel-01095298v2〉

Partager

Métriques

Consultations de la notice

100

Téléchargements de fichiers

72