Matériel

Lectures

1. Introduction >PDF [2 heures]
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
2. Biotechnologie >PDF [2 heures]
Sujets
  • hybridation/dénaturation
  • cisaillement
  • enzymes de restriction
  • clonage
  • PCR
  • séquençage Sanger
3. Calcul moléculaire >PDF [5+1 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
  • 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
Présentation par Yasmine Yacef : DNA self-assembly >PDF ou PPT.
  • 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. Algorithmic Self-Assembly of DNA: Theoretical Motivations and 2D Assembly Experiments. In Sarma & Sarma (eds.) Proceedings of the Eleventh Conversation, Journal of Biomolecular Structure and Dynamics, No. 2, 263-270 (2000). >PDF (preprint au site d'Erik Winfree).
4. Séquençage shotgun - aperçu et statistiques >PDF [6 heures]
Sujets
  • séquençage hiérarchique et génome complet
  • statistiques de Lander-Waterman
Lecture obligatoire
  • 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.
Références
  • Waterman, M. S. Introduction to Computational Molecular Biology: Maps, Sequences, and Genomes. CRC Press 1995, 6.1.1, 7.1.5. [statistiques pour îles et océans]
  • 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 - v. note 24] >HTML
  • Li, X. & M. S. Waterman. Estimating the repeat structure and length of DNA sequences using {ell}-tuples. Genome Research, 13: 1916-1922, 2003. >HTML
5. Chevauchements >PDF [7 heures]
Sujets
  • alignement de deux séquences
  • heuristiques : hachage, X-drop
  • pratique : assembleurs CAP3, Arachne, Phusion
Lecture obligatoire
  • IHGSC. Initial sequencing and analysis of the human genome. Nature, 609: 860-921 (2001). >HTML
Références
  • 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
  • Waterman 7.1 ou Gusfield 16.17 : la super-séquence la plus courte.
  • Waterman 9.1-9.6 ou Gusfield 11.1-11.7 : alignement de deux séquences.
  • Chiaromonte, V. B. Yap, & W. Miller. Scoring pairwise genomic sequence alignments. Pacific Symposium on Biocomputing, 7: 115-126 (2002). [scores pour subsitutions] >PDF
  • Batzoglou, S., D. B. Jaffe & al. ARACHNE: a whole-genome shotgun assembler. Genome Research, 12: 177-189 (2002). >HTML
  • Mullikin, J. C., et Z. Ning. The Phusion assembler. Genome Research, 13: 81-90 (2003). >HTML
  • 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
  • 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
6. Assemblage >PDF [7+1 heures]
Sujets
  • layout : construction de contigs
  • ossatures
  • consensus et profiles
Lectures obligatoires
  • Huang, X., et A. Madan. CAP3: a DNA sequence assembly program. Genome Research, 9: 868-877 (1999). >HTML
  • Myers, E. W. & al. A whole-genome assembly of Drosophila. Science, 287: 2196-2204 (2000). [ossatures] >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).
  • Kent, W. J. & D. Haussler. Assembly of the working draft of the human genome with GigAssembler. Genome Research, 11: 1541 (2001). [orientation de contigs, utilité des ESTs] >HTML
  • Huson, D. H., K. Reinert & E. W. Myers. The greedy path-merging algorithm for contig scaffolding. Journal of the ACM, 49: 603-615 (2002). [ossatures] >HTML
  • Pop, M., D. S. Kosack, & S. L. Salzberg. Hierarchical scaffolding with Bambus. Genome Research, 14: 149-159 (2004). [ossatures] >HTML
  • Wang, J. & al. RePS: A sequence assembler that masks exact repeats identified from shotgun data. Genome Research, 12: 824-831 (2002). >HTML
  • Huang, X. & A. Madan. CAP3: a DNA sequence assembly program. Genome Research, 9: 868-877 (1999). [consensus]
  • Gusfield 14.1-14.3.1. [alignement multiple et profiles]
Présentation par Tamás Marcinkovics : Ossatures et assemblage hybride >PDF.
  • Huson, D, K. Reinert, & E. W. Myers. The greedy path-merging algorithm for contig scaffolding. Journal of the ACM, 49: 603-615 (2002). >HTML. (version préliminaire à RECOMB 2001: HTML)
  • Huson, D. & al. Design of a compartmentalized shotgun assembler for the human genome. Bioinformatics, 17: S132-S139 (2001). >HTML
  • Waterston, R. H., E. S. Lander, & J. E. Sulston. On the sequencing of the human genome. Proceedings of the National Academy of Sciences of the USA, 99: 3712-3716 (2002). >HTML
7. Cartographie >PDF [1+2 heures]
Sujets
  • concept de cartographie physique et génétique
  • empreintes, STS, bouts de BACs
Présentation par Pierre-Alexandre Ladouceur : Problème de double digestion >PDF ou PPT.
  • Pevzner, P. A. Computational Molecular Biology : an Algorithmic Approach, chapitre 2, MIT Press, Cambridge (2000).
  • Pevzner, P. A. DNA physical mapping and alternating Eulerian cycles in colored graphs. Algorithmica, 13: 77-105 (1995).
Présentation par Michel Devine : Optical mapping
  • Muthukrishnan, S. & L. Parida. Towards constructing physical maps by optical mapping: an effective, simple, combinatorial approach. RECOMB 1997: 209-219. [modèle 0-1] >HTML.
  • Karp, R. M. & R. Shamir. Algorithms for optical mapping. Journal of Computational Biology, 7: 303-316 (2000). [modèle 0-1 analyse avancé] >HTML.
  • Anantharaman, T. S., B. Mishra & D. C. Schwartz. Genomics via optical mapping II: Ordered restriction maps. Journal of Computational Biology, 4: 91-118 (1997). [modèle probabiliste] >PDF (preprint au site de Bud Mishra).
8. Séquençage par hybridation >PDF [4+1 heures]
Sujets
  • puces ADN et le graphe de Bruijn
  • reséquençage par puces
  • application à séquençage shotgun : Euler
  • bases universelles
Lecture obligatoire
  • 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
Références
  • Waterman 7.2 (puces ADN)
  • Pe'er, I., N. Arbili & R. Shamir. A computational method for resequencing long DNA targets by universal oligonucleotide arrays. Proceedings of the National Academy of Sciences of the USA, 99: 5492-15496 (2002). [alignement de spectrum - théorie] >HTML
  • Pe'er, I. & al. Advanced computational techniques for re-sequencing DNA with polymerase signaling assay arrays. Nucleic Acids Research, 31: 5667-5675 (2003). [alignement de spectrum - pratique] >HTML
  • Idury R. et M. S. Waterman. A new algorithm for DNA sequence assembly. Journal of Computational Biology, 2: 291-306 (1995).
  • Pevzner, P. A., H. Tang & M. S. Waterman. A new approach to fragment assembly in DNA sequencing. RECOMB 2001, 256-267. [version préliminaire de l'article de journal] >HTML
  • Pevzner, P. A. et H. Tang. Fragment assembly with double-barreled data. Bioinformatics, 17: S225-S233 (ISMB 2001). [Euler-DB] >HTML
  • Frieze, A. M., F. P. Preparata & E. Upfal. Optimal reconstruction of a sequence from its probes. Journal of Computational Biology, 6: 361-368 (1999). [bases universelles] >HTML
Présentation par Ming-Te Cheng : DNA segmentation >PDF (41M) ou PPT (490k).
  • Braun J. V. & H.-G. Müller. Statistical methods for DNA segmentation. Statistical Science, 13: 142-162, 1998.
  • Li, W., P. Bernaola-Galván, F. Haghighi, & I. Grosse. Applications of recursive segmentation to the analysis of DNA sequences. Computers & Chemistry, 26:491-510 (2002). >HTML.
  • Csürös, M. Algorithms for finding maximal-scoring segment sets. WABI 2004, 62-73. >PDF.
9. Comparaison de séquences >PDF [9+2 heures]
Sujets
  • génomique comparative
  • recherche de homologies : hachage et arbres de suffixe
  • alignement de génomes
  • alignement statistique
Lecture obligatoire
  • 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.
Références
  • Batzoglou, S., L. Pachter, J. P. Mesirov, B. Berger & E. S. Lander. Human and mouse genome structure: comparative analysis and application to exon prediction. Genome Research, 10: 950-958 (2000). [méthode ROSETTA] >HTML.
  • Blanchette, M. & M. Tompa. Discovery of regulatory elements by a computational method for phylogenetic footprinting. Genome Research, 12: 739-748 (2002). >HTML.
  • Ma, B., J. Tromp & M. Li. PatternHunter: faster and more sensitive homology search. Bioinformatics, 18: 440-445 (2002). >PDF
  • Karlin, S. & S. F. Altschul. Methods for assessing the statistical significance of molecular sequence features by using general scoring schemes. Proceedings of National Academy of Sciences of the USA, 87: 2264-2268 (1990). >HTML.
  • Gusfield, Section 13.3 [chaînage d'alignements locaux]
  • 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.
  • 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.
  • 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.
  • 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.
  • Thorne, J. L., H. Kishino & J. Felsenstein. An evolutionary model for maximum likelihood alignment of DNA sequences. Journal of Molecular Evolution, 33: 114-124 (1991). >PDF (sur le site de Jeffrey Thorne).
  • Hein, J., C. Wiuf, B. Knudsen, M. B. Moller & G. Wibling. Statistical alignment: Computational properties, homology testing and goodness-of-fit. Journal of Molecular Biology, 302: 265-279 (2000). [aperçu de l'alignement statistique] >HTML.
  • Knudsen, B. & M. M. Miyamoto. Sequence alignments and pair hidden Markov models using evolutionary history. J. Mol. Biol., 333: 453-460 (2003). >HTML.
Présentation par Mahshid Shakiba : Alignement de génomes à l'aide d'arbres de suffixe >PDF (38M) ou PPT (300k).
  • 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.
Présentation par Maribel Hernández Rosales : Comparative gene prediction >PDF ou PPT.
  • Burge, C. & S. Karlin. Prediction of complete gene structures in human genomic DNA. Journal of Molecular Biology, 268: 78-94 (1997). [GENSCAN] >HTML.
  • Yeh, R-F., L. P. Lim & C. B. Burge. Computational inference of homologous gene structures in the human genome. Genome Research, 11: 803-816 (2001). [GenomeScan] >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.
  • Birney, C., M. Clamp & R. Durbin. GeneWise and Genomewise. Genome Research, 14: 988-995 (2004). >HTML.

Devoirs

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