Matériel

Lectures

Introduction (jeudi 4 septembre)
Acétates : PDF
Lecture obligatoire : Molecular Biology for Computer Scientists - par Lawrence Hunter (in L. Hunter, Artificial Intelligence and Molecular Biology, AAAI Press)
Référence additionnelle : Structure de la molécule d'ADN - notes de cours de Gilles Bourbonnais de l'Université de Laval.
Manipulation d'ADN (mercredi 10 septembre)
Acétates : PDF
Calcul moléculaire (11 et 17 septembre)
Acétates : PDF
Références
  • Adleman, L. M. Molecular computation of solutions to combinatorial problems. Science, 266 : 1021-1023 (1994). >Version soumise (PDF) au site du Labo Adleman.
  • Clelland C. T., V. Risca, et C. Bancroft. Hiding messages in DNA microdots. Nature, 399 : 533-534 (1999). >HTML
  • Bancroft C., T. Bowler, B. Bowler, et C. T. Clelland. Long-term storage of information in DNA. Science, 293 : 1763-1765 (2001). >HTML
  • Stojanovic, M. N., T. E. Mitchell, et D. Stefanovic. Deoxyribozyme-based logic gates. Journal of the American Chemical Society, 124 : 3555-3561 (2002). >HTML
  • Stojanovic, M. N., et D. Stefanovic. A deoxyribozyme-based molecular automaton. Nature Biotechnology, 21 : 1069-1074 (2003). >HTML
  • Y. Benenson, R. Adar, T. Paz-Elizur, Zvi Livneh, et 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
Présentation par Thomas Leplus : DNA self-assembly and cryptography > PDF et notes (PDF).
  • Winfree, E., F. Liu, L. A. Wenzler, et N. C. Seeman. Design and self-assembly of two-dimensional DNA crystals. Nature, 394 : 539-544 (1998). >HTML
  • Gehani, A., T. H. LaBean, et J.H. Reif. DNA-based Cryptography. Proc. DNA Based Computers V, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Volume 54, edited by E. Winfree and D.K. Gifford, American Mathematical Society, Providence, RI, 233-249, (2000). >PDF
Assemblage I (18-30 septembre)
Acétates : PDF.
Lectures obligatoires
  • E. D. Green. Strategies for the systematic sequencing of complex genomes. Nature Reviews Genetics, 2 : 573-583 (2001). >La version HTML n'est pas accessible sans abonnement mais vous pouvez copier ~csuros/pub/green.pdf sur les machines de DIRO.
  • IHGSC. Initial sequencing and analysis of the human genome. Nature, 609 : 860-921 (2001). >HTML
Références additionnelles
  • Waterman 6.1.1, 7.1.5: statistiques pour îles et océans.
  • Waterman 7.1 ou Gusfield 16.17: la super-séquence la plus courte.
Chevauchements (2-21 octobre)
Acétates : PDF.
Lectures obligatoires
  • Waterman 9.1-9.6 ou Gusfield 11.1-11.7: alignement de deux séquences.
  • Huang, X., et A. Madan. CAP3: a DNA sequence assembly program. Genome Research, 9 : 868-877 (1999). >HTML
  • Mullikin, J. C., et Z. Ning. The Phusion assembler. Genome Research, 13 : 81-90 (2003). >HTML
Références additionnelles
  • Batzoglou, S., D. B. Jaffe, et al. ARACHNE: a whole-genome shotgun assembler. Genome Research, 12: 177-189 (2002). >HTML
  • Altschul, S. F., et 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, et M. Li. PatternHunter: faster and more sensitive homology search. Bioinformatics, 18 : 440-445 (2002). [implantation du tableau de k-mers] >PDF
Assemblage II (23 octobre - 6 novembre)
Acétates : PDF.
Références
  • Sutton G. R., O. White, M. D. Adams, et 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] >Preprint (PostScript) sur le site de Gene Myers.
  • Myers, E. W., et al. A whole-genome assembly of Drosophila. Science, 287 : 2196-2204 (2000). [ossatures] >HTML
  • Huson, D. H., K. Reinert, et E. W. Myers. The greedy path-merging algorithm for contig scaffolding. Journal of the ACM, 49 : 603-615 (2002). [ossatures] >HTML
  • Kent, W. J., et 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
  • Huang, X., et 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]
Séminaires
Cartographie physique (11 et 13 novembre)
Acétates : PDF
Références
  • Pevzner, P. A. Computational Molecular Biology : an Algorithmic Approach, chapitre 2, MIT Press, Cambridge (2000). (problème DDP)
  • Pevzner, P. A. DNA physical mapping and alternating Eulerian cycles in colored graphs. Algorithmica, 13 : 77-105 (1995). (DDP)
  • Alizadeh, F., R. M. Karp, L. A. Newberg, et D. K. Weisser. Physical mapping of chromosomes : a combinatorial problem in molecular biology. Algorithmica, 13 : 52-76 (1995). [voyageur commerçant, chemins de réseau]
  • Gusfield ch. 16.4-16.8. [cartes STS, voyageur commerçant, chemins de réseau]
Présentation par Patrick Charbonneau : Double Digest Problem > PowerPoint ou PDF.
Séquençage par hybridation (18 - 27 novembre)
Acétates : PDF.
Lectures obligatoires
  • Pevzner chapitre 5 (DNA Arrays)
  • Pevzner, P. A., H. Tang, et M. S. Waterman. A new approach to fragment assembly in DNA sequencing. RECOMB 2001, 256-267. >HTML
Références additionnelles
  • Waterman 7.2 (puissance des puces)
  • Idury R. et M. S. Waterman. A new algorithm for DNA sequence assembly. Journal of Computational Biology, 2 : 291-306 (1995).
  • 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, et E. Upfal. Optimal reconstruction of a sequence from its probes. Journal of Computational Biology, 6 : 361-368 (1999). [bases universelles] >HTML
  • Pe'er I., N. Arbili, et 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] >HTML
Présentation par Nicolas Bruchon : Séquençage par hybridation > PowerPoint ou PDF; notes (PDF).
Présentation par Frédéric Morin : Filtres non-continus > PDF.
  • Ma, B., J. Tromp, et M. Li. PatternHunter: faster and more sensitive homology search. Bioinformatics, 18 : 440-445 (2002).
  • J. Buhler, U. Keich, et Y. Sun. Designing seeds for similarity search in genomic DNA. RECOMB 2003, 93-101. >HTML
Pooling (2 et 4 décembre)
Références
  • Anderson, I., et I. Honkala. A short course on combinatorial designs. [plan projectif PG(2,p)] >PostScript
  • Alon, N., R. Beigel, S. Kasif, S. Rudich, et B. Sudakov. Learning a hidden matching. IEEE Symposium on Foundations of Computer Science, 2002. [algorithme aléatoire pour PCR multiplexé] >PDF

Devoirs

Projet

Implantation d'un assembleur de génome complet, et assemblage du génome de Rickettsia typhi. Date limite : matin de 12 décembre. >PDF.