Thèse numérisée par la Direction des bibliothèques de l'Université de Montréal.

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

Thèse numérisée par la Direction des bibliothèques de l'Université de Montréal.

Avec l'arrivée des données moléculaires vers la fin des années 70, nous avons assisté à la découverte de nouveaux mécanismes d'évolution primordiaux dont l'échange du matériel génétique entre les espèces. Un tel échange peut se faire horizontalement, quand l'organisme intègre le matériel génétique provenant d'un autre organisme qui n'est pas son descendant direct, ou verticalement, quand l'organisme reçoit du matériel génétique à partir de son ancêtre le plus proche. Le problème de la détection et de la classification des transferts horizontaux de gènes (THG) est parmi les plus ardus en bioinformatique. Dans cette thèse, nous décrivons cinq nouveaux algorithmes pour la détection de THGs complets ou partiels qui seront basés sur des comparaisons topologiques et métriques entre un arbre d'espèces et un arbre de gène inférés pour le même ensemble d'espèces. Ces algorithmes incluent l'algorithme de détection de THGs complets ainsi que ses versions interactive et consensus. Les deux algorithmes de détection de transferts partiels que nous avons proposés peuvent être vus comme une généralisation de l'algorithme de détection de transferts complets. Ils peuvent être utilisés pour identifier des gènes mosaïques. Nous présentons aussi dans cette thèse une version parallèle de l'algorithme de détection de THGs complets, ainsi qu'une plateforme pour la transformation semi-automatique de programmes bioinformatiques séquentiels en programmes parallèles. Une interface Web intégrant tous les programmes développés dans le cadre de ce projet doctoral a aussi été mise au point. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : algorithmes bioinformatiques, arbre phylogénétique, programmation parallèle, réseau réticulé, transfert horizontal de gènes (THG).

Les rudistes bivalves forment un groupe monophylétique qui s’étend dans le registre fossile de 160 à 66 millions d’années. L’objectif de cette thèse est de porter un nouveau regard sur l’histoire évolutionnaire de ce groupe dans le cadre de la théorie cladistique. Dans une première partie sont posées les bases théoriques, méthodologiques et techniques de l’analyse à trois éléments. Le concept de triplet permet de proposer des arguments sur la pertinence des arbres consensus. La méthode d’analyse à trois éléments est ensuite comparée à la méthode de parcimonie grâce à des arguments théoriques et méthodologiques, ainsi que par des simulations basées sur des modèles d’évolution. Dans une seconde partie, nous appliquons la théorie et la méthode à la reconstruction de l’histoire des rudistes. Le genre Ichthyosarcolites est révisé, et des analyses statistiques permettent de tester la pertinence des hypothèses d’homologie basée sur la forme de la coquille. Les hypothèses d’homologie sont revues et de nouveaux caractères basés sur les myophores et les canaux palléaux sont formalisés pour l’ensemble des Hippuritida. La nouvelle phylogénie qui en découle est cohérente avec l’âge géologique et permet de raffiner l’histoire évolutive des rudistes au Crétacé. L’étude de couches Cénomaniennes du Bassin Sud-Provençal (Var, France) nous permettent de faire un lien entre l’histoire de la diversification des rudistes et leur paléoécologie. / The rudist bivalves form a monophyletic group that extends in the fossil record from 160 to 66 million years. The objective of this thesis is to propose new insights at the evolutionary history of this group within the framework of cladistic theory. In the first part, we lay the theoretical, methodological and technical foundations of the three-item analysis. The concept of triplet allows us to propose arguments on the relevance of consensus trees in cladistics. The three-item analysis method is then compared to the method of parsimony using theoretical and methodological arguments, and simulations based on evolutionary models. In a second part, we apply the theory and method to the reconstruction of the rudist history. The genus Ichthyosarcolites is reviewed, and statistical analyses are used to test the relevance of homology hypotheses based on shell shape. Hypotheses of homology and new characters based on myophores and pallial canals are tested on the Hippuritida. The new, resulting phylogeny is consistent with known geological occurrences of the group and further our understanding of rudist evolutionary history during the Cretaceous. The study of Cenomanian outcrops of the South Provence Basin (Var, France) allows us to make a link between the history of the diversification of rudists and their paleoecology.

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.

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

Ce travail de thèse propose une étude des nouvelles méthodes de classification, dites phylogénétiques, empruntées à la biologie dans le but de proposer une nouvelle classification linguistique. Les langues étudiées appartiennent à la famille « bantu », présentes au sein de la famille linguistique Niger-Congo, parlée en Afrique. De nombreux travaux ont été établis sur les langues bantu, montrant ainsi la complexité de cette famille linguistique. Notre étude se spécialise sur la zone « Nord-Ouest », qui comprend les pays suivants : Cameroun, Guinée Équatoriale, Gabon, Congo et République Démocratique du Congo. Ce travail présente une nouvelle classification de ces langues à travers l’étude du lexique. Nous avons ainsi constitué une base de données de 100 mots appartenant au vocabulaire de base pour les 207 langues retenues. Plusieurs arbres ont été générés par l’application des algorithmes Neighbor-Joining (Saitou et Nei, 1987) et Neighbor-Net (Bryant et Moulton, 2004). L’étude de la classification des langues du Nord-Ouest a permis de mieux comprendre les relations de proximité linguistiques qui existent entre les langues parlées dans cette région. De même, l’analyse de la classification a permis de proposer un schéma de migrations des langues bantu. / This dissertation is presenting a linguistic classification based on phylogenetic methods borrowed from biology. The sample of languages considered here belongs to the Bantu family, a linguistic sub branch of Niger-Congo languages spoken in Africa. Numerous publications have shown a complexity and the diversity of Bantu languages. Our study focus on the North-West region which includes the following countries: Cameroon, Equatorial Guinea, Gabon, Congo and Democratic Republic of Congo. This new classification is based on the comparison of lexical items. We have organized a database including 100 words from the basic vocabulary for 207 languages. Several tree representations were obtained by using Neighbor-Joining (Saitou and Nei, 1987) and Neighbor-Net (Bryant and Moulton, 2004) algorithms.This study allows us to get a better understanding of the linguistic proximity of these languages. It also provides a historical scenario for Bantu migrations.

Mémoire numérisé par la Division de la gestion de documents et des archives de l'Université de Montréal.

Les milliers d’espèces de microorganismes présentes dans les océans sont essentiellement connus pour être planctoniques ou benthiques. Moins décrits, de nombreux micro-organismes colonisent également la surface et le tube digestif des macro-organismes marins, formant des communautés appelées microbiomes. Ces microbiomes ont des conséquences cruciales sur la fitness de leur hôte. Les récents progrès en biologie moléculaire ont ouvert la voie à une caractérisation des différentes facettes de sa biodiversité, à la fois taxonomique, phylogénétique, et fonctionnelle. L’objectif de cette thèse est donc de caractériser la biodiversité des microbiomes cutanés des organismes marins, d’identifier ses échelles de variabilité, ses déterminants, et son importance à l’échelle de l’écosystème. Dans un premier temps j’ai mesuré l’efficacité d’indices de biodiversité à détecter des signaux écologiques dans le cas spécifique de communautés microbiennes. Puis, j’ai décrit le microbiome cutané des principaux grands clades d’animaux marins (poissons téléostéens, cétacés et invertébrés de plusieurs classes). J’ai démontré que le microbiome cutané était très différent des communautés présentes dans l’eau environnante. J’ai aussi montré qu’il était variable, à la fois entre individus et entre espèces, mais ne présentait pas de patron de phylosymbiose. Enfin, j’ai évalué la contribution de la diversité des microbiomes cutanés à la diversité de la communauté microbienne globale d’un écosystème corallien. J’ai ainsi démontré que les animaux marins hébergent collectivement une richesse microbienne presque vingt fois supérieure à celle de l’eau les environnant, et 75% de la richesse phylogénétique à l’échelle de l’écosystème. Dans un contexte d’érosion massive de la diversité des macro-organismes marins, ces résultats soulignent la nécessité d’évaluer plus exhaustivement la biodiversité microbienne marine et sa vulnérabilité face aux pressions anthropiques. / Oceans contain thousands of microbial species playing crucial roles for the functioning of the marine ecosystem. These microorganisms are present everywhere in the water column. Some microorganisms also colonize the surface and the digestive tract of marine macro-organisms, forming communities called microbiomes. These microbiomes have positive effects for their host’s fitness. The diversity of these marine animal surface microbiome is still largely understudied, despite recent progress in molecular biology that now permits to fully assess its different facets of biodiversity, i.e. taxonomic, phylogenetic and functional. The goal of this thesis is therefore to describe the diversity of the surface microbiome of marine animals, to assess its variability at different levels, as well as its determinants, and the significance of such diversity at the ecosystem’s scale. Firstly, I have assessed the efficiency of various diversity indices to detect ecological signals in the specific case of microbial communities. Secondly, I have described the surface microbiome of major marine animal clades (teleostean fishes, cetaceans and several classes of invertebrates). I found that these microbiomes are highly distinct from the surrounding planktonic communities. I demonstrated that these microbiomes are variable both between individuals from the same species and between species, but do not show a phylosymbiosis pattern. Last, I assessed the contribution of surface microbiomes to the global microbial community at the scale of a coral reef ecosystem. I demonstrated that marine animal surfaces host almost twenty times more microbial species than the water column, and 75% of the phylogenetic richness present in the ecosystem. In a context of massive erosion of marine macroscopic organisms, it is therefore urgent to exhaustively assess marine microbial biodiversity and its vulnerability facing anthropic pressures.