Décompositions fonctionnelles et structurelles dans les modèles graphiques probabilistes appliquées à la reconstruction d’haplotypes

• Soutenue le : 12/12/2011
• Directeur de thèse : Simon de Givry
• Co-directeur : Andres Legarra (Station d’Amélioration Génétique des Animaux, INRA Toulouse)
• Ecole doctorale : Mathématiques Informatique et Télécommunications de Toulouse (Toulouse III)
• Mots-clés : optimisation combinatoire, modèle graphique probabiliste, réseau de fonctions de coûts, reconstruction d’haplotypes, pedigree
• Manuscrit : Manuscrit (français)

Résumé : Cette thèse s’intéresse à la décomposition dans les modèles graphiques que sont, entre autres, les réseaux bayésiens et les réseaux de fonctions de coûts (WCSP) et son application pour la reconstruction d’haplotypes dans les pedigrees. Nous appliquons les techniques des WCSP pour traiter les réseaux bayésiens, en exploitant les propriétés structurelles, de manière exacte et approchée, des instancesdans un cadre voisin de l’inférence. Pour l’optimisation, nous définissons une décomposition de fonctions qui produit des fonctions portant sur un plus petit nombre de variables. Les cohérences locales souples profitent de ces nouvelles fonctions plus petites. Un exemple d’application en optimisation est la reconstruction d’haplotypes. Elle est essentielle pour mieux analyser l’architecture génétique de caractères particuliers comme la production des animaux de rente ou la susceptibilité à une maladie . Le problème de reconstruction d’haplotypes se modélise sous forme d’un réseau bayésien. Notre décomposition fonctionnelle permet de réduire ce réseau bayésien en un problème d’optimisation Max-2SAT résolu efficacement par des méthodes exactes.