Modèles et méthodes pour les études d'association à l'échelle du génome

The interdisciplinary field of systems biology has evolved rapidly over the last few years. Different disciplines have contributed to the development of both its experimental and theoretical branches. Although computational biology has been an increasing activity in computer science for more than a two decades, it has been only in the past few years that optimization models have been increasingly developed and analyzed by researchers whose primary background is Operations Research ( OR ). This dissertation aims at contributing to the field of computational biology by applying mathematical programming to certain problems in molecular biology. Specifically, we address three problems in the domain of Genome-Wide Association Studies: (i) the Pure Parsimony Haplotyping under Uncertain Data Problem that consists in finding the minimum number of haplotypes necessary to explain a given set of genotypes containing possible reading errors; (ii) the Parsimonious Loss of Heterozygosity Problem that consists of partitioning suspected polymorphisms from a set of individuals into a minimum number of deletion areas; (iii) and the Multiple Individuals Polymorphic ALU Insertions Recognition Problem that consists of finding the set of locations in the genome where ALU sequences are inserted in some individual(s). All three problems are NP-hard combinatorial optimization problems. Therefore, we analyse their combinatorial structure and we propose an exact approach to solution for each of them. The proposed models are efficient, accurate, compact, polynomial-sized and usable in all those cases for which the parsimony criterion is well suited for estimation.Le domaine interdisciplinaire de la biologie des systèmes a évolué rapidement au cours des dernières années. Différentes disciplines ont contribué au développement de la branche expérimentale aussi bien que de la branche théorique Bien que la biologie computationnelle a été une activité en en croissance en informatique depuis plusde deux décennies, ce n’est que depuis quelques années que des modèles d’optimisation ont été de plus en plus développés et analysés par des chercheurs dont la spécialité de base est la recherche opérationnelle. Cette thèse vise à apporter une contribution au domaine de la biologie computationnelle en appliquant la programmation mathématique à certains problèmes de biologie moléculaire. Plus précisément, nous abordons trois problèmes dans le domaine de GenomeWide Association Studies: (i) le problème appelé Pure Parsimony Haplotyping under Uncertain Data, qui consiste à trouver le nombre minimum d’haplotypes nécessaire pour expliquer un ensemble donné de génotypes contenant des erreurs de lecture potentielles; (ii) le problème appelé Parsimonious Loss of Heterozygosity Problem, qui consiste dans le partitionnement des polymorphismes soupçonnés à partir d’un ensemble d’individus en un nombre minimal de zones de suppression; (iii) et le troisième problème appelé Multiple Individuals Polymorphic ALU Insertions Recognition Problem, qui consiste à trouver l’ensemble des emplacements dans le génome où une séquence d’ ALU est insérée dans certains individus. Les trois problèmes sont des problèmes d’optimisation combinatoire NP-difficile. Par conséquent, nous avons analysé leur structure combinatoire et proposé une approche exacte de résolution pour chacun d’entre eux. Les modèles proposés sont efficaces, précis, compacts, de taille polynomiale, et utilisables dans tous les cas pour lesquels le critère de parcimonie est bien adapté à l’estimation