Utilisation des algorithmes genetiques pour l'analyse de sequences biologiques

Ce travail a ete consacre aux alignements de sequences (proteines et arns). Il s'agit d'un probleme complexe combinant des elements de biologie (definition d'un alignement correct) et d'informatique (elaboration d'une strategie d'optimisation). L'aspect algorithmique a consiste a adapter une methode d'optimisation generale connue sous le nom d'algorithme genetique au probleme des alignements de sequences. Les algorithmes genetiques sont des methodes d'optimisation stochastiques inspirees par le phenomene de selection naturelle. A l'aide d'un tel algorithme, il est possible d'optimiser l'alignement d'un groupe de sequences, compte tenu de n'importe quel critere de qualite (fonction objective). Saga s'est avere plus efficace qu'aucune autre alternative pour l'optimisation des fonctions courantes. Afin d'utiliser au maximum les capacites de notre algorithme, nous avons defini une nouvelle fonction (coffee : consistancy based objective function for alignment evaluation). Coffee a ete valide en utilisant des groupes de sequences pour lesquels existent des alignements de reference. Il en decoule que saga utilise avec coffee produit des alignements qui sont parmis les meilleurs disponibles aujourd'hui. Le second projet a consiste a adapter saga pour rendre possible l'alignement de deux sequences d'arn compte tenu de leurs structures secondaires. La correction des alignements obtenus a ete validee par l'utilisation d'alignements de references fait par des specialistes. Raga n'est pas la seule methode de ce type, mais a notre connaissance il s'agit du seul algorithme capable d'utiliser des sequences tres longues (jusqu'a 2 kbases) et aussi divergeantes (moins de 30% d'homologie).