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. Origami
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
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:
    1. 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.
    2. 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.
    3. L'alignment peut être visualisé par prettyplot en couleur: choisissez MSF Format pour le format avec needle, copiez ou sauvegardez l'alignement trouvé.
  • Exercice pour l'alignement local de deux séquences:
    1. 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.
    2. 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.)
    3. 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 le homeobox présent dans tous les deux gènes (vérifiez sur le NiceProt view de Swiss-Prot, sous Features). Est-ce que les mêmes régions sont trouvées avec d'autres paramètres de score?
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