Matériel

Notes de cours

1. Introduction >PDF [dernière modification: 5 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 Marie-Paul Bassez de l'Université de Strasbourg >HTML.
  • Origami-ADN: noir/blanc ou couleur, et instructions. Origami
2. Alignement de deux séquences >PDF [dernière modification: 26 janvier] 8 heures
Sujets
  • programmation dynamique : calcul de la distance d'édition
  • alignment de deux séquences
  • pondération de substitutions
  • pénalisation de trous
  • alignment en espace linéaire
Références
  • Jones & Pevzner sections 6.1-6.9, 7.2
  • Ewens & Grant sections 6.4-6.5
  • Chiaromonte, 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
Exercices
  • 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 rapide >PDF [dernière modification: 9 février] 8 heures
Sujets
  • banques de séquences (Genbank)
  • techniques de hachage
  • BLAST : signification
  • alignment global de séquences longues
Références
  • 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
  • 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: 25 février] 9+1 heures
Sujets
  • alignement multiple : approche progressiste
  • alignement à un profile
  • modèle de Markov caché
  • alignement statistique
  • prédiction de gènes ab initio
  • recherche de motifs
Références
  • Ewens & Grant chapitre 11
  • Jones & Pevzner chapitre 11, sections 4.5-4.9, 12.2-12.3
  • 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.
Présentation de François Gauthier : 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).
5. Analyse de génomes >PDF [dernière modification: 11 mars] 4 heures
Sujets
  • traits de génomes
  • génomique comparative: footprinting, shadowing, prédiction de gènes par comparaison
  • annotation, fureteurs de génomes
Références
  • Blanchette, M., W. J. Kent, C. Riemer, L. Elnitski, A. F. A. Smit, K. M. Roskin, R. Baertsch, K. Rosenbloom, H. Clawson, E. D. Green, D. Haussler & W. Miller. Aligning multiple genomic sequences with the threaded blockset aligner. Genome Research, 14: 708-715 (2004). >HTML.
  • Kent, W. J., R. Baertsch, A. Hinrichs, W. Miller & D. Haussler. Evolution's cauldron: Duplication, deletion, and rearrangement in the mouse and human genomes. Proceedings of National Academy of Sciences of the USA, 100: 11484-11489 (2003). >HTML.
  • Brudno, M., S. Malde, A.Poliakov, C. B. Do, O. Couronne, I. Dubchak & S. Batzoglou. Glocal alignment: Finding rearrangements during alignment. Bioinformatics, 19: i54-i62 (2003). >HTML.
6. Séquençage >PDF [dernière modification: 31 mars] 3+1 heures
Sujets
  • outils de génie génétique : hybridation/dénaturation, enzymes de restriction, clonage, PCR, séquençage Sanger
  • aperçu de séquençage shotgun
  • séquençage par hybridation
Références
  • Jones & Pevzner sections 8.3-8.9
  • E. D. Green. Strategies for the systematic sequencing of complex genomes. Nature Reviews Genetics, 2 : 573-583 (2001). >HTML : n'est pas accessible sans abonnement mais vous pouvez copier ~csuros/pub/green.pdf sur les machines de DIRO.
  • Huang, X., et A. Madan. CAP3: a DNA sequence assembly program. Genome Research, 9: 868-877 (1999). C'est l'article qui montre comment calculer tous les chevauchements d'une façon très efficace. Les sections les plus pertinentes : Fast identification of pairs of reads with an overlap et Computation and evaluation of overlaps. >HTML
  • Myers, E. W. Toward simplifying and accurately formulating fragment assembly. Journal of Computational Biology, 2: 275-290 (1995). [calcul de contigs, simplification du graphe de chevauchements] >PDF (preprint au site de Gene Myers).
  • Myers, E. W. & al. A whole-genome assembly of Drosophila. Science, 287: 2196-2204 (2000). [ossatures] >HTML
Présentation de Winnie Sheun-Ye Ng: Séquençage par hybridation.
7. Calcul moléculaire >PDF [dernière modification: 31 mars] 2+1 heures
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
  • Stojanovic, M. N. & D. Stefanovic. A deoxyribozyme-based molecular automaton. Nature Biotechnology, 21: 1069-1074 (2003). >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
Présentation de Louis-Philippe Lemieux-Perreault : Chemins hamiltoniens 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). > JSTOR (pas encore accessible de l'UdeM); PDF (preprint au site du Labo Adleman).
8. Phylogénies >PDF [dernière modification: 1 avril] 2 heures
Sujets
  • modèles d'évolution de séquences
  • parcimonie et distances
  • reconstruction d'arbres phylogénétiques
Références
  • Jones & Pevzner sections 10.5-10.11
  • Ewens & Grant sections 13.1-13.2, 14.1-14.2, 14.4, 14.6
9. Structure secondaire de l'ARN 1 heure
Sujets
  • prediction de la structure secondaire de l'ARN: Nussinov, Zucker
Présentation de Maxime Caron : Calcul de structure secondaire de l'ARN par la méthode de Nussinov.
10. Expression de gènes >PDF [dernière modification: 8 avril] 1+1 heures
Sujets
  • puces ADN : traitement de signal, dessin de puces
  • analyse de l'expression génique : groupement
Références
  • Jones & Pevzner sections 10.1-10.3
  • Principes de puces d'ADN de l'ENS.
  • M. B. Eisen, P. T. Spellman, P. O. Brown, & D. Botstein. Cluster analysis and display of genome-wide expression patterns. Proceedings of the National Academy of Sciences of the USA, 95(25) : 14863-14868 (1998). >HTML
Présentation de Xiao Zhu : Analyse de l'expression génique par groupement hiérarchique.

Devoirs et examens

Pour remettre vos travaux : vos rapports écrits en personne au cours ou fichier PDF par courriel (pas de doc ou d'autres formats non-portables). Pour votre code : sur les machines de DIRO faites remise ift3299 tpn <fichier>... où n est le numéro du TP. (Consultez man remise si nécessaire.)

Devoir 1 à remettre le 26 janvier.
Énoncé : PDF
Devoir 2 à remettre le 18 février.
Énoncé : PDF
Vous travaillerez avec la séquence du gène cytochrome c. L'ARN messager de ce gène est stocké sous le nombre d'accession NM_018947 [gi:34328939) en GenBank. Étudiez l'annotation pour trouver le segment qui correspond à la partie codante (CDS). Après avoir téléchargé la séquence en format Fasta (choisir format de Display Fasta en haut, et puis presser Send), sauvergardez le CDS dans un fichier hcs.fna en utilisant l'outil d'extraction de sous-mots du Devoir 1 (pour vérifier: la séquence est de longuer 318nt, commence avec le codon ATG et finit par le codon TAA). C'est la séquence dont les occurrences inexactes vous devez cherchez dans le génome humain. Ce gène a produit beaucoup de pseudogènes dans le génome, et ces pseudogènes nous donnent des snapshots de la séquence du gène comme elle était au moment de l'insertion du pseudogène (ça fait quelques dizaines de millions d'ans), et sont ainsi des témoins importants de l'évolution d'une séquence. Pour cet exercice, au lieu de chercher tout le génome humain, il suffit de travailler avec une partie de la séquence de chromosome 7, stockée sous le nombre d'accession NT_007933 [gi:51493052] Attention: c'est une sénce de longueur 62M. Téléchargez la séquence et essayez de trouver les pseudogènes de cytochrome c en utilisant votre logiciel listOccurrences. Après avoir trouvé les occurrences, servez-vous de l'outil du Devoir 1 pour extraire les séquences qui y correspondent et faites un alignement global entre chacune d'eux et la séquence de hcs.fna à l'aide du logiciel needle en EMBOSS. Vérifiez la présence de signes de pseudogènes: décalages de cadre (frameshifts --- trous de longueur qui n'est pas divisible par trois) et/ou des codons d'arrêt. Dans votre report, donnez les coordonnés des pseudogènes identifiés (sortie de listOccurrences) ainsi que les alignements globaux. (Idéalement, vous trouverez deux pseudogènes, avec scores d'environ 220-240.)
Examen intra 23 février.
Énoncé : PDF
Devoir 3 à remettre le 18 mars.
Énoncé : PDF