Matériel

Lectures

1. Introduction >PDF [dernière modification: 6 septembre] 1 heure
Sujets
  • Plan de cours
  • L'ADN
  • Contenu du cours
Lecture obligatoire
  • Hunter, L. Molecular Biology for Computer Scientists, in L. Hunter, Artificial Intelligence and Molecular Biology, AAAI Press. >PDF.
Références additionnelles
  • Structure de la molécule d'ADN - notes de cours de Gilles Bourbonnais de l'Université de Laval. >HTML.
2. Biotechnologie >PDF [dernière modification: 8 septembre] 2 heures
Sujets
  • hybridation/dénaturation
  • cisaillement
  • enzymes de restriction
  • clonage
  • PCR
  • séquençage Sanger
  • pyroséquençage
  • aperçu de séquençage shotgun
Références
  • Green, E. D. 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.
  • Ewing, B. & P. Green. Base-calling of automated sequencer traces using Phred. II. Error probabilities. Genome Research, 8: 186-194. (1998). >HTML
  • Ronaghi, M., M. Uhlén, & P. Nyrén. A sequencing method based on real-time pyrophosphate. Science, 281: 363-365 (1998). [pyroséquençage] >HTML
3. Calcul moléculaire >PDF [dernière modification: 15 septembre] 5 heures
Sujets
  • encodage de text et de base de données par ADN
  • encodage de graphes et de chemins
  • implantation de portes logiques par deoxyribozymes
  • implantation d'automates finis
Lectures obligatoires
  • 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
  • Adleman, L. M. Computing with DNA. Scientific American, 279(2): 54-61, août 1998. >PDF (13 Meg)
Références
  • Clelland C. T., V. Risca & C. Bancroft. Hiding messages in DNA microdots. Nature, 399: 533-534 (1999). >HTML
  • Bancroft C., T. Bowler, B. Bowler & C. T. Clelland. Long-term storage of information in DNA. Science, 293: 1763-1765 (2001). >HTML
  • 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).
  • Stojanovic, M. N., T. E. Mitchell & D. Stefanovic. Deoxyribozyme-based logic gates. Journal of the American Chemical Society, 124: 3555-3561 (2002). >HTML
  • Stojanovic, M. N. & D. Stefanovic. A deoxyribozyme-based molecular automaton. Nature Biotechnology, 21: 1069-1074 (2003). >HTML
  • Bennett, Charles H. The thermodynamics of computation: a review. International Journal of Theoretical Physics, 21: 905-940 (1982). >PDF.
  • Adar, R., Y. Benenson, G. Linsiz, A. Rosner, N. Tishby & E. Shapiro. Stochastic computing with biomolecular automata. Proceedings of the National Academy of Sciences of the USA, 101: 9960-9965 (2004). [extension de l'idée de Benenson et al. (2003): comment imposer des probabilités de transition en variant la concentration des molécules] >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
  • Condon, A. Automata make antisense. Nature (News and views), 429: 351-352 (2004). [donne une bonne introduction à l'article de Benenson et al. (2004), et explique comment l'automate reconnait l'expression élevée ou baissée d'un gène] >HTML
4. Séquençage shotgun - aperçu >PDF [dernière modification: 26 septembre] 5 heures
Sujets
  • séquençage hiérarchique
  • statistiques de Lander-Waterman
  • algorithmique de l'assemblage: construction de contigs
Lecture obligatoire
  • Green, E. D. Strategies for the systematic sequencing of complex genomes. Nature Reviews Genetics, 2: 573-583 (2001). >HTML.
Références
  • Sutton G. R., O. White, M. D. Adams & A. R. Kerlavage. TIGR assembler: a new tool for assembling large shotgun sequencing projects. Genome Science and Technology, 1: 9 (1995).
  • 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).
  • Lander, E. S. & M. S. Waterman. Genomic mapping by fingerprinting random clones: a mathematical analysis. Genomics, 2: 231-239 (1988). [le pionnier des modèles statistiques en séquençage] >PDF sur le site de Michael Waterman.
  • Myers, E. W. & al. A whole-genome assembly of Drosophila. Science, 287: 2196-2204 (2000). [test pour compression de contigs] >HTML
5. Alignement et comparaison >PDF [dernière modification: 12 octobre] 13 heures
Sujets
  • approche classique: alignement global et local par programmation dynamique
  • alignement en espace linéaire
  • recherche rapide: hit-and-extend
  • alignement de génomes et PD éparse
Lectures obligatoires
  • Batzoglou, S. The many faces of sequence alignment. Briefings in Bioinformatics, 6: 6-22 (2005). >PDF.
  • Frazer, K. A., L. Elnitski, D. M. Church, I. Dubchak & R. C. Hardison. Cross-species sequence comparisons: A review of methods and available resources. Genome Research, 13: 1-12 (2003). >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.
Références
  • Gusfield Sections 11.1-11.7 : alignement de deux séquences par PD.
  • 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
  • NIH/NCBI: Principles de recherche de similarités >HTML
  • Brown, D. G., M. Li & B. Ma. Homology search methods. Chapter 10 In Wong, L. (ed.) The Practical Bioinformatician, World Scientific, Singapore (2004). >PDF [impression interdite].
  • Ma, B., J. Tromp & M. Li. PatternHunter: faster and more sensitive homology search. Bioinformatics, 18: 440-445 (2002). [implantation du tableau de k-mers, introduction des graines espacées] >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
  • Huang, X., et A. Madan. CAP3: a DNA sequence assembly program. Genome Research, 9: 868-877 (1999). >HTML
  • Brown, D. G., M. Li & B. Ma. A tutorial of recent developments in the seeding of local alignment. Journal of Bioinformatics and Computational Biology, 2: 819-849 (2004). [sensitivité des graines espacées] >HTML.
  • Eppstein, D., Z. Galil, R. Giancarlo & G. F. Italiano. Sparse dynamic programming I: linear cost functions. Journal of the ACM, 39: 519-545 (1992). >HTML.
  • Gusfield, Section 13.3 [chaînage d'alignements locaux]
  • Slater, G. S. & E. Birney. Automated generation of heuristics for biological sequence comparison. BMC Bioinformatics, 6:31 (2005). >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.
  • 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.
  • 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.
  • Schwartz, S., W. J. Kent, A. Smit, Z. Zhang, R. Baertsch, R. C. Hardison, D. Haussler & W. Miller. Human-mouse alignments with BLASTZ. Genome Research, 13:103-107 (2003). >HTML.
  • Kalafus, K. J., A. R. Jackson & A. Milosavljevic. Pash: efficient genome-scale sequence anchoring by positional hashing. Genome Research, 14:672-678 (2004). >HTML.
  • Tufarelli, C., R. C. Hardison, W. Miller, J. Hughes, K. Clark, N. Ventress, A. M. Frischauf & D. R. Higgs. Comparative analysis of the alpha-like globin clusters in mouse, rat, and human chromosomes indicates a mechanism underlying breaks in conserved synteny. Genome Research, 14:623-630 (2004). >HTML.
  • 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.
6. Modèles probabilistes >PDF [dernière modification: 4 novembre] 2 heures
Sujets
  • segmentation de l'ADN
  • modèle de Markov caché
  • phylogenetic shadowing
Références
  • Csűrös, M. Maximum-scoring segment sets. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 1:139-150 (2005). >PDF.
  • Knudsen, B. & M. M. Miyamoto. Sequence alignments and pair hidden Markov models using evolutionary history. Journal of Molecular Biology, 333: 453-460 (2003). >HTML.
  • Boffelli, D., J. McAuliffe, D. Ovcharenko, K. D. Lewis, I. Ovcharenko, L. Pachter & E. M. Rubin. Phylogenetic shadowing of primate sequences to find functional regions of the human genome. Science, 299:1391-1394 (2003). >HTML.
Grève des professeurs 3, 10, et 17 novembre.
7. Gènes dans le génome >PDF [dernière modification: 18 novembre] 4 heures
Sujets
  • notions de homologie
  • prédiction de gènes
  • familles de gènes
  • évolution de répertoire de gènes: duplication, transfert latéral
  • profiles phylétiques
Lecture obligatoire
  • Tatusov, R. L. & al. (17 auteurs) The COG database: an updated version includes eukaryotes. BMC Bioinformatics, 4:41 (2003). >HTML.
  • Rogozin, I. B., A. V. Sverdlov, V. N. Babenko & E. V. Koonin. Analysis of evolution of exon-intron structure of eukaryotic genes. Briefings in Bioinformatics, 6:118-134 (2005).
Références
  • Lukashin, A. V. & M. Borodovsky. Genemark.hmm: new solutions for gene finding. Nucleic Acids Research, 26:1107-1115 (1998). >HTML.
  • Baldi, P., S. Brunak, Y. Chauvin & A. Krogh. Naturally occurring nucleosome positioning signals in human exons and introns. Journal of Molecular Biology, 263:503-510 (1996). >HTML.
  • Burge, C. & S. Karlin. Prediction of complete gene structures in human genomic DNA. Journal of Molecular Biology, 268: 78-94 (1997). [GENSCAN] >HTML.
  • Miller, W., K. D. Makova, A. Nekrutenko & R. C. Hardison. Comparative genomics. Annual Review of Genomics and Human Genetics, 5:15-56 (2004). >HTML.
  • Parra, G, P. Agarwal, J. F. Abril, T. Wiehe, J. W. Fickett & R. Guigó. Comparative gene prediction in human and mouse. Genome Research, 13: 108-117 (2003). [SGP-2] >HTML.
  • Fitch, W. M. Homology: a personal view on some of the problems. Trends in Genetics, 16:227-231 (2000). >HTML.
  • Tatusov, R. L., E. V. Koonin & D. J. Lipman. A genomic perspective on protein families. Science, 278:631-637 (1997). [COG v1.0] >HTML.
  • Remm, M., C. E. V. Storm & E. L. L. Sonnhammer. Automatic clustering of orthologs and in-paralogs from pairwise species comparisons. Journal of Molecular Biology, 314:1041-1052 (2001). [INPARANOID] >HTML.
  • Kellis, M., N. Patterson, B. Birren, B. Berger & E. S. Lander. Methods in comparative genomics: genome correspondence, gene identification and regulatory motif discovery. Journal of Computational Biology, 11:319-355 (2004). [BUS] >HTML.
  • Pellegrini, M., E. M. Marcotte, M. J. Thompson, D. Eisenberg & T. O. Yates. Assigning protein functions by comparative genome analysis: Protein phylogenetic profiles. Proceedings of the National Academy of Sciences of the USA, 96:4285-4288 (1999). >HTML.
  • 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). [profiles phylogénétiques] >HTML.
  • Koonin, E. V. Comparative genomics, minimal gene-sets, and the last universal common ancestor. Nature Reviews Microbiology, 1:127-136 (2003). >HTML.
  • Kunin, V., L. Goldovsky, N. Darzentas & C. A. Ouzounis. The net of life: Reconstructing the microbial phylogenetic network. Genome Research, 15:954-959 (2005). [fréquence de transfert latéral] >HTML.
  • Notebaart R. A., M. A. Huynen, B. Teusink, R. J. Siezen & B. Snel. Correlation between sequence conservation and the genomic context after gene duplication. Nucleic Acids Research, 33:6164-6171 (2005). [le BeT n'est pas toujours l'orthologue] >HTML.
  • Jordan, I. K., K. S. Makarova, J. L. Spouge, Y. I. Wolf & E. V. Koonin. Lineage-specific gene expansions in bacterial and archaeal genomes. Genome Research, 11:555-565 (2001). [lineage specific expansion] >HTML.
8. Évolution moléculaire >PDF [dernière modification: 1 décembre] 4 heures
Sujets
  • parcimonie
  • évolution de séquences: modèles de Markov
  • vraisemblance
Références
  • Felsenstein, J. Statistical inference of phylogenies. Journal of the Royal Statistical Society A, 146:246-272 (1983). [article classique sur PD pour le calcul des vraisemblances]
  • Rogozin, I. B., Y. I. Wolf, A. V. Sorokin, B. G. Mirkin & E. V. Koonin. Remarkable interkingdom conservation of intron positions and massive, lineage-specific intron loss and gain in eukaryotic evolution. Current Biology, 13:1512-1517 (2003). [parcimonie Dollo pour évolution d'introns]

Présentations des étudiants

Andreas Grimm : DNA self-assembly
  • Winfree, E., F. Liu, L. A. Wenzler & N. C. Seeman. Design and self-assembly of two-dimensional DNA crystals. Nature, 394: 539-544 (1998). >HTML
  • Winfree, E. DNA Computing by Self-Assembly. The Bridge, 33(4): 31-38 (2003). >PDF (preprint au site d'Erik Winfree).
  • Rothemund, P. W. K., N. Papadakis & E. Winfree. Algorithmic self-assembly of DNA Sierpinski triangles. PLoS Biology, 2(12): e424 (2004). >HTML.
Karine St-Onge : Gene clusters in prokaryotes
Marc Parisien : Protein beta-sheets
  • Parisien, M. & F. Major. A new catalog of protein beta-sheets. Proteins: Structure, Function and bioinformatics, 61:545-558 (2005). >HTML.
Olga Feiguina : Evolving complex networks
  • Newman, M. E. J. The structure and function of complex networks. SIAM Review, 45:167-256 (2003). >HTML.
  • Barabási, A.-L. & Z. N. Oltvai. Network biology: understanding the cell's functional organization. Nature Reviews Genetics, 5:101-114 (2004). >HTML.
  • Barabási, A.-L. & R. Albert. Emergence of scaling in random networks. Science, 286:509-512 (1999). >HTML.
Amine Halawani : Arbres de suffixe
  • 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). [MUMmer 1] >HTML.
  • Delcher, A. L., A. Phillippy, J. Carlton & S. L. Salzberg. Fast algorithms for large-scale genome alignment and comparison. Nucleic Acids Research, 30: 2478-2483 (2002). [MUMmer 2] >HTML.
  • Kurtz, S., A. Phillippy, A. L. Delcher, M. Smoot, M. Shumway, C. Antonescu & S. L. Salzberg. Versatile and open software for comparing large genomes. Genome Biology, 5:R12 (2004). [MUMmer 3] >HTML.
  • Kurtz, S., J. V. Choudhuri, E. Ohlebusch, C. Schleiermacher, J. Stoye & R. Giegerich. REPuter: the manifold applications of repeat analysis on a genomic scale. Nucleic Acids Research, 29:4633-4642 (2001). >HTML.
Perrine Landreau : Séquençage d'ADN et chemins euleriens
  • Pevzner, P. A., H. Tang & M. S. Waterman. An Eulerian path approach to DNA fragment assembly. Proceedings of the National Academy of Sciences of the USA, 98: 9748-9753 (2001). >HTML.
  • Zhang, Y. & M. S. Waterman. An Eulerian path approach to local multiple alignment for DNA sequences. Proceedings of the National Academy of Sciences of the USA, 102:1285-1290 (2005). >HTML.
Paul Dallaire : Haplotypes et algorithmes
  • Gusfield, D. & S. H. Orzack. Haplotype inference. In S. Aluru, Ed. CRC Handbook on Bioinformatics, 2005. >PDF.
  • Stephens, M., N. J. Smith & P. Donnelly. A new statistical method for haplotype inference from population data. American Journal of Human Genetics, 68:978-989 (2001). >HTML.

Devoirs

Devoir 1 à remettre le 13 octobre.
Énoncé : PDF.
Devoir 2 à remettre le 1 décembre.
Énoncé : PDF.