La reconstruction phylogénétique est considérée comme un élément central de divers domaines comme l’écologie, la biologie et la physiologie moléculaire pour lesquels les relations généalogiques entre séquences d’espèces ou de gènes, représentées sous forme d’arbres, peuvent apporter des éclairages significatifs à la compréhension de phénomènes biologiques. Le problème de Maximum de Parcimonie est une approche importante pour résoudre la reconstruction phylogénétique en se basant sur un critère d’optimalité pour lequel l’arbre comprenant le moins de mutations est préféré. Dans cette thèse nous proposons différentes méthodes pour s’attaquer à la nature combinatoire de ce problème NP-complet. Premièrement, nous présentons un algorithme de Recuit Simulé compétitif qui nous a permis de trouver des solutions de meilleure qualité pour un ensemble de problèmes. Deuxièmement, nous proposons une nouvelle technique de Path-Relinking qui semble intéressante pour comparer des arbres mais pas pour trouver des solutions de meilleure qualité. Troisièmement, nous donnons le code d’une implantation sur GPU de la fonction objectif dont l’intérêt est de réduire le temps d’exécution de la recherche pour des instances dont la longueur des séquences est importante. Finalement, nous introduisons un prédicteur capable d’estimer le score optimum pour un vaste ensemble d’instances avec une très grande précision. / Phylogenetic reconstruction is considered a central underpinning of diverse fields like ecology, molecular biology and physiology where genealogical relationships of species or gene sequences represented as trees can provide the most meaningful insights into biology. Maximum Parsimony (MP) is an important approach to solve the phylogenetic reconstruction based on an optimality criterion under which the tree that minimizes the total number of genetic transformations is preferred. In this thesis we propose different methods to cope with the combinatorial nature of this NP-complete problem. First we present a competitive Simulated Annealing algorithm which helped us find trees of better parsimony score than the ones that were known for a set of instances. Second, we propose a Path-Relinking technique that appears to be suitable for tree comparison but not for finding trees of better quality. Third, we give a GPU implementation of the objective function of the problem that can reduce the runtime for instances that have an important number of residues per taxon. Finally, we introduce a predictor that is able to estimate the best parsimony score of a huge set of instances with a high accuracy.

La reconstruction de phylogénies moléculaires consiste à retrouver l'arbre évolutif (ou phylogénie) d'un ensemble de séquences homologues. La méthode de reconstruction la plus fiable actuellement, semble être la méthode du maximum de vraisemblance. Les méthodes classiques pour rechercher la phylogénie de vraisemblance maximale deviennent, rapidement, très coûteuses en temps de calcul lorsque le nombre de séquences augmente. Elles ne peuvent donc pas traiter de grandes phylogénies. Actuellement, les deux types de méthodes qui permettent de reconstruire de grandes phylogénies suivant le principe du maximum de vraisemblance sont : les méthodes de distances et les méthodes de quadruplets. Toutes deux divisent le problème initial en sous-problèmes contenant peu de séquences. Elles peuvent alors résoudre rapidement (suivant le principe du maximum de vraisemblance) chacun de ces sous-problèmes, puis combiner les solutions obtenues pour proposer une phylogénie de l'ensemble des séquences. Après avoir présenté les principales méthodes de reconstruction phylogenetique, nous décrivons une nouvelle méthode de quadruplets (Weight Optimization) qui possède de bonnes propriétés théoriques et reconstruit des arbres plus fiables que Quartet Puzzling (une méthode de quadruplets très populaire). Nous expliquons ensuite en quoi les méthodes de quadruplets sont mal adaptées pour reconstruire de grandes phylogénies suivant le principe du maximum de vraisemblance, et comment ces méthodes peuvent résoudre efficacement d'autres problèmes. Puis, nous proposons une approche qui combine de manière originale les méthodes de distances et du maximum de vraisemblance. Cette approche que nous appelons TripleML permet d'améliorer la fiabilité de différentes méthodes de distances en remplaçant les distances qu'elles utilisent par des distances qui sont estimées en optimisant localement la vraisemblance de triplets de séquences (ou de groupes de séquences).

La reconstruction phylogénétique vise à reconstituer l'histoire évolutive d'un ensemble d'espèces sous forme d'un arbre. Parmi les méthodes de reconstruction, le problème Maximum de Parcimonie (MP) consiste à trouver un arbre binaire dont les feuilles sont associées à des séquences de caractères données, et qui minimise le score de parcimonie. Les méthodes de résolution existantes de ce problème NP-complet s'attachent généralement à appliquer des méthodes heuristiques traditionnelles, comme des algorithmes gloutons et de recherche locale. L'une des diffcultés du problème repose sur la manipulation d'arbres et la définition de voisinages d'arbres.<br />Dans cette thèse, nous nous intéressons en premier lieu à l'amélioration des techniques de résolution du problème MP basées sur un algorithme de descente. Après avoir montré de manière empirique les limites des voisinages existants, nous introduisons un voisinage progressif qui évolue au cours de la recherche afin de limiter l'évaluation de voisins infructueux lors d'une descente. L'algorithme obtenu est ensuite hybridé à un algorithme génétique utilisant un croisement d'arbres spécifique fondé sur les mesures de distance entre chaque couple d'espèces dans l'arbre. Cet algorithme mémétique exhibe des résultats très compétitifs, tant sur des jeux de test tirés de la littérature que sur des jeux générés aléatoirement.

Cette thèse a porté, d'une part, sur l'analyse des sur- et sous-représentations en dinucléotides au sein de différents génomes complets, en recherchant les liens éventuels avec des mécanismes connus de dommages causés à l'ADN qui soient liés à des sites avoisinants — particulièrement les voisins directs en 5' et 3'. L'étude de l'effet des UVs sur les génomes de micro-organismes, et sur l'effet de la méthylation sur les génomes de métazoaires en a été un des grands axes. D'autre part, les résultats récents de Bérard et al. sur des modèles d'évolution incorporant des dépendances entre bases adjacentes (pyrimidine suivie de purine) ont permis de développer une approche probabiliste d'estimation des substitutions liées au mécanisme de méthylation-désamination spontanée des dinucléotides CG.