CPSC 536A - Bioinformatics Course, Spring 2002

General / Administrative Information

Time: Mon 9:30-11:00, Wed 9:10-10:40 (changed time slot for Wed!)
Room: CISR 304

Instructors: Anne Condon / Holger Hoos

Preliminary Course Outline

Module 1: Introduction and Basics (hh; 1.5wk)

• basics of molecular biology [e.g., BML:1] - 1wk
  • foundations of molecular genetics: DNA, RNA, proteins; transcription, translation, regulation; genome organisation, sexual and asexual reproduction
  • cellular organisation, metabolism, regulatory pathways
  • tree of life, phylogeny
  • modern biochemical techniques: cloning, DNA and protein sequencing, genome mapping, PCR, mutagenesis; in-vivo / in-vitro / in-silico
  • biological models and formalisms: exceptions are the rule
• problems in bioinformatics: overview [BML:1.5] - 0.5wk
  • sequencing genomes: physical mapping, genome structure
  • interpreting genomic sequence data: sequence alignment, gene finding, structure prediction (rna and proteins), pattern discovery
  • understanding the cell / organisms: regulatory pathways and networks, simulations
  • relations between organisms and evolutionary questions: phylogenetic trees, computational models of evolution, simulations
  • biomolecular computing: dna computing, inverse folding, self-assembling structures
  • bioinformatics: tools vs. synergistic research

Module 2: Sequence Alignment (hh; 1.5wk)

• scoring
  • intro, basics
  • details
• global sa
  -> dynamic programming
• local sa
• complex models (affine gap scores etc.)
  -> fsa models
• heuristic methods
  -> blast, fasta, etc.
• multiple sa

Module 3: Phylogenetic Trees (ac/hh; 1.5wk)

• Intro and common algorithms (hh)
  • formulation of the tree reconstruction problem [CRS]
  • parsimony: a sequence-based algorithm [BSA, SO, Fe78]
  • distance-based algorithms [Wa96, SO]
• Probabilistic models and associated algorithms (ac)
  • probabilistic models of evolution;
  • the maximum likelihood algorithm [BSA, CKR]
  • experimental studies of phylogenetic tree algorithms [H92, Wa01]
• Biological perspectives [Wo98]; current research directions (ac)
  • the universal tree of life
  • properties of molecular sequence data used to construct trees
  • fit between models of evolution and real evolution
  • synopsis of other topics in phylogeny and current research questions [Mo00...]

Module 4: RNA and Protein Structure (ac+hh; 1.5wk)

• RNA secondary structure prediction (ac)
  • comparative sequence analysis
  • dynamic programming approaches [Z81, CKR]
  • equilibrium partition function for secondary structure [McC90]
• Prediction of pseudoknots in RNA secondary structure (ac) [I00, L00, R99]
• protein structure (hh)
  • basics: primary, secondary, tertiary, quartary structure; forces that stabilise structure
  • computational problems
  • tertiary structure prediction: approaches, energy minimisation with genetic algorithms [CBC,RRO]
  • secondary structure prediction: simple statisitical methods, chou-fasman rules, neural network approaches [BML,RRO]

Module 5: Gene Finding and Motif Discovery (ac; 2wk)

• gene finding
  • basic problem; why is it interesting? why is it hard?
  • open reading frames ('the watson method')
  • simple pattern search
  • weight matrix methods (WAM, etc.)
  • signal detection and integration
  • HMM-based methods [BML:8.2]
  • state-of-the-art gene finders (HMMGene, GenScen)
  • evaluating gene finding algorithms; probabilistic scores, benchmark collections
  • combining gene finders
• motif discovery and characterisation

Module 6: Gene Expression Analysis and Regulatory Networks (hh; 1.5wk)

• technologies for gene expression analysis (microarrays, SAGE)
• clustering gene expression data
• cancer diagnosis: algorithms for class prediction and class discovery
• inference of regulatory relationships from gene expression data

Module 7: Biomolecular Computing (ac; 1.5wk)

• Adleman's experiment; "classical" models for DNA computing
• Self-assembly models for DNA computing; Winfree's work
• combinatorial and algorithmic problems arising in biomolecular
• computation: inverse RNA folding, theory of self-assembly and resource bounded tiling

Other Topics (not to be covered this time):

• physical mapping [CRS]
• genome structure / rearrangements [CRS]

Algorithms / approaches to be covered:

• dynamic programming
• basic data structures (e.g. as arise in phylogeny tree reconstruction)
• heuristic search / gradient descent / stochastic search (including simulated annealing, genetic/evolutionary algorithms)
• HMMs
• clustering, tree inference
• neural networks
• high-level understanding of what NP-completeness means

Course Projects

Students are expected to select and complete a course project according to the following timetable:

01/15	sample project descriptions are now available
01/22	students form groups and select project
02/04	students submit project proposal
03/04	students submit progress report
04/02	students submit final report
04/17, 10:00-16:00	CPSC53A Bioinformatics Mini-workshop 2002 (project presentations)

Students should work in groups of two or three, preferably combining different background and expertise in each team. Each project team must have at least one, preferably two CS graduate student members. The project proposals and reports will be reviewed and evaluatated according to standard criteria for research proposals / research papers.

Grading

• homework assignments (simple problems and questions; hands-on use of tools, literature research; approx. one per module) - ca. 30%
• course project (proposal, reports, and presentation) - ca. 70%

Assignments

01/07 - due 01/14	Reading assignment: Douglas Hofstadter, The Genetic Code: Arbitrary? (available from the Reading Room)
01/16 - due 01/23	Reading assignment: Durbin, Eddy, Krogh, Mitchison: Biological sequence analysis, Chapter 2, Section 2.3 (available from the Reading Room)
01/23 - due 01/30	Reading assignment: Durbin, Eddy, Krogh, Mitchison: Biological sequence analysis, Chapter 6, Section 6.4 (available from the Reading Room)
01/30 - due 02/06	Assignment 1 (covers Modules 1+2)
02/12 - due 02/27	Assignment 2 (covers Module 3)
03/25 - due 04/08	Assignment 3 (covers Module 4+5)

Resources

Books:

• [ASTS] D.Gusfield: Algorithms on Strings, Trees, and Sequences: Computational Science and Computational Biology. Cambridge University Press, 1997.
• [BSA] Durbin, Eddy, Krogh, Mitchison: Biological sequence analysis: Probabilistic models of proteins and nucleic acids. Cambridge University Press, 1998. (Available from CICSR Reading Room)
  -- [BSA:12] gives a long list of online resources
• [BML] P. Baldi, S. Brunak: Bioinformatics: the machine learning approach. MIT Press, 1998. (Available from CICSR Reading Room)
• [BIOCH] Garret and Grisham: Biochemistry. Saunders College Publishing, 1995
  -- used parts of Chapters 1-7 for Module 1
• [MBC] Alberts, Bray, Lewis, Raff, Roberts, Watson: Molecular Biology of the Cell. Garland Publishing, Inc., 1994
  -- used parts of Chapters 1-7 for Module 1
• Benjamin Lewin: Genes V. Oxford University Press, 1994.
• [GA] Griffiths, Miller, Suzuki, Lewontin, Gelbart: An Introduction to Genetic Analysis. Freeman and Company, 1993.
• Watson, Gilman, Witkowsi, Zoller: Recombinant DNA. Scientific American Books, 1992.
• Gesteland, Cach, Atkins (Editors): The RNA World. Cold Spring Harbor Laboratory Press, 1999.
  -- used part of Chapter 24 (translation of selenocystein) for Module 1
• T.Brock, M.Madigan, J.Martinko, J.Parker: Biology of Microorganisms. Prentice Hall, Seventh Edition, 1994

Papers / online articles: