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
- 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
- Nariya Saitou sur la génomique comparative.
- Paul Havlak sur le projet du génome du rat.
- 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.