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.