UE Applications de la science des données et de l’intelligence artificielle, ENSIMAG 2A

Projet: Algorithmes de programmation dynamique pour l'alignement de séquences



Contexte

L'UE Applications de la science des données et de l’intelligence artificielle (ASDIA, 2A ENSIMAG) comporte 3 projets, cette page concerne le projet intitulé "Algorithmes de programmation dynamique pour l'alignement de séquences" dont je suis responsable.
Pour les autres projets, voir la page de l'UE (accès intranet ENSIMAG nécessaire).

Objectifs

Comparer deux séquences biologiques (ADN, ARN, protéines) est une tâche essentielle en bioinformatique afin d'identifier les régions homologues ou similaires, et de quantifier leur similarité. Dans ce projet nous étudierons et implémenterons en C deux algorithmes classiques d'alignement de séquences: l'algorithme de Smith-Waterman puis une extension de celui-ci, et nous les appliquerons sur quelques exemples typiques.

Liens utiles

03/03/2021: Une archive avec l'énoncé, les slides de la première séance, le code et les exemples.
L'archive contient également les exécutables aliDnaLinear_ntm, aliDnaAffine_ntm, aliDnaAffineLongGaps_ntm et aliProtAffine_ntm qui vous permettent de comparer/valider vos implémentations, et de traiter les questions de l'énoncé même si vous ne parvenez pas à tout faire.

10/03/2021: Slides complémentaires sur le modèle affine de coût des insertions-deletions, et l'algorithme de Altschul-Erickson qui permet de traiter ce cas correctement.


Contact

Nicolas Thierry-Mieg, email: Nicolas.Thierry-Mieg<at>univ-grenoble-alpes<dot>fr