Spelling suggestions: "subject:"famille dde gènes"" "subject:"famille dee gènes""
1 |
Approches algorithmiques pour l’inférence d’histoires de duplication en tandem avec inversions et délétions pour des familles multigéniquesLajoie, Mathieu 08 1900 (has links)
[Français] Une fraction importante des génomes eucaryotes est constituée de Gènes Répétés en Tandem (GRT). Un mécanisme fondamental dans l’évolution des GRT est la recombinaison inégale durant la méiose, entrainant la duplication locale (en tandem) de segments chromosomiques contenant un ou plusieurs gènes adjacents.
Différents algorithmes ont été proposés pour inférer une histoire de duplication en
tandem pour un cluster de GRT. Cependant, leur utilisation est limitée dans la pratique, car ils ne tiennent pas compte d’autres événements évolutifs pourtant fréquents, comme les inversions, les duplications inversées et les délétions.
Cette thèse propose différentes approches algorithmiques permettant d’intégrer ces
événements dans le modèle de duplication en tandem classique. Nos contributions sont
les suivantes:
• Intégrer les inversions dans un modèle de duplication en tandem simple (duplication
d’un gène à la fois) et proposer un algorithme exact permettant de calculer
le nombre minimal d’inversions s’étant produites dans l’évolution d’un cluster de
GRT.
• Généraliser ce modèle pour l’étude d’un ensemble de clusters orthologues dans
plusieurs espèces.
• Proposer un algorithme permettant d’inférer l’histoire évolutive d’un cluster de GRT en tenant compte des duplications en tandem, duplications inversées, inversions
et délétions de segments chromosomiques contenant un ou plusieurs gènes adjacents. / [English] Tandemly arrayed genes (TAGs) represent an important fraction of most genomes. A fundamental mechanism at the origin of TAG clusters is unequal crossing-over during meiosis, leading to the duplication of chromosomal segments containing one or many adjacent genes. Such duplications are called tandem duplications, as the duplicated segment is placed next to the original one on the chromosome.
Different algorithms have been proposed to infer the tandem duplication history of
a TAG cluster. However, their applicability is limited in practice since they do not take
into account other frequent evolutionary events such as inversion, inverted duplication and deletion.
In this thesis, we propose different algorithmic approaches allowing to integrate these evolutionary events in the original tandem duplication model of evolution. Our contributions are summarized as follows:
• We integrate inversion events in a tandem duplication model restricted to single
gene duplications, and we propose an exact algorithm allowing to compute the minimum number of inversions explaining the evolution of a TAG cluster.
• We generalize this model to the study of orthologous TAG clusters in different species.
• We propose an algorithm allowing to infer the evolutionary history of a TAG cluster
through tandem duplication, inverted duplication, inversion and deletion of
chromosomal segments containing one or many adjacent genes.
|
2 |
Approches algorithmiques pour l’inférence d’histoires de duplication en tandem avec inversions et délétions pour des familles multigéniquesLajoie, Mathieu 08 1900 (has links)
[Français] Une fraction importante des génomes eucaryotes est constituée de Gènes Répétés en Tandem (GRT). Un mécanisme fondamental dans l’évolution des GRT est la recombinaison inégale durant la méiose, entrainant la duplication locale (en tandem) de segments chromosomiques contenant un ou plusieurs gènes adjacents.
Différents algorithmes ont été proposés pour inférer une histoire de duplication en
tandem pour un cluster de GRT. Cependant, leur utilisation est limitée dans la pratique, car ils ne tiennent pas compte d’autres événements évolutifs pourtant fréquents, comme les inversions, les duplications inversées et les délétions.
Cette thèse propose différentes approches algorithmiques permettant d’intégrer ces
événements dans le modèle de duplication en tandem classique. Nos contributions sont
les suivantes:
• Intégrer les inversions dans un modèle de duplication en tandem simple (duplication
d’un gène à la fois) et proposer un algorithme exact permettant de calculer
le nombre minimal d’inversions s’étant produites dans l’évolution d’un cluster de
GRT.
• Généraliser ce modèle pour l’étude d’un ensemble de clusters orthologues dans
plusieurs espèces.
• Proposer un algorithme permettant d’inférer l’histoire évolutive d’un cluster de GRT en tenant compte des duplications en tandem, duplications inversées, inversions
et délétions de segments chromosomiques contenant un ou plusieurs gènes adjacents. / [English] Tandemly arrayed genes (TAGs) represent an important fraction of most genomes. A fundamental mechanism at the origin of TAG clusters is unequal crossing-over during meiosis, leading to the duplication of chromosomal segments containing one or many adjacent genes. Such duplications are called tandem duplications, as the duplicated segment is placed next to the original one on the chromosome.
Different algorithms have been proposed to infer the tandem duplication history of
a TAG cluster. However, their applicability is limited in practice since they do not take
into account other frequent evolutionary events such as inversion, inverted duplication and deletion.
In this thesis, we propose different algorithmic approaches allowing to integrate these evolutionary events in the original tandem duplication model of evolution. Our contributions are summarized as follows:
• We integrate inversion events in a tandem duplication model restricted to single
gene duplications, and we propose an exact algorithm allowing to compute the minimum number of inversions explaining the evolution of a TAG cluster.
• We generalize this model to the study of orthologous TAG clusters in different species.
• We propose an algorithm allowing to infer the evolutionary history of a TAG cluster
through tandem duplication, inverted duplication, inversion and deletion of
chromosomal segments containing one or many adjacent genes.
|
3 |
Algorithmes pour la réconciliation d’un arbre de gènes avec un arbre d’espècesDoyon, Jean-Philippe 04 1900 (has links)
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.
|
4 |
Algorithmes pour la réconciliation d’un arbre de gènes avec un arbre d’espècesDoyon, Jean-Philippe 04 1900 (has links)
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.
|
Page generated in 0.0707 seconds