Module : Algorithmique combinatoire et optimisation. CODE UMINS306
Responsable
Vincent Berry
Parcours intégrant UV
parcours bioinformatique du master Informatique pour les Sciences.
Parcours possibles
autres parcours du master Informatique pour les sciences.
Pré-Requis
UMIPS101 (Algorithmique, Programmation Objet, Introduction à la complexité)
Controle connaissances
2,5
Description de l'UE :
Semestre
Code
Intitulé
Cours
TD
TP
TER
S3
UMINS306
Algorithmique combinatoire et optimisation
12
7
Detail du programme
Objectifs : Contenu :
Objectif
De nombreux problèmes de bioinformatique se modélisent sous la forme de problèmes combinatoires. L'objectif est de présenter
des formalismes et des méthodes classiques d'informatique théorique qui peuvent être utilisés pour résoudre ces problèmes
combinatoires. On étudiera aussi un certain nombre d'algorithmes spécifiques du domaine de la bioinformatique.
Plan
– Formalisme pour les problèmes combinatoires (exemple de modélisation de divers problèmes d'informatique et bioinformatique)
– Rappels sur les graphes (en tant que structure de données combinatoire) et les parcours de graphes (application à l'assemblage
de fragments d'ADN après analyse shotgun).
– Algorithmes d'énumération itérative et d'élagage (application à l'alignement multiple de séquence et aux phylogénies)
– Algorithmes de programmation dynamique (applications à l'alignement de séquences, aux phylogénies, à la prédiction de structure
d'ARN)
– Modèles de Markov cachés (application à la découverte de gènes).
– Algorithmes stochastiques (application au problème de protein threading).
