Matériel
Notes de cours
- 1. Introduction >PDF [dernière modification: 11 janvier] 2 heures
- Sujets
- plan de cours
- macromolécules de la vie : protéines et acides nucléiques
- gènes et le code génétique
- premier aperçu des sujets de bioinformatique
- Références
- Jones & Pevzner Sections 3.1-3.7
- Cours de bio-informatique de l'Infobiogen. >HTML.
- Hunter, L. Molecular Biology for Computer Scientists, in L. Hunter, Artificial Intelligence and Molecular Biology, AAAI Press. >PDF.
- Structure de la molécule d'ADN - notes de cours de Gilles Bourbonnais de l'Université de Laval. >HTML.
- Le code génétique - introduction pour lycéens par Gilles Furelaud de l'Université Marie-Curie >HTML.
- Notes de cours sur protéines par Alexandra Debloise (editée par Marie-Paul Bassez) de l'Université Robert Schuman (Strasbourg) >HTML.
- Origami-ADN: noir/blanc ou couleur, et instructions.
- 2. Alignement de deux séquences >PDF [dernière modification: 7 février] 12 heures
- Sujets
- programmation dynamique : calcul de la distance d'édition
- alignment de deux séquences
- pondération de substitutions
- pénalisation de trous
- banques de séquences, formats de fichiers (GenBank, Fasta)
- alignement rapide : techniques de hachage
- alignment global de séquences longues
- Notes de cours
- alignement (pages 0-30)
- alignement en espace linéaire (pp. 31-34)
- NCBI, Genbank et Fasta (pp. 35-46)
- hachage (pp. 47-55)
- extension de hits (pp. 56-67)
- Références
- Jones & Pevzner sections 6.1-6.9, 7.2
- Ewens & Grant sections 6.4-6.5
- Chiaromonte, F., V. B. Yap, & W. Miller. Scoring pairwise genomic sequence alignments. Pacific Symposium on Biocomputing, 7: 115-126 (2002). [scores pour subsitutions] >PDF
- Hirschberg, D. S. A linear space algorithm for computing maximal common subsequences. Communications of the ACM, 18: 341 (1975). >HTML
- Jones & Pevzner sections 9.6-9.8
- Ewens & Grant chapitre 9
- Principles de recherche de similarités >HTML
- GenBank - résumé >HTML
- Ma, B., J. Tromp & M. Li. PatternHunter: faster and more sensitive homology search. Bioinformatics, 18: 440-445 (2002). [implantation du tableau de k-mers] >PDF
- Altschul, S. F. & al. Gapped BLAST and PSI-BLAST: a new generation of protein database search programs. Nucleic Acids Research, 25: 3389-3402 (1997). [X-drop et HSPs] >HTML
- Exercices pratiques
-
Exercice pour l'alignement global de deux séquences:
- Les deux séquences
sont les suivantes.
>souris MSALLILALVGAAVAFPVDDDDKIVGGYTCRESSVPYQVSLNAGYHFCGGSLINDQWVVSAAHCYKYRIQ VRLGEHNINVLEGNEQFVDSAKIIRHPNYNSWTLDNDIMLIKLASPVTLNARVASVPLPSSCAPAGTQCL ISGWGNTLSNGVNNPDLLQCVDAPVLPQADCEASYPGDITNNMICVGFLEGGKDSCQGDSGGPVVCNGEL QGIVSWGYGCAQPDAPGVYTKVCNYVDWIQNTIADN
>grenouille MKFLVILVLLGAAVAFEDDDKIVGGFTCAKNAVPYQVSLNAGYHFCGGSLINSQWVVSAAHCYKSRIQVR LGEHNIALNEGTEQFIDSQKVIKHPNYNSRNLDNDIMLIKLSTTARLSANIQSVPLPSACASAGTNCLIS GWGNTLSSGTNYPDLLQCLNAPILTDSQCSNSYPGEITKNMFCAGFLAGGKDSCQGDSGGPVVCNGQLQG VVSWGYGCAQRNYPGVYTKVCNFVTWIQSTISSN
Il s'agit de séquences P07146 et P70059. - Alignez les deux séquences: utilisez
l'interface
EMBOSS needle. Copiez les deux
séquences (
enter the sequence data manually here
) ci-dessus et pressez Run (vérifiez qu'il n'y a pas de lignes vides avant >souris. et >grenouille). Les options de défaut sont OK. -
L'alignment peut être visualisé par
prettyplot
en couleur: choisissez
MSF Format
pour le format avec needle, copiez ou sauvegardez l'alignement trouvé.
- Les deux séquences
sont les suivantes.
- Exercice pour l'alignement local de deux séquences:
- On va aligner la séquence protéique
du gène humain HOXA5 et
celle
du gène HOXD3 du poulet. Suivez le lien en bas de la page pour
le
FASTA format
. - Notez que les longueurs et compositions des deux séquences sont assez différentes. (Si vous voulez vous convaincre, essayez de les aligner avec needle et afficher l'alignement global avec prettyplot comme dans l'exercice précédent.)
- Performez un alignement local avec
water,
une implémentation de l'algorithme Smith-Waterman. Utilisez un
gros coût pour des espaces/trous (p.e.
gap opening penalty
=23,gap extension penalty
=0.5, matrice de défaut). L'alignement devrait trouver lehomeobox
présent dans tous les deux gènes (vérifiez sur leNiceProt view
de Swiss-Prot, sousFeatures
). Est-ce que les mêmes régions sont trouvées avec d'autres paramètres de score?
- On va aligner la séquence protéique
du gène humain HOXA5 et
celle
du gène HOXD3 du poulet. Suivez le lien en bas de la page pour
le
-
Exercice pour l'alignement global de deux séquences:
- 3. Alignement de génomes >PDF [dernière modification: 7 février] 6 heures
- Sujets
- programmation dynamique éparse
- alignment global de séquences longues
- synténies
- annotation
- Références
- Brudno, M., C. B. Do, G. M. Cooper, M. F. Kim, E. Davydov, NISC Comparative Sequencing Program, E. D. Green, A. Sidow & S. Batzoglou. LAGAN and Multi-LAGAN: Efficient tools for large-scale multiple alignment of genomic DNA. Genome Research, 13: 721-731 (2003). >HTML.
- Schwartz, S., Z. Zhang, K. A. Frazer, A. Smit, C. Riemer, J. Bouck, R. Gibbs, R. Hardison & W. Miller. PipMaker: A Web server for aligning two genomic DNA sequences. Genome Research, 10: 577-586 (2000). >HTML.
- 4. Alignement multiple, profiles et modèles de Markov >PDF [dernière modification: 23 février] 6 heures
- Sujets
- alignement multiple : approche progressiste
- alignement à un profile, position-specific scoring matrices
- segmentation
- modèle de Markov caché
- Références
- Ewens & Grant chapitre 11
- Jones & Pevzner chapitre 11
- Bréhélin, L. & O. Gascuel. Modèles de Markov cachés et apprentissage de séquences. Le temps, l'espace et l'évolutif en sciences du traitement de l'information, Éditions Cépaduès, H. Prade, R. Jeansoulin & C. Garbay éditeurs, p. 407-421 (2000). >PDF.
- Eddy, S. R. Profile hidden Markov models. Bioinformatics, 14: 755-763 (1998). >PDF.
- 5. Gènes >PDF [dernière modification: 8 mars]
- Sujets
- notions de homologie
- prédiction de gènes ab initio
- méthode comparative de prédiction de gènes
- phylogenetic shadowing
- recherche de motifs
- phylogenetic footprinting
- Références
- Jones & Pevzner sections 4.5-4.9, 6.11-6.13, 12.2
- 6. Biotechnologie >PDF [dernière modification: 24 mars]
- Sujets
- hybridation/dénaturation
- cisaillement
- enzymes de restriction
- clonage
- PCR
- séquençage Sanger
- aperçu de séquençage shotgun
- 7. Calcul moléculaire >PDF [dernière modification: 24 mars]
- Sujets
- encodage de text et de base de données par ADN
- encodage de graphes et de chemins
- implantation d'automates finis
- Références
- Clelland C. T., V. Risca & C. Bancroft. Hiding messages in DNA microdots. Nature, 399: 533-534 (1999). >HTML
- Benenson, Y., R. Adar, T. Paz-Elizur, Zvi Livneh & E. Shapiro. DNA molecule provides a computing machine with both data and fuel. Proceedings of the National Academy of Sciences of the USA, 100: 2191-2196 (2003). >HTML
- Benenson, Y., B. Gil, U. Ben-Dor, R. Adar & E. Shapiro.
An autonomous molecular computer for logical control of gene expression.
Nature, 429: 423-429 (2004).
>HTML.
Le film sur le
médicament intelligent
se trouve sur le site Web de Ehud Shapiro > Quicktime
Devoirs
Pour remettre vos travaux : envoyez-moi un courriel (l'addresse formée en permutant les mots 'ca', 'csuros', 'iro', 'umontreal') avec le fichier comme attachement.
- Devoir 1 à remettre le 10 février.
- Énoncé >PDF.
- Devoir 2 à remettre le 15 mars.
- Énoncé >PDF. Le fichier NC_005213-tRNA-SE.txt.
- Devoir 3 à remettre le 12 ou 18 avril.
Présentations des étudiants
- Audrey Gélinas :
Problème de la
petite parcimonie
.- Jones & Pevzner 10.10
- Mirkin, B. G., T. I. Fenner, M. Y. Galperin & E. V. Koonin. Algorithms for computing parsimonious evolutionary scenarios for genome evolution, the last universal common ancestor and dominance of horizontal gene transfer in the evolution of prokaryotes. BMC Evolutionary Biology, 3:2 (2003). >HTML.
- Jeremie Lasalle-Ratelle :
Recherche de motifs par projections aléatoires.
- Buhler, J. & M. Tompa. Finding motifs using random projections. Journal of Computational Biology, 9(2): 225-242 (2002).
- Jones & Pevzner 12.3
- Roman Noizet :
Solution du problème du voyageur commerçant par la méthode d'Adleman.
- Adleman, L. M. Computing with DNA. Scientific American, 279(2): 54-61, août 1998. >PDF (13 Meg)
- Adleman, L. M. Molecular computation of solutions to combinatorial problems. Science, 266: 1021-1023 (1994). > PDF (preprint au site du Labo Adleman).
- Benjamin Provencher :
Alignement de génomes à l'aide d'arbres de suffixe.
- Jones & Pevzner 9.5
- Delcher, A. L., S. Kasif, R. D. Fleischmann, J. Peterson, O. White & S. L. Salzberg. Alignment of whole genomes. Nucleic Acids Research, 27: 2369-2376 (1999). >HTML.
- Guy Raymond Tremblay : Prédiction de la structure secondaire de l'ARN