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.
