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.
- 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:
- 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 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
etComputation 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 DisplayFasta
en haut, et puis presserSend
), sauvergardez le CDS dans un fichierhcs.fnaen 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 dessnapshots
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'accessionNT_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 logiciellistOccurrences. 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 dehcs.fnaà l'aide du logicielneedleen 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 delistOccurrences) 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