• Langue : Français
• Discipline : Informatique
• Identifiant : Inconnu
• Type de thèse : Doctorat
• Date de soutenance : 01/01/2000

Résumé en langue originale

Nous nous interessons dans cette these a la conception d'une mesure de dissimilarite entre sequences genetiques. La methode la plus classique pour comparer de tels objets biologiques est de realiser un alignement. L'inconvenient est que l'ordre de lecture des sequences est respecte et que la comparaison a lieu sur des bases au lieu de considerer des segments. On ne peut donc pas detecter d'evenements remaniant les sequences tels que la duplication ou l'inversion. D'autres methodes, telles que les distances par rearrangements, prennent en compte ces evenements mais elles necessitent de connaitre a priori les segments mis en jeu. Nous proposons une approche differente : le concept de distance de transformation. La mesure est basee sur un script transformant une sequence s en une sequence t par l'application d'une suite d'operations sur des segments similaires. Les segments sont detectes automatiquement. En associant un poids a chaque operation, on mesure le poids d'un script comme la somme des poids de ses operations. La mesure de la distance de transformation est definie comme le poids du script de poids minimal. Le concept de distance de transformation est tres flexible car il est possible de definir une instance particuliere en choisissant un jeu d'operations et des poids adaptes a un contexte biologique precis. Le script associe a la distance peut etre interprete comme le moyen le plus efficace d'obtenir t a partir de s. En ce sens, la distance de transformation est etroitement liee aux idees de la compression de donnees et de la theorie algorithmique de l'information. Nous detaillons des algorithmes pour le calcul de la distance dans le cas ou deux operations sont permises : l'une fournit des segments communs a s et t, tandis que l'autre fournit les segments propres a t. Nous discutons precisement la maniere dont les poids doivent etre definis puis nous appliquons notre mesure a une analyse phylogenetique des isopodes terrestres.