老虎机游戏
Acquérir des notions d'algorithmiques sur des questions classique de la bio-informatique.
COURS MAGISTRAUX (15 H)
- Introduction de la notion de complexité (linéaire, polynomial, exponentielle, NP-difficile, NP-complet), ouverture et illustration sur le problème du tri
I – Alignement de séquences
? Brefs rappels, alignement de 2 séquences, notion de complexité
? Alignement de plus de deux séquences
? Complexité : présentation des niveaux de complexité algorithmique
II - Heuristiques d'alignements multiple
Introduction à la notion de clusterisation (contro?de / algorithmes griddy, classification hiérarchique : UPGMA)
III – Recherche de motif exact
? Algorithme na?f (brute force)
? Pré-traitement sur le motif : (KMP)
? Pré-traitement sur le texte : (introduction aux structures de données)
? Indexation de texte:table de hash, (illustration sur l'ancrage du BLAST (?))
? Arbre des suffixes : structure de TREE (algorithme de Ukkonen)
? Ouverture sur le Burrow-wheller et limites des motifs exacts en mapping
IV – Recherche / alignement de motifs non exacts (Pattern matching ?)
? Pattern matching : PSSM au HMM
? Qu'est-ce qu'un modèle de Markov, un modèle de Markov caché
? Scoring : probabilité que le modèle génère une séquence (algorithme direct)
? Alignment : trouver la séquence d'états optimale (meilleur chemin) du HMM pour caractériser une séquence : algorithme de VITERBI (programmation dynamique)
? Training : trouver la structure et apprendre les paramètres d'un HMM (proba de transition et d’émission) à partir d'un jeu de données : algorithme avant-arrière ; Baum-Welch (EM)
TRAVAUX DIRIGES (6 H)
Présentation d'articles travaillés entre les cours présentiels :
TRAVAUX PRATIQUES (9 H)
? Implémentation d’algorithmes vus en cours (KMP, MM/HMM, UPGMA)
Informations complémentaires
? Comprendre le principe et savoir utiliser des outils bio-informatiques dédiés à l’analyse de séquences
? Développer une méthode d’analyse et une argumentation scientifique
