La génomique comparative étudie les similarités et/ou les dissimilarités entre génomes et permet d'établir des relations entre les espèces afin notamment de construire des phylogénies. Elle permet également de mettre en évidence des régions conservées au sein des génomes et de trouver ainsi des ensembles de gènes impliqués dans des processus biologiques conservés au cours de l'évolution. Dans ce mémoire, nous nous intéressons au calcul de mesures entre deux génomes en présence de gènes dupliqués, et plus particulièrement aux mesures à base de points de cassure, d'adjacences, d'intervalles communs et d'intervalles conservés. Suivant une démarche informatique, nous proposons tout d'abord une étude avancée de la complexité algorithmique des problèmes rencontrés, en prouvant notamment pour la plupart d'entre eux soit leur NP-Complétude soit leur APX-Difficulté. Par la suite, nous exposons plusieurs méthodes de calcul de mesures entre deux génomes, à savoir (i) une approche exacte basée sur une transformation en un problème de contraintes à variables booléennes, (ii) une heuristique et (iii) une méthode hybride qui s'appuie sur la méthode exacte et l'heuristique proposées. Par une étude sur un jeu de données réel, nous montrons les qualités respectives de ces méthodes. Enfin, nous proposons un protocole de calcul des intervalles communs et mettons en évidence, par son utilisation et par un outil de visualisation, l'aspect fonctionnel de certains intervalles communs.

L'évolution moléculaire, basée sur l'étude des données de séquençage, s'est imposée comme une approche majeure pour l'étude de l'Histoire des organismes vivants (notamment à travers les arbres phylogénétiques). Ses méthodes classiques reposent sur un découpage des génomes en entités supposées indépendantes : les gènes. Or, les gènes n'évoluent pas indépendamment : au sein de l'histoire des espèces qui le portent, l'histoire d'un gène s'inscrit. En outre, leur position le long des chromosomes fait qu'ils partagent des événements de mutations structurales (duplications, pertes de fragments chromosomiques) avec les gènes proches. Enfin, leur potentielle fonction biologique les amène à être influencés par (et à influencer en retour) l'évolution d'autres gènes. Je montre que ne pas prendre en compte ces relations d'inter-dépendances évolutives (de coévolution) lors de l'inférence d'arbres de gènes résulte en une suresti mation des différences entre les arbres des différents gènes ainsi qu'entre les arbres des gènes et l'arbre des espèces. Des modèles permettent déjà d'intégrer la coévolution des gènes avec les espèces à la reconstruction des arbres de gènes. Par ailleurs, on connaît des modèles décrivant l'évolution des relations entre gènes, néanmoins sans intégrer ces informations à la reconstruction des arbres de gènes. Je reprends ces avancées et les combine au sein d'une méthode qui modifie les arbres de gènes selon un critère qui prend en compte les séquences ainsi que des relations de coévolution avec les espèces et d'autres gènes. Cette méthode, appliquée à des mammifères et des champignons, permet de produire des histoires de gènes cohérentes entre elles / Molecular evolution, based on the study of sequencing data, established itself as a fundamental approach in the study of the history of living organisms (noticeably through the inference of phylogenetic trees). Classical molecular evolution methods rely on the decomposition of genomes into entities that are supposed independent: genes. However we know that genes do not evolve independently: their potential biological function lead them to be influenced by (and influence) the evolution of other genes. Moreover, their position along chromosomes imply that they share events of structural mutations (duplication, loss of a chromosome fragment) with neighbouring genes. Similarly, a gene individual history inscribes itself in the history of the species that bears it. I show that not taking into account this inter-dependency relationships (co- evolutionary relationships) during the inference of gene trees results in an overesti- mation of the differences between gene trees as well as between gene tree and species tree. Modelling efforts these last year have allowed the integration of gene and species co-evolution information to the reconstruction of gene trees. Besides, researchers have proposed models describing the evolution of the relationships linking genes, but without integration of this information in the tree building process. My works aim to combine these advances in a method that modify gene trees according to a criterion that integrates sequence information and information coming from co-evolution relationships. This method, applied to mammals and fungi, leads to gene histories that are more congruent (simpler adjacency histories, longer events of loss or transfer, ...)

L'évolution des génomes peut être observée à plusieurs échelles, chaque échelle révélant des processus évolutifs différents. A l'échelle de séquences ADN, il s'agit d'insertions, délétions et substitutions de nucléotides. Si l'on s'intéresse aux gènes composant les génomes, il s'agit de duplications, pertes et transferts horizontaux de gènes. Et à plus large échelle, on observe des réarrangements chromosomiques modifiant l'agencement des gènes sur les chromosomes. Reconstruire l'histoire évolutive des génomes implique donc de comprendre et de modéliser tous les processus à l'œuvre, ce qui reste hors de notre portée. A la place, les efforts de modélisation ont exploré deux directions principales. D'un côté, les méthodes de reconstruction phylogénétique se sont concentrées sur l'évolution des séquences, certaines intégrant l'évolution des familles de gènes. D'un autre côté, les réarrangements chromosomiques ont été très largement étudiés, donnant naissance à de nombreux modèles d'évolution de l'architecture des génomes. Ces deux voies de modélisation se sont rarement rencontrées jusqu'à récemment. Au cours de ma thèse, j'ai développé un modèle d'évolution de l'architecture des génomes prenant en compte l'évolution des gènes et des séquences. Ce modèle rend possible une reconstruction probabiliste de l'histoire évolutive d'adjacences et de l'ordre des gènes de génomes ancestraux en tenant compte à la fois d'évènements modifiant le contenu en gènes des génomes (duplications et pertes de gènes), et d'évènements modifiant l'architecture des génomes (les réarrangements chromosomiques). Intégrer l'information phylogénétique à la reconstruction d'ordres des gènes permet de reconstruire des histoires évolutives plus complètes. Inversement, la reconstruction d'ordres des gènes ancestraux peut aussi apporter une information complémentaire à la phylogénie et peut être utilisée comme un critère pour évaluer la qualité d'arbres de gènes, ouvrant la voie à un modèle et une reconstruction intégrative / Genomes evolve through processes that modify their content and organization at different scales, ranging from the substitution, insertion or deletion of a single nucleotide to the duplication, loss or transfer of a gene and to large scale chromosomal rearrangements. Extant genomes are the result of a combination of many such processes, which makes it difficult to reconstruct the overall picture of genome evolution. As a result, most models and methods focus on one scale and use only one kind of data, such as gene orders or sequence alignments. Most phylogenetic reconstruction methods focus on the evolution of sequences. Recently, some of these methods have been extended to integrate gene family evolution. Chromosomal rearrangements have also been extensively studied, leading to the development of many models for the evolution of the architecture of genomes. These two ways to model genome evolution have not exchanged much so far, mainly because of computational issues. In this thesis, I present a new model of evolution for the architecture of genomes that accounts for the evolution of gene families. With this model, one can reconstruct the evolutionary history of gene adjacencies and gene order accounting for events that modify the gene content of genomes (duplications and losses of genes) and for events that modify the architecture of genomes (chromosomal rearrangements). Integrating these two types of information in a single model yields more accurate evolutionary histories. Moreover, we show that reconstructing ancestral gene orders can provide feedback on the quality of gene trees thus paving the way for an integrative model and reconstruction method