Mardi 14 décembre à 10h 15

Amphithéâtre de l'INRIA Rhône Alpes 655 avenue de l'Europe 38330 Montbonnot Saint Martin

Algorithmes incrémentaux pour l'alignement et la phylogénie de grandes familles de séquences homologues

Jean-François Dufayard, projet Helix, INRIA Rhône-Alpes

sous la direction de Manolo Gouy (UMR 5558, université Claude Bernard, Lyon) et François Rechenmann (INRIA Rhône-Alpes)

Jury

Michel Adiba, examinateur

Alain Guénoche, rapporteur

Sege Hazout, rapporteur

Guy Perrière, examinateur

Denis Trystram, examinateur

François Rechenmann, directeur de thèse

Résumé

La gestion d'une famille de séquences homologues consiste la plupart du temps à calculer l'alignement multiple puis l'arbre phylogénétique des séquences, ainsi que mettre ces données à jour lorsque de nouvelles séquences sont ajoutées à la famille.

Pour des familles de taille réduite (environ inférieure à 2000 gènes), les algorithmes existants pour le calcul des alignements multiples et la construction des arbres phylogénétiques répondent bien aux besoins des biologistes. Cependant, un problème de gestion se pose pour des familles de taille plus importante. Lorsqu'une nouvelle séquence doit être ajoutée à une famille existante, la seule solution est actuellement de recalculer l'alignement multiple et de reconstruire l'arbre phylogénétique intégralement. Cette solution n'est pas concrètement utilisable pour des familles de gènes homologues pouvant atteindre la taille de plusieurs dizaines de milliers de membres.

Des algorithmes incrémentaux pour le calcul d'alignements multiples et la construction d'arbres phylogénétiques ont été développés dans le cadre de ce travail de thèse. Lorsqu'une séquence est ajoutée dans une famille, l'alignement et l'arbre sont modifiés et non recalculés. Cela permet d'une part d'éviter une partie des redondances de calcul, et d'autre part d'être plus réaliste vis-à-vis de l'utilisation qui est faîte de ce type d'algorithmes. Ces algorithmes ont été implémentés dans un logiciel appelé « Mentalign ». « Mentalign » a été testé sur de nombreuses familles de séquences similaires issues des bases de données.

Abstract

The management of similar sequence families consists in computing a mutliple alignment and a phylogenetic tree for each family, and to add new sequences of the family in both the structures.

For small families (less than 2000 sequences), existing algorithms are efficient enough for biologists needs. But several problems occur for larger families. First, for families larger than 2000 sequences, existing algorithms are most of the time unable to compute a result in a reasonnable time. And when new sequences are added in a family, the only solution with these algorithms is to recompute entirely the alignment and the tree.

In order to solve this problem, incremental algorithms has been developped. They are able to add new sequences to an alignment and a tree in a short time, avoiding redondant computations. These algorithms have been implemented in a software named "Mentalign", and have been tested on several different families.