Programmation dynamique et alignement de séquences

 

L’alignement de séquences se range dans les problèmes traitant les séquences de caractères comme du texte ou de la voix. Il a pour objectif d’associer, ou non, à chaque caractère d’une séquence, un autre caractère d’une autre séquence. Nous verrons dans cet article différents algorithmes de difficulté croissante et aborderons des applications qui se trouvent en génétique, en recherche d’information ou encore en linguistique comparative.

Au sommaire de l’article

1 Séquence

2 Alignement

3. Programmation dynamique et distance de Levenshtein

3.1 Mise en pratique de la programmation dynamique

3.2 Exemples

4 Alignement global

4.1 L’alignement et l’algorithme de Needleman-Wunsch

4.2 Exemple

5 Alignement local

6 Cas pratique en génétique : l’algorithme BLAST

6.1 Les besoins en génétique

6.2 Au cœur de BLAST

7 Applications en linguistique comparative

Conclusion

Références

Clément Besnier

 > Lire l’intégralité de cet article sur notre plateforme de lecture en ligne Connect  

Retrouvez cet article (et bien d’autres) dans GNU/Linux Magazine n°212, disponible sur la boutique et sur Connect !

Laisser un commentaire