Abstract FR:

Cette these porte sur la mise en oeuvre et le developpement d'outils algorithmiques et combinatoires pour l'analyse des sequences de nucleotides. Nous developpons des algorithmes de recherche de differents types de repetitions, utilisant la structure d'arbre des suffixes. Ces algorithmes sont appliques a la compression des sequences de nucleotides et a la prediction de structure secondaire d'arn. Nous nous interessons aussi a l'enumeration combinatoire de ces structures, en utilisant les series generatrices. Les algorithmes classiques de compression sont inefficaces sur les sequences genetiques. Nous developpons le premier algorithme de compression dedie a ce type de donnees. Celui-ci, base sur la detection et le codage des repetitions simples et palindromiques, donne de bons resultats sur des sequences contenant de longues repetitions. Nous l'etendons ensuite avec des primitives statistiques pour couvrir les regions non codees. Nous definissons aussi un nouveau mode de compression, le mode vertical, ou le codage d'une sequence est realise par rapport a une autre sequence. Dans une seconde partie de notre these, nous traitons le probleme de la prediction des structures secondaires d'arn. Nous nous interessons a l'automatisation de l'approche comparative qui consiste a rechercher une structure secondaire commune a un ensemble de sequences. Nous developpons un algorithme recursif base sur l'approche diviser pour regner. Des criteres de selection des palindromes sont definis, bases sur leur longueur et leur nombre de mutations compensatoires. L'algorithme est teste et valide sur un ensemble d'arn ribosomaux 16s et 23s : la majorite des helices communes sont isolees. Dans le cas de l'arn de transfert, une seule iteration suffit pour isoler les quatre helices. La derniere partie porte sur l'enumeration de differents types de structures secondaires d'arn. Celles-ci verifient un nombre minimal de h appariements adjacents et de b bases dans les boucles terminales. En utilisant les series generatrices, nous generalisons les resultats obtenus par waterman (cas h = b = 1 et h = 1, b = 2). Ce dernier utilisait l'approche par recurrence, qui rend la generalisation a des valeurs de h et b superieures difficile, voire impossible. Nous montrons ainsi la puissance des series generatrices pour la resolution de ce type de problemes.