Algorithmes Bio-informatiques
| Nature | UE |
|---|
| Crédits ECTS | 3 |
|---|---|
| Volume horaire total | 30 |
| Volume horaire CM | 12 |
| Volume horaire TD | 9 |
| Volume horaire TP | 9 |
Pré-requis
Avoir suivi l'UE « Algorithmie et programmation en Python » (M1S1) ou avoir des bases d'algorithmie et savoir programmer en python.
Objectifs
• 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
Contenu
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)
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)
Appartient à
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