Ceratomyxa shasta infects salmonids in the Pacific Northwest (PNW) of North America, occasionally causing losses in wild and captive populations. Host-specific parasite genotypes (O, I, II, III) were previously characterized molecularly using markers in the ribosomal DNA and phenotypically by type host in the Klamath River, CA/OR. This thesis sough to re-examine the composition of the parasite population elsewhere in the PNW and to further evaluate the host specificity of each genotype. I surveyed salmonids native to the PNW primarily from the Fraser, the Columbia and the Sacramento River basins. I also conducted sentinel studies on the Willamette and Deschutes Rivers that exposed native and non-native salmonids to parasite populations above and below migration barriers. These studies expanded upon the known host range of each genotype: O was specific to rainbow/steelhead (Oncorhynchus mykiss) and coastal cutthroat trout (O. clarkii); I was specific with Chinook salmon (O. tshawytscha); II was non-specific, being detected in six species, but predominating in coho (O. kitsuch), chum (O. keta), and pink (O. gorbuscha) salmon; and III was also non-specific infecting many native and non-native salmonids. Hosts infected with genotype III were considered “adequate” if myxospore development occurred, and included brook char (Salvelinus fontinalis), brown (Salmo trutta), rainbow, cutthroat, and steelhead trout; but Chinook, kokanee/sockeye (O. nerka) and Atlantic salmon (Salmon salar) were less suitable. The distribution, life history, and phylogenetic traits of each salmonid host are factors that potentially explain the host specificity and the spatial and temporal patterns of each genotype. Data collected in this thesis provide evidence that host-specific C. shasta coevolved with Pacific salmonids, adapting unique host-parasite relationships over time. / Graduation date: 2012

Bonobos (Pan paniscus) are threatened with extinction. They are the largest primates, and the only apes (except human), of the southern bank of the Congo Basin. Along with chimpanzees, they are our closest living relatives and are studied by anthropologists to include/understand our hominid origins; but what about their functional role in the forest? Would their disappearance have serious consequences for forest ecology? Answering this question is the aim of this new project, with several years of observations of a free-ranging habituated group of bonobos on the LuiKotale research station (DR Congo). In this tropical rainforest, the very great majority of plants need animals to reproduce and disperse their seeds. Bonobos are the largest frugivorous animals in this region, after elephants. During its life, each bonobo will ingest and disperse nine tons of seeds, from more than 91 species of lianas, grass, trees and shrubs. These seeds will travel 24 hours in the bonobo digestive tract, which will transfer them over several kilometers (mean 1.3 km; max: 4.5 km), far from their parents, where they will be deposited intact in their feces. These dispersed seeds remain viable, germinate better and more quickly than unpassed seeds. For those seeds, diplochory with dung-beetles (Scarabaeidae) imrpoves post-dispersal survival. Certain plants such as Dialium may even be dependent on bonobos to activate the germination of their seeds, characterized by tegumentary dormancy. The first parameters of the effectiveness of seed dispersal by bonobos are present. Behavior of the bonobo could affect the population structure of plants whose seeds they disperse. The majority of these zoochorous plants cannot recruit without dispersal and the homogeneous spatial structure of the trees suggests a direct link with their dispersal agent. Few species could replace bonobos in terms of seed dispersal services, just as bonobos could not replace elephants. There is little functional redundancy between frugivorous mammals of the Congo, which face severe human hunting pressures and local exctinction. The defaunation of the forests, leading to the empty forest syndrome, is critical in conservation biology, as will be illustrated here. The disappearance of the bonobos, which disperse seeds of 65% of the tree species in these forests, or 11.6 million individual seeds during the life of each bonobo, will have consequences for the conservation of the Congo rainforest

Submitted by Erika Cruz (erikakato@globo.com) on 2018-01-12T13:45:25Z No. of bitstreams: 1 Tese Érika Mayumi Kato Cruz Final.pdf: 3238940 bytes, checksum: 84bdc9eb0f173ba3a93ca437e9f343a0 (MD5) / Approved for entry into archive by Pamela Beltran Tonsa (pamela.tonsa@fgv.br) on 2018-01-18T10:59:43Z (GMT) No. of bitstreams: 1 Tese Érika Mayumi Kato Cruz Final.pdf: 3238940 bytes, checksum: 84bdc9eb0f173ba3a93ca437e9f343a0 (MD5) / Made available in DSpace on 2018-01-18T12:17:14Z (GMT). No. of bitstreams: 1 Tese Érika Mayumi Kato Cruz Final.pdf: 3238940 bytes, checksum: 84bdc9eb0f173ba3a93ca437e9f343a0 (MD5) Previous issue date: 2017-12-18 / A presente tese teve como foco o estudo dos aspectos coevolucionários em redes interorganizacionais de cooperação e sua relação com as configurações e práticas de governança da rede. A literatura sobre coevolução aponta para um entendimento macro do fenômeno nos estudos sobre redes, levantando carências no que tange à análise dos seus microfundamentos, com destaque para as relações intrarede e interfirmas. De forma complementar, verificam-se na literatura de redes oportunidades de pesquisa no que diz respeito à análise dos aspectos sociais que regem os relacionamentos em rede, bem como aos fatores que influenciam o alcance de resultados individuais e coletivos de seus participantes. A tese objetivou, assim, aprofundar o conhecimento sobre dinâmica de redes por meio de estudo de casos múltiplos em Arranjos Produtivos Locais (APLs) no estado de São Paulo e Paraná. O objetivo consistiu em analisar a relação entre a configuração das redes empresariais e de sua governança com a coevolução das empresas participantes e das redes como um todo. Dado o caráter indutivo do estudo, este fez uso da abordagem de construção de teoria por meio de estudo de caso proposta por Eisenhardt (1989). Os resultados apontam para a existência de aspectos coevolucionários nos relacionamentos em rede, com destaque para o compartilhamento de custos, assim como ganhos relativos a troca de conhecimentos e experiências. A configuração da estrutura e das práticas de governança dos arranjos, por fim, influenciam na coevolução na medida em que contribui para a publicização das ações e o alinhamento de interesses dos agentes envolvidos. / This thesis focused on the study of coevolutionary aspects in interorganizational cooperation networks and its relation with the network governance practices and configurations. The literature on coevolution points to a macro understanding of the phenomenon in the studies on networks, raising deficiencies regarding the analysis of its micro-foundations, with emphasis on intrarede and interfirm relations. In a complementary way, the network literature offers research opportunities in the analysis of social aspects that govern network relationships, as well as the factors that influence the achievement of individual and collective results of its participants. The aim of this thesis was to deepen the knowledge about network dynamics through a study of multiple cases in Local Productive Arrangements (APLs) in the states of São Paulo and Paraná. The objective was to analyze the relationship between the configuration of the business networks and their governance with the coevolution of participating companies and the networks as a whole. Given the inductive nature of the study, it made use of the theory-building approach by means of a case study proposed by Eisenhardt (1989). The results point to the existence of coevolutionary aspects in network relationships, with emphasis on cost sharing, as well as gains related to the exchange of knowledge and experiences. The configuration of the structure and governance practices of the arrangements, lastly, influence on coevolution in so far as it contributes to the publicity of actions and the alignment of interests of the involved agents.

[pt] Esta dissertação investiga a aplicação de Algoritmos Genéticos e de Co-Evolução Cooperativa na otimização da programação da produção em refinarias de petróleo. Refinarias de petróleo constituem um dos mais importantes exemplos de plantas contínuas multiproduto, isto é, um sistema de processamento contínuo gerador de múltiplos produtos simultâneos. Uma refinaria, em geral, processa um ou mais tipos de petróleo, produzindo uma série de produtos derivados, como o GLP (gás liquefeito de petróleo), a nafta, o querosene e o óleo diesel. Trata- se de um problema complexo de otimização, devido ao número e diversidade de atividades existentes e diferentes objetivos. Além disso, neste problema, algumas atividades dependem de que outras atividades já tenham sido planejadas para que possam então ser planejadas. Um caso típico é o das retiradas de produtos de uma unidade de processo, que dependem de que a carga já tenha sido planejada, assim como em qual campanha a unidade estará naquele instante. Por isso, o uso de modelos revolucionários convencionais, como os baseados em ordem, pode gerar muitas soluções inválidas, que deverão ser posteriormente corrigidas ou descartadas, comprometendo o desempenho e a viabilidade do algoritmo. O objetivo do trabalho foi, então, desenvolver um modelo evolucionário para otimizar a programação da produção (scheduling), segundo objetivos bem definidos, capaz de lidar com as restrições do problema, gerando apenas soluções viáveis. O trabalho consistiu em três etapas principais: um estudo sobre o refino de petróleo e a programação da produção em refinarias; a definição de um modelo usando algoritmos genéticos e co-evolução cooperativa para otimização da programação da produção e a implementação de uma ferramenta para estudo de caso. O estudo sobre o refino e a programação da produção envolveu o levantamento das várias etapas do processamento do petróleo em uma refinaria, desde o seu recebimento, destilação e transformação em diversos produtos acabados, que são então enviados a seus respectivos destinos. Neste estudo, também foi levantada a estrutura de tomada de decisão em uma refinaria e seus vários níveis, diferenciando os objetivos destes níveis e explicitando o papel da programação da produção nesta estrutura. A partir daí, foram estudadas em detalhes todas as atividades que normalmente ocorrem na refinaria e que são definidas na programação, e seus papéis na produção da refinaria. A decisão de quando e com que recursos executar estas atividades é o resultado final da programação e, portanto, a saída principal do algoritmo. A modelagem do algoritmo genético consistiu inicialmente em um estudo de representações utilizadas para problemas de scheduling. O modelo coevolucionário adotado considera a decomposição do problema em duas partes e,portanto, emprega duas populações com responsabilidades diferentes: uma é responsável por indicar quando uma atividade deve ser planejada e a outra é responsável por indicar com quais recursos essa mesma atividade deve ser realizada. A primeira população teve sua representação baseada em um modelo usado para problemas do tipo Dial-A-Ride (Moon et al, 2002), que utiliza um grafo para indicar à função de avaliação a ordem na qual o planejamento deve ser construído. Esta representação foi elaborada desta forma para que fosse levada em conta a existência de restrições de precedência (atividades que devem ser planejadas antes de outras), e assim não fossem geradas soluções inválidas pelo algoritmo. A segunda população, que se responsabiliza pela alocação dos recursos para a execução das atividades, conta com uma representação onde os operadores genéticos podem atuar na ordem de escolha dos recursos que podem realizar cada uma das atividades. Finalmente, des / [en] This work investigates the use of Genetic Algorithms and Cooperative Coevolution in refinery scheduling optimization. Oil refineries are one of the most important examples of multiproduct continuous plants, that is, a continuous processing system that generates a number of products simultaneously. A refinery processes various crude oil types and produces a wide range of products, including LPG (liquefied petroleum gas), gasoline, kerosene and diesel. It is a complex optimization problem, mainly due to the number of different tasks involved and different objective criteria. In addition, some of the tasks have precedence constraints that require other tasks to be scheduled first. For example, in order to schedule a task that transfers one of the yields of a certain crude distillation unit, both the task that feeds the crude oil into the unit and the task that sets the unit`s current operation mode must already be scheduled. Therefore, applying traditional evolutionary models, like the order- based ones, can create many infeasible solutions that will have to be corrected or rejected later on, thereby jeopardizing the algorithm performance and feasibility. The main goal was the development an evolutionary model satisfying well-defined objectives, which would optimize production scheduling and address the various constraints entailed in the problem, thus generating only feasible solutions. This work consisted on three main steps: a survey on crude oil refining and refinery scheduling; the development of a cooperative coevolutionary model to optimize the refinery scheduling and the development of a software tool for case studies. The study about refining and scheduling involved gathering information about the existent processes in a refinery, starting from the arrival of crude oil, its distillation and transformation into several products and, finally, the delivery of these products to their respective destination. The levels of decision making in a refinery were surveyed too, in order to identify the main goals for each one, and how the scheduling level fits into the structure as whole. Then, all the routine scheduling tasks and their roles in a refinery were carefully studied. The decision of when and how to assign those tasks is the final output of the scheduling task, so it must be the main output of the algorithm too. The development of the evolutionary model consisted of a survey on some of the most common evolutionary approaches to scheduling. The adopted coevolutionary model breaks the problem down into two parts, thus using two species with different responsibilities: One is responsible for deciding when a task should be scheduled, while the other is responsible for assigning a resource for this task. The first species representation was based on a model used for the Dial-a- Ride (Moon et al, 2002) kind of problems, and uses a graph to help the fitness evaluation function find the right order in which to schedule the tasks. This representation was devised in such a way that the precedence constraints were satisfied and no infeasible solutions were generated. The representation of the second species, which assigns resources for the tasks, let genetic operators change the selection order when picking a resource for a task. Finally, a software tool was developed to be used for implement this model and for performing a case study. This case study should comprise all the needed characteristics, in order to test the quality of the representation as well as evaluate the results. A simple refinery was designed, containing all equipment types, tasks and constraints found in a real-world refinery. The constraints mentioned are the precedence constraints, handled by the graph used by the first species, plus other operational constraints found in refinery scheduling. It was possible, then, to see the decoding of chromosomes into feasible solutions, always satisfying all the constraints. Several tests

Dans un contexte environnemental anthropisé, fragmenté et soumis à un changement climatique rapide, l’appréhension des processus d'adaptation locale des organismes marins par l'étude de zones de contact entre taxa proches constitue une approche privilégiée. Dans ces zones, des génotypes hybrides persistent malgré un état de maladaptation liée à des incompatibilités génétiques endogènes et/ou des barrières exogènes. L'histoire biogéographique complexe de la telline baltique Macoma balthica fait émerger quatre zones hybrides européennes, dont l'une, localisée autour de la Pointe Finistère (France), est le résultat d’un contact entre deux stocks génétiques ayant divergé en allopatrie. Ces divergences sont susceptibles de rompre la coadaptation entre génomes nucléaire et mitochondrial en raison de l'émergence d'incompatibilités mitonucléaires (MNIs). Ainsi, les sous-unités protéiques des cinq complexes de la chaine OXPHO sont codées à la fois par des gènes nucléaires et mitochondriaux, et une coévolution inter-génomique étroite est requise pour maintenir la production énergétique cellulaire. De précédentes données de transcriptomique dévoilent de probables MNIs chez M. balthica au niveau des complexes respiratoires I et V. Afin d’apporter des éléments de compréhension aux mécanismes de maintien des zones hybrides dans un contexte de pression anthropique, le présent travail se propose de tester l'hypothèse de putatives MNIs dans cette zone de contact. Pour cela, (i) six mitogénomes correspondant à cinq lignées haplotypiques divergentes en Europe ont été séquencés et l'architecture génomique a été étudiée conjointement à une cartographie des mutations des 13 gènes mitochondriaux, (ii) le niveau de transcription de 5 gènes nucléaires et 8 gènes mitochondriaux (complexe I à V) des individus hybrides a été comparé à celui des lignées parentales après détermination du statut d'hybridation de chaque individu (six populations françaises). A défaut d'apporter des éléments de réponses concrets quant à l'existence de MNIs chez M. balthica, et ses répercussions évolutives en terme de dépression d'hybridation, ce travail constitue un tremplin vers une étude approfondie de la zone hybride française en développant de nouveaux outils moléculaires, et de solides techniques expérimentales pour la conduite de futurs croisements artificiels. / In the anthropized, fragmented environmental context subject to rapid climate change, understand local adaptation processes of marine organisms by studying the contact zones between close taxa is a preferred approach. In these areas, hybrid genotypes persist despite a maladaptive state related to endogenous genetic incompatibilities and/or exogenous barrier. The complex biogeographic history of the Baltic tellin Macoma balthica leads to emergence of several European hybrid zones, one of which, located around the Pointe Finistère (France), is the result of the confluence of two genetic stocks that have diverged in allopatric. These divergences may have lead to the co-adaptation breakdown between nuclear and mitochondrial genomes due to the emergence of mito-nuclear incompatibilities (MNIs). Thus, the different protein subunits of the five OXPHO chain complexes are encoded by both nuclear and mitochondrial genes, and a tight inter-genomic coevolution is required to maintain the cellular energy production. Recent transcriptomic data unveil the existence of underlying MNIs in M. balthica, bearing by the respiratory complexes I and V. In order to provide some understanding clues of mechanisms in hybrid zone's maintenance in the context of human pressure, the present work aims to test the assumption of putative MNIs in this area. For this purpose, (i) six mitogenomes corresponding to five divergent haplotype lineages in Europe were sequenced and the genomic architecture has been studied jointly to a mapping mutation of the 13 mitochondrial genes, (ii) the level of transcription of 5 nuclear and 8 mitochondrial genes (complex I to V) of hybrid individuals was compared to the parental lineages after identification of the hybrid status of each individual (six french populations). For the lack of bringing concrete answers concerning the existence of MNIs in M. balthica, and its evolutionary effects in term of hybrid breakdown, this work is a springboard for a comprehensive study of the French hybrid zone by developing new molecular tools, and stable experimental technics for the realisation of future artificial crosses.

p, li { white-space: pre-wrap; } Evoluce v přírodě slouží jako zdroj inspirace pro tuto práci . Základní myšlenkou je využití generativní síly gramatik v kombinaci s evolučním přístupem . Nabyté znalosti jsou aplikovány na hledání strategií chování v rozmanitých prostředích . Stromy chování jsou modelem , který bývá běžně použit na řízení rozhodování různých umělých inteligencí . Tato práce se zabývá hledáním stromů chování , které budou řídit jedince řešící nasledující dva problémy : upravenou verzi problému cesty koněm šachovnicí a hraní hry Pirátské kostky . Při hledání strategie hráče kostek , byla použita konkurenční koevoluce . Důvodem je obtížnost návrhu spravedlivé fitness funkce hodnotící výkony hráčů .

Adaptive evolution of Toll-like receptors in birds Hana Velová, PhD thesis 6 Abstract Toll-like receptors (TLRs) are one of the key and presumably also evolutionary most original components of animal immune system. As Pattern recognition receptors they form the first line of innate immune defence against various pathogens. The proper receptor binding of pathogenic ligands is crucial for their correct recognition and for subsequent triggering of an appropriate immune response. Because there exists a direct interaction between the receptor surface and the pathogenic ligand, host-pathogen coevolution on molecular level can be predicted. Thus, through variability of their ligands, TLRs are exposed to extensive selective pressures that may be detected on both genetic and protein levels. Surprisingly, the variability we revealed in birds is even higher than previously expected based on the reports from other vertebrates, mainly mammals. In my doctoral thesis I summarise the results of my contribution to the avian TLR research. We were the first who experimentally verify the absence of functional TLR5 in several avian species and duplication of TLR7 in others. We finally resolved the origin of duplication in TLR1 and in TLR2 family. An important part of my research project focused on the prediction of potentially...

Les interactions font partie intégrante des écosystèmes. Que ce soit aux niveaux les plus fins, comme les protéines, ou les plus larges, comme les méta-communautés, il est possible de les regrouper en réseaux et d’en étudier la structure. Cela a permis de mettre en évidence que certaines structures sont observables à différents niveaux, c’est le cas par exemple des réseaux emboîtés. De plus, les réseaux d’interaction ont la spécificité de ne pas être fixes dans le temps et l’espace, ce qui leur confère un avantage de taille pour l’étude de l’évolution. Ils peuvent ainsi servir de support à l’études des mécanismes intervenants dans les processus évolutifs. Cependant, il n’existe pas encore de méthodologie ayant fait consensus sur l’utilisation des réseaux et leur analyse à différentes échelles d’organisation. Cette thèse se base sur l’hypothèse que les réseaux, de par leurs propriétés, sont pertinents à considérer pour comprendre l’évolution et ce à différentes échelles d’organisation, et offrent la possibilité de faire des liens entre chacune d’entre elles. L’approche basée sur les réseaux, combinée à l’utilisation de modèles théorique serait donc un outil méthodologique puissant dans l’élargissement des connaissances concernant les processus sous-jacents à l’évolution. La thèse qui suit composée de six chapitres dont le contenu est le suivant. Elle commence par un chapitre d’introduction aux concepts d’intérêts, notamment sur l’évolution et la coévolution. Le deuxième chapitre est une introduction à l’utilisation des réseaux en écologie, suivit par le troisième chapitre qui effectue une revue non exhaustive des méthodologies développées autour des réseaux d’interactions. Les chapitres suivants sont en quelque sorte une mise en pratique de ces méthodes et ce à différents niveaux d’organisation. Le quatrième chapitre revient sur une étape avortée de ce doctorat qui servira tout de même à la construction du modèle du chapitre suivant. Le cinquième chapitre se concentre sur la coévolution et son suivit au travers des réseaux d’interaction entre les bactéries et leurs virus. Enfin, le sixième chapitre traque l’évolution des communautés grâce à la structure des arbres phylogénétiques et structure des réseaux d’interactions au cours du temps. / Interactions are an integral part of ecosystems. Whether at the finest levels, such as proteins, or the broadest, such as meta-communities, it is possible to group them into networks and study their structure. This made it possible to demonstrate that certain structures can be observed at different levels, such as nested networks, for example. In addition, interaction networks have the property of not being fixed in time and space, which gives them a major advantage for the study of evolution. They can thus serve as a support for the study of the mechanisms involved in the evolutionary processes. However, there is not yet a methodology that has achieved consensus on the use of networks and their analysis at different organizational scales. This thesis is based on the hypothesis that networks, by virtue of their properties, are relevant to consider in order to understand evolution at different organizational scales, and offer the possibility of making links between each of them. The network-based approach, combined with the use of theoretical models, would therefore be a powerful methodological tool in expanding knowledge about the processes underlying evolution. The thesis which follows consists of six chapters whose content is as follows. It begins with an introductory chapter to the concepts of interest, in particular on evolution and coevolution. The second chapter is an introduction to the use of networks in ecology, followed by the third chapter which performs a non-exhaustive review of the methodologies developed around interaction networks. The following chapters are in a way a practical application of these methods at different levels of organization. The fourth chapter returns to an aborted stage of this doctorate which will nevertheless be used to construct the model of the following chapter. The fifth chapter focuses on coevolution and its follow-up through the interaction networks between bacteria and their viruses. Finally, the sixth chapter tracks the evolution of communities thanks to the structure of phylogenetic trees and the structure of interaction networks over time.

Une réconciliation entre un arbre de gènes et un arbre d’espèces décrit une histoire d’évolution des gènes homologues en termes de duplications et pertes de gènes. Pour inférer une réconciliation pour un arbre de gènes et un arbre d’espèces, la parcimonie est généralement utilisée selon le nombre de duplications et/ou de pertes. Les modèles de réconciliation sont basés sur des critères probabilistes ou combinatoires. Le premier article définit un modèle combinatoire simple et général où les duplications et les pertes sont clairement identifiées et la réconciliation parcimonieuse n’est pas la seule considérée. Une architecture de toutes les réconciliations est définie et des algorithmes efficaces (soit de dénombrement, de génération aléatoire et d’exploration) sont développés pour étudier les propriétés combinatoires de l’espace de toutes les réconciliations ou seulement les plus parcimonieuses. Basée sur le processus classique nommé naissance-et-mort, un algorithme qui calcule la vraisemblance d’une réconciliation a récemment été proposé. Le deuxième article utilise cet algorithme avec les outils combinatoires décrits ci-haut pour calculer efficacement (soit approximativement ou exactement) les probabilités postérieures des réconciliations localisées dans le sous-espace considéré. Basé sur des taux réalistes (selon un modèle probabiliste) de duplication et de perte et sur des données réelles/simulées de familles de champignons, nos résultats suggèrent que la masse probabiliste de toute l’espace des réconciliations est principalement localisée autour des réconciliations parcimonieuses. Dans un contexte d’approximation de la probabilité d’une réconciliation, notre approche est une alternative intéressante face aux méthodes MCMC et peut être meilleure qu’une approche sophistiquée, efficace et exacte pour calculer la probabilité d’une réconciliation donnée. Le problème nommé Gene Tree Parsimony (GTP) est d’inférer un arbre d’espèces qui minimise le nombre de duplications et/ou de pertes pour un ensemble d’arbres de gènes. Basé sur une approche qui explore tout l’espace des arbres d’espèces pour les génomes considérés et un calcul efficace des coûts de réconciliation, le troisième article décrit un algorithme de Branch-and-Bound pour résoudre de façon exacte le problème GTP. Lorsque le nombre de taxa est trop grand, notre algorithme peut facilement considérer des relations prédéfinies entre ensembles de taxa. Nous avons testé notre algorithme sur des familles de gènes de 29 eucaryotes. / A reconciliation between a gene tree and a species tree depicts an evolutionary scenario of the homologous genes in terms of gene duplications and gene losses. To infer such a reconciliation given a gene tree and a species tree, parsimony is generally used according to the number of gene duplications and/or losses. The combinatorial models of reconciliation are based on probabilistic or combinatorial criteria. The first paper defines a simple and more general combinatorial model of reconciliation which clearly identifies duplication and loss events and does not only induce the most parsimonious reconciliation. An architecture of all possible reconciliations is developed together with efficient algorithms (that is counting, randomization, and exploration) to study combinatorial properties of the space of all reconciliations or only the most parsimonious ones. Based on the classical birth-death process, an algorithm that computes the likelihood of a reconciliation has recently been proposed. The second paper uses this algorithm together with the combinatorial tools described above to compute efficiently, either exactly or approximately, the posterior probability of the reconciliations located in the considered subspace. Based on realistic gene duplication and loss rates and on real/simulated datasets of fungal gene families, our results suggest that the probability mass of the whole space of reconciliations is mostly located around the most parsimonious ones. In the context of posterior probability approximation, our approach is a valuable alternative to a MCMC method and can competes against a sophisticated, efficient, and exact computation of the probability of a given reconciliation. The Gene Tree Parsimony (GTP) problem is to infer a species tree that minimizes the number of duplications and/or losses over a set of gene family trees. Based on a new approch that explores the whole species tree space for the considered taxa and an efficient computation of the reconciliation cost, the third paper describes a Branch-and- Bound algorithm that solves exactly the GTP problem. When the considered number of taxa is too large, our algorithm can naturally take into account predefined relationships between sets of taxa. We test our algorithm on a dataset of eukaryotic gene families spanning 29 taxa.

Une réconciliation entre un arbre de gènes et un arbre d’espèces décrit une histoire d’évolution des gènes homologues en termes de duplications et pertes de gènes. Pour inférer une réconciliation pour un arbre de gènes et un arbre d’espèces, la parcimonie est généralement utilisée selon le nombre de duplications et/ou de pertes. Les modèles de réconciliation sont basés sur des critères probabilistes ou combinatoires. Le premier article définit un modèle combinatoire simple et général où les duplications et les pertes sont clairement identifiées et la réconciliation parcimonieuse n’est pas la seule considérée. Une architecture de toutes les réconciliations est définie et des algorithmes efficaces (soit de dénombrement, de génération aléatoire et d’exploration) sont développés pour étudier les propriétés combinatoires de l’espace de toutes les réconciliations ou seulement les plus parcimonieuses. Basée sur le processus classique nommé naissance-et-mort, un algorithme qui calcule la vraisemblance d’une réconciliation a récemment été proposé. Le deuxième article utilise cet algorithme avec les outils combinatoires décrits ci-haut pour calculer efficacement (soit approximativement ou exactement) les probabilités postérieures des réconciliations localisées dans le sous-espace considéré. Basé sur des taux réalistes (selon un modèle probabiliste) de duplication et de perte et sur des données réelles/simulées de familles de champignons, nos résultats suggèrent que la masse probabiliste de toute l’espace des réconciliations est principalement localisée autour des réconciliations parcimonieuses. Dans un contexte d’approximation de la probabilité d’une réconciliation, notre approche est une alternative intéressante face aux méthodes MCMC et peut être meilleure qu’une approche sophistiquée, efficace et exacte pour calculer la probabilité d’une réconciliation donnée. Le problème nommé Gene Tree Parsimony (GTP) est d’inférer un arbre d’espèces qui minimise le nombre de duplications et/ou de pertes pour un ensemble d’arbres de gènes. Basé sur une approche qui explore tout l’espace des arbres d’espèces pour les génomes considérés et un calcul efficace des coûts de réconciliation, le troisième article décrit un algorithme de Branch-and-Bound pour résoudre de façon exacte le problème GTP. Lorsque le nombre de taxa est trop grand, notre algorithme peut facilement considérer des relations prédéfinies entre ensembles de taxa. Nous avons testé notre algorithme sur des familles de gènes de 29 eucaryotes. / A reconciliation between a gene tree and a species tree depicts an evolutionary scenario of the homologous genes in terms of gene duplications and gene losses. To infer such a reconciliation given a gene tree and a species tree, parsimony is generally used according to the number of gene duplications and/or losses. The combinatorial models of reconciliation are based on probabilistic or combinatorial criteria. The first paper defines a simple and more general combinatorial model of reconciliation which clearly identifies duplication and loss events and does not only induce the most parsimonious reconciliation. An architecture of all possible reconciliations is developed together with efficient algorithms (that is counting, randomization, and exploration) to study combinatorial properties of the space of all reconciliations or only the most parsimonious ones. Based on the classical birth-death process, an algorithm that computes the likelihood of a reconciliation has recently been proposed. The second paper uses this algorithm together with the combinatorial tools described above to compute efficiently, either exactly or approximately, the posterior probability of the reconciliations located in the considered subspace. Based on realistic gene duplication and loss rates and on real/simulated datasets of fungal gene families, our results suggest that the probability mass of the whole space of reconciliations is mostly located around the most parsimonious ones. In the context of posterior probability approximation, our approach is a valuable alternative to a MCMC method and can competes against a sophisticated, efficient, and exact computation of the probability of a given reconciliation. The Gene Tree Parsimony (GTP) problem is to infer a species tree that minimizes the number of duplications and/or losses over a set of gene family trees. Based on a new approch that explores the whole species tree space for the considered taxa and an efficient computation of the reconciliation cost, the third paper describes a Branch-and- Bound algorithm that solves exactly the GTP problem. When the considered number of taxa is too large, our algorithm can naturally take into account predefined relationships between sets of taxa. We test our algorithm on a dataset of eukaryotic gene families spanning 29 taxa.