Présentation du cours : (M075) Algorithmes pour la BioInformatique
Table des matières
- 1 Les cours : M075a
- 2 Les cours : M075b
- 3 Le devoir : les outils pour comparer de très grandes séquences d'ADN
Voici le programme qui était prévu (mais pas exactement ce qui sera fait!) :
- Algorithmique des chaînes de caractère, arbres suffixe, automate des suffixes. Recherche de motifs - mots communs (approchés), Plus longue sous-séquence commune.
- Algorithmique du séquençage - graphe d'intervalle, graphe de De Bruijn, séquençage par hybridation.
- Distance entre séquences - distance d'édition, comparaison d'ordres, distance évolutives.
- Graphes d'interaction et de régulation.
- Complexité des algorithmes de la Bio-Info : Complexité en temps et en mémoire des algorithmes ; ces principes seront illustrés sur des exemples : alignement de séquences, alignements multiples, analyses des données de puces à ADN.
- Algorithmes avancés : chaque année un algorithme sera analysé en profondeur : par exemple réarrangement du génome.
Ce séminaire sera suivi par les élèves du master Informatique Recherche IF 2ème année, ainsi que par les élèves du Master Pro BBSG 2ème année (cours optionnel). Nous avons choisit de découper cette UE en 2 demi UE de 3 crédits (6 cours). Les étudiants seront évalués sur le devoir ainsi que sur la lecture-présentation-compréhension d'un article proposé par un des enseignants du module.
En complément de ce module, les étudiants peuvent suivre le module d'Apprentissage Automatique, dont de nombreuses méthodes sont appliquées à la bio-informatique. Ce cours a lieu le mercredi matin au CMI (Chateau-Gombert).
1 Les cours : M075a
1.1 Jeudi 18 Novembre :
-
Séminaire LIF/MAGMA : 14h-15h30 -- Amphi 12 : Claudine Chaouiya (LGPD, IBDM, Marseille) --
Modélisation dynamique qualitative des réseaux de régulation génétique :
de la modélisation logique aux réseaux de Petri
Résumé : La complexité des réseaux de régulation génétique ne permet pas une compréhension intuitive des propriétés dynamiques de ces systèmes. On a donc recours à des méthodes mathématiques et informatiques spécifiques pour modéliser, analyser et simuler ces systèmes. Le formalisme logique permet une modélisation qualitative qui a déjà prouvé son utilité pour diverses applications. Par ailleurs, les réseaux de Petri (RdP) constituent un formalisme particulièrement adapté à la modélisation et l'analyse de systèmes présentant des situations de concurrence, synchronisation, parallélisme. Les RdP ont déjà été largement appliqués à la modélisation de réseaux de réactions biochimiques.
Après avoir introduit le formalisme logique, nous proposerons une ré-écriture systématique des modèles logiques de réseaux de régulation génique en RdP. Nous montrerons que les RdP obtenus nous permettent de retrouver des propriétés qualitatives importantes de nos réseaux de régulation. Nous conclurons sur les perspectives de ces travaux, portant sur l'analyse formelle de ces systèmes, mais aussi sur la modélisation de réseaux mixtes métaboliques-génétiques. - Cours 1 : 15h30-17h30 (Salle de réunion du Département d'Informatique Bat TPR1 entrée H 6ème étage - j'espère qu'elle est libre) :
Algorithmes d'alignements de séquence - Programmation dynamique. (Michel Van Caneghem)
Après avoir regardé rapidement l'algorithme classique, on regardera différentes variantes. On insistera sur la complexité en temps et en utilisation mémoire. On examinera de près un algorithme de complexité linéaire en occupation mémoire. Enfin on regardera rapidement les algorithmes qui sont derrière BLAST.
1.2 Jeudi 25 novembre :
-
Cours 2 : 14h-16h (La salle de réunion du département d'info si elle est libre) : Alignement de très grandes séquences (Michel Van Caneghem)
On a vu dans le cours précédent qu'il est impossible d'aligner de manière exacte des grandes séquences (> 100 000bp). On va donc proposer des méthodes pour résoudre ce problèmes de manière approchée. Description de MUMmer. Le but du jeu est de chercher la plus grande chaine commune à deux grandes séquences et de s'en servir comme ancre. Il existe des algoritmes linéaires en temps, qui sont basés sur les arbres suffixes (voir prochain cours). Je vous proposerais une autre méthode basé sur les tables de hash-code (si j'y arrive!!) -- sinon sur les tables suffixe, que vous devrez programmer. Présentation du devoir, qui en plus du programme précédent vous demandera de faire des expérimentations en utilisant mummer(ou le programme que vous allez réaliser) et "stretcher" de EMBOSS (This program implements the Myers and Miller algorithm for finding an optimal global alignment in an amount of computer memory that is only proportional to the size of the smaller sequence - O(N).). Pour ce devoir cela serait idéal si on pouvait contruire des binômes biologiste/informaticien.
- Séminaire 16h-17h30 Amphi IML : Ovidiu Radulescu (Université de Rennes). Information positionnelle et
réaction-diffusion dans l'organisation spatiale.
Résumé: D'habitude, les mécanismes du type information positionnelle et du type réaction-diffusion sont traités séparément en morphogénèse. Après une introduction au sujet je montre comment ces deux concepts sont intrinsiquement liés dans deux situations provenant de domaines tres différents : la formation de bandes de cisaillement en mécanique des fluides complexes et les premiers stades de la segmentation de l'embryon de Drosophila.
1.3 Jeudi 2 décembre :
- Cours 3 : 13h30 - 16h : (petite salle à l'IML à coté de l'amphi ou a lieu le séminaire Magma) Arbres suffixes (B. Mosse)
- Séminaire 16h-17h30 Amphi IML : Tristan Colombo (IML, LCB) Algorithmes pour la recherche de classes de gènes en relations
fonctionnelles par analyse de proximités et de similarités de séquences C'est un ancien élève du DEA d'Informatique. c'est un exemple de thèse que
vous pouvez faire
Notre étude porte sur les transporteurs ABC dans les génomes bactériens complets. L'analyse bioinformatique du répertoire de ces systèmes comprend l'identification des partenaires, l'assemblage, la reconstruction des systèmes incomplets, la classification en sous-familles, et l'identification du substrat transporté. Cette thèse propose des outils permettant l'étude de ces problèmes par l'utilisation de méthodes informatiques. Les hypothèses biologiques employées sont que : (i) des gènes voisins sur le chromosome peuvent être impliqués dans un même processus métabolique s'ils ont été conservés au cours de l'évolution, et (ii) des gènes présentant des similarités de séquence peuvent permettre la synthèse de protéines de même fonction.
Trois études ont été menées sur le répertoire des transporteurs ABC :
* L'exploration du voisinage chromosomique.
D'après l'hypothèse selon laquelle plus les gènes conservés dans le voisinage d'un transporteur sont proches, plus leur lien fonctionnel avec le transporteur est fort, on essaye d'identifier le substrat transporté ou des associations de gènes. Ce problème est traité par une méthode de résolution issue des problèmes de satisfaction de contraintes.
* La classification.
Les transporteurs ABC sont classés par grandes catégories en fonction des molécules qu'ils transportent (sucres, ...). Pour chaque domaine, en représentant les relations d'homologie par un graphe, la recherche des zones de forte densité permet de déterminer des sous-classes de substrat.
* La reconstitution des systèmes incomplets.
Les transporteurs ABC sont assemblés en utilisant la proximité chromosomique des gènes codant pour les domaines et la compatibilité des sous-familles de domaines. Lorsque la proximité n'est pas respectée, on utilise une stratégie développée à partir d'une méthode d'analyse de graphes pour assembler les domaines et prédire des systèmes actifs.
Ces méthodes, en complément de l'identification des partenaires et de l'assemblage, permettent une étude fonctionnelle des transporteurs ABC. Elles pourraient être appliquées à d'autres systèmes biologiques.
1.4 Jeudi 9 décembre :
- Cours 4 : 13h30 - 16h : (petite salle à l'IML à coté de l'amphi ou a lieu le séminaire Magma) suite (B. Mosse)
- Séminaire 16h-17h30 Amphi IML : David Martin (LGPD, Marseille).
1.5 ATTENTION : Vendredi 17 décembre :
-
Cours 5 : 14h-17h (Salle 122 IML) Algorithmique du séquençage (A. Guénoche)
Algorithmique du séquençage ; fragments, contigs et assemblage ; recherche d'un graphe d'intervalles
Séquençage par hybridation ; graphe de De Bruijn, chemin eulérien et chaîne couvrante.
1.6 Jeudi 6 janvier :
- Cours 6 : (Salle 122 IML) Conception des puces à oligos et plus courte sur-séquence commune Puces CGH et évolution des tumeurs cancéreuses (A. Guénoche)
2 Les cours : M075b
- Jeudi 13 janvier : Méthodes combinatoires en classification (B. Fichet)
- Jeudi 20 janvier : suite (B. Fichet)
- Jeudi 27 janvier : Reconstruction phylogénétique (A. Guénoche)
- Jeudi 3 février : suite (A. Guénoche)
- Jeudi 10 février : Réseaux de régulation et interaction (D. Thieffry)
Le cours commencera par une présentation générale de la problématique de la modélisation des réseaux de régulation biologique et des motivations biologiques sous-jacentes. Les principales approches formelles utilisées pour la modélisation dynamique des réseaux génétiques seront ensuite brièvement introduites. Celles-ci seront ensuite illustrées à travers un petit nombre d'applications concrètes publiées au cours des dernières années: -la modélisation du réseau génétique contrôlant le choix enter lyse et lysogénie lorsque le phage lambda infecte la bactérie E. coli; - la modélisation du processus de segmentation au début du développement de la drosophile; - la modélisation du réseau génétique contrôlant le cycle cellulaire chez les eucaryotes.
- Jeudi 17 février : suite (D. Thieffry)
3 Le devoir : les outils pour comparer de très grandes séquences d'ADN
Il ne s'agit pas dans ce devoir de refaire ce qui se trouve dans un logiciel comme MUMmer, mais seulement une partie.3.1 Recherche des plus grandes sous chaines communes à 2 séquences
On va utiliser une méthode basée sur le hashcode comme expliqué en cours. Quand on prend une chaine d'ADN tirée au hasard (probabilité d'apparation de chaque base = 1/4) on trouve que la longueur moyenne de la plus grande sous-chaine qui apparait 2 fois dans la chaine est de l'ordre de log(n) si n est la longueur de la chaine initiale. (je ne sais pas bien comment le prouver). On va donc découper les deux chaines à comparer en une suite de chaines de longueur 2log(n). Et construire la table de hashcode correspondante (on stocke les doublets <chaine, position dans la séquence>). En parcourant cette table dans un certain ordre, il est facile de construire les plus grandes sous-chaines communes. Remarque : pour faire un essai j'ai utilisé les fonctions de base de Java, mais il est clair que dans une implémentation raisonnable il faut : utiliser le fait que quand on calcule le hash-code d'une sous-chaine, pour calculer le hash-code de la sous-chaine suivante, il ne faut pas tout recalculer. De même nous n'avons pas besoin de stocker la sous-chaine dans une table, il suffit d'utiliser des pointeurs vers les séquences. Evaluer la complexité de cette méthode : c'est beaucoup plus simple à programmer que les arbres suffixes, mais est-ce que la complexité est en O(n) ou en O(nlog(n)) ? En fait le comportement est relativement différent entre une chaine aléatoire et une vrai séquence biologique. Comment est rempli la table de hash-code (nombre de conflits)?3.2 Validité de l'alignement estimé
Sur quelques exemples réels, il faudrait comparer les deux techniques suivantes :- On calcule le score de l'alignement global des deus séquences, ce qui se fait facilement en espace linéaire, mais en temps quadratique. Ce qui fait que l'on doit se limiter a des séquences de l'ordre de 200 000 à 300 00 bp.
- soit on découpe les séquences en partant de 2 ou 3 sous chaine communes comme ancre et on calcule le score de l'alignement global des séquences entre deux ancres
Dans cette seconde partie je ne m'intéresse pas du tout à la signification biologique de ces alignements.
3.3 L'alignement de 2 chromosomes
Bien sûr vous n'avez pas le temps de traiter cette partie, mais essayez de réfléchir sur le fait de combiner cette méthode avec la méthode issue de "sorting by reversal". Dans ce cas on ne prend pas des gènes, mais plutôt des sous-chaines communes. Donnez moi quelques idées que vous inspire le mélange de ces deux méthodes. Si il y a des étudiants intéressés par ces problèmes je pourrais poser un sujet de DEA sur ce problème (il faudrait que je trouve des biologistes intéressés).3.4 Les logiciels existants
Beaucoup de logiciel sont apparus de puis quelques années pour faire ce genre de travail :- BLASTZ - On trouve les sources et le binaire un peu partout. Voici un article qui décrit son utilisation Human/Mouse Alignments with BLASTZ
- MUMmer. Ce prgramme est très bien décrit et il est accompagné d'articles. Je vous conseille la lecture du premier et du dernier. La version 3.0 date de 2004.
- AVID. Un article qui décrit la méthode : AVID: A Global Alignment Program
- GAME: Genome Alignment by Match Extension - Je n'ai trouvé que des transparents et un petit article qui décrit la méthode. (date inconnue)
- PatternHunter 2.0 -- Ce n'est pas un logiciel gratuit et je ne sais pas ce qu'il fait exactement, mais il travaille sur des séquences de plusieurs millions de bp.