Algorithmes bioinformatiques pour la reconstruction d'arbres consensus et de super-arbres multiples

Tahiri, Nadia (2019). « Algorithmes bioinformatiques pour la reconstruction d'arbres consensus et de super-arbres multiples » Thèse. Montréal (Québec, Canada), Université du Québec à Montréal, Doctorat en informatique.

Fichier(s) associé(s) à ce document :
[img]
Prévisualisation
PDF
Télécharger (9MB)

Résumé

Les arbres phylogénétiques (c.-à-d., arbres additifs ou X-arbres) contiennent des informations importantes caractérisant l'évolution spécifique des familles de gènes étudiées. Cependant, un arbre consensus d'espèces fiable ne peut pas être inféré à partir d'un alignement de séquences multiples d'une famille de gènes unique ou de la concaténation des alignements correspondant à des familles de gènes ayant des histoires évolutives différentes. Ces histoires évolutives peuvent différer, par exemple, à cause des transferts horizontaux subis par certains gènes ou à cause de l'ancienne duplication génique qui provoque l'émergence de paralogues dans un génome. De nombreuses méthodes ont été proposées pour déduire un arbre consensus unique pour un ensemble d'arbres phylogénétiques donné. L'application de ces méthodes classiques peut donc conduire à la perte d'information sur les histoires évolutives spécifiques qui caractérisent certaines familles de gènes ou certains groupes de familles de gènes. Ainsi, la problématique d'inférence des arbres consensus multiples devient pertinente. Dans cette thèse de doctorat, nous présentons de nouveaux algorithmes permettant de raffiner le processus d'inférence d'arbres consensus et de super-arbres obtenus par regroupement d'arbres phylogénétiques. L'avantage de notre approche par rapport aux approches classiques, qui retournent comme solution un arbre consensus ou un super-arbre unique, est qu'elle permet de déterminer un ou plusieurs arbres consensus ou super-arbres représentant au mieux le groupe d'arbres phylogénétiques fournis en entrée. Nous montrons comment les algorithmes de regroupement classiques, les k-moyennes et les k-médoïdes, peuvent être modifiés pour partitionner des arbres phylogénétiques définis sur un même ensemble de feuilles (problématique de l'arbre consensus) ou sur des ensembles de feuilles différents, mais mutuellement chevauchants (problématique de super-arbre). Dans notre étude, la distance topologique de Robinson et Foulds (classique et normalisée) sera utilisée pour comparer des arbres phylogénétiques. Les trois nouveautés majeures de cette thèse sont les suivantes : 1) le développement des algorithmes rapides de construction d'arbres consensus et de super-arbres multiples; 2) l'adaptation des indices de validité des clusters populaires (c.-à-d., l'indice de Calinski-Harabasz, l'indice Silhouette et la statistique Gap) pour leur utilisation dans les algorithmes de regroupement d'arbres phylogénétiques; 3) l'application des algorithmes proposés aux données réelles montrant comment ils peuvent être utilisés pour détecter des transferts horizontaux de gènes ou des événements d'hybridation. _____________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : arbre phylogénétique, arbre consensus, super-arbre, distance de Robinson et Foulds, algorithme des k-moyennes, algorithme des k-médoïdes, partitionnement d'arbres

Type: Thèse ou essai doctoral accepté
Informations complémentaires: La thèse a été numérisée telle que transmise par l'auteur.
Directeur de thèse: Makarenkov, Vladimir
Mots-clés ou Sujets: Arbre consensus / Méthode des super-arbres / Réseaux phylogénétiques / Bio-informatique / Algorithmes / Distance Robinson–Foulds
Unité d'appartenance: Faculté des sciences > Département d'informatique
Déposé par: Service des bibliothèques
Date de dépôt: 02 mars 2020 11:41
Dernière modification: 02 mars 2020 11:41
Adresse URL : http://archipel.uqam.ca/id/eprint/13294

Statistiques

Voir les statistiques sur cinq ans...