Plan du cours d'algorithmes pour la biologie (BNF 103)

Le cours suivra le plan suivant :

Définitions, notations, pseudocode

Exemple, Pseudo-code, pseudo-code->scheme, recherche dans une liste, complexité, notations asymptotiques.

Données et information

Quelques notions de base.

Graphes et arbres

Encores des notions de base...

Automates et machines de Turing

À l’attaque des vrais fondements.

Automates II : non-déterminisme

Après les automates à états finis déterministes, les automates non-déterministes, qui sont d’ailleurs équivalents.

Expressions régulières

La suite logique des automates, auxquels elles sont équivalentes.

Accélération d’un algorithme

Recherche du maximum d’un ensemble de valeurs, memoization de Fibonacci, recherche de segments maximaux O(n³), O(n²), O(n). On attaque l’algorithmique proprement dite.

Accélération de l’algorithme de Fibonacci

Un exemple.

Tris

Algorithmes de tri par insertion, recherche de maximum dans une liste, tri fusion, tri rapide, tri linéaire.

Structures de données élémentaires

Les pile, les files, le tas et tris par tas, les arbres, arbres binaires de recherche, tables de hashage.

Recherche de mots dans un texte

Force brute, Knuth-Morris-Pratt (KMP), Karp Rabin.

Le précédent en style récursif

Instrumentation d’un programme pour l’observer : KMP

Une variation autour du précédent.

Recherche de mots dans un texte (suite)

Structures de données Les arbres de mot-clés (keyword trees), les arbres de suffixes (suffix trees).

Recherche d’un motif dans un texte

Prosite, les expressions régulières, grep, les automates à état fini, expression régulières -> automates à état finis indéterministes, déterminisation d’un automate à état fini, minimisation d’automates à état finis.

Algorithmes sur les graphes

Le métabolisme, représentation de graphe, recherche de plus court chemin, recherche d’arbre couvrant minimal.

Algorithme de Needleman et Wunsch

Alignement de séquences.

Programmation dynamique

Recherche de séquences hydrophobes, comparaison de séquence par l’algorithme de Needleman et Wunsch, par l’algorithme de Smith et Waterman, optimisation de Gotoh, multiplication de matrices : minimisation des calculs.

Recherche dans des banques de données

Blast, Fasta, les matrices PAM.

Chaines de Markov

Prédiction de modèles de gènes, prédiction de structure, représentation de motifs fonctionnels.

Des problèmes difficiles : NP-complétude

Problème de la clique, Sat, voyageur de commerce.

Solution presque optimales

Simulated anealing, algorithmes génétiques...