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.