Algorithms for Bioinformatics (CPSC 445)

[General Info] · [Course Outline] · [Course Calendar] · [Grading] · [Assignments] · [Resources]

Latest news (06/04/15):

The schedule for the oral final examinations is available here. All examinations are held in Holger's office (ICCS X541). Students must be available at precisely the time shown on the exam schedule and are urged to take any measures necessary to ensure timely arrival at the exam location. Late arrivals or missed exams will be handled strictly according to UBC examination rules. As for any UBC examinations, students need to bring student ID and gouvernment-issued picture ID. Each oral exam will take about 15-20 minutes. The examiner (Holger) may ask questions on any materials covered in the course (i.e., lectures, assignments, quizzes), but a significant part of the exam will be focussed on material previously covered in homework assignments and quizzes. Exam questions may involve moderate amounts of calculation as a means of demonstrating knowledge of algorithms covered in the course.
All assignment and quiz results are now available on WebCT.

Classes:
Tue+Thu, 9:30-11:00 in DMP 301
First class: Tue, 2006/01/10

Instructor:
   Holger H. Hoos
   E-mail: hoos@cs.ubc.ca
   Office: ICICS/CS complex, Room X542
   Office hours: Tue, 11:00-11:30 + Thu, 12:00-12:30

Teaching Assistants:
Baharak Rastegari (baharak "at" cs.ubc.ca)
MohammadAli Safari (safari "at" cs.ubc.ca)

Course Description:

Bioinformatics involves the application of computational methods in order to address problems in molecular biology. This course will provide a introduction to algorithms and their applications in bioinformatics. Topics in molecular biology that will motivate the algorithmic content of the course include: sequence alignment, phylogenetic tree reconstruction, prediction of RNA and protein structure, gene finding and sequence annotation, gene expression, and biomolecular computing.

Graduate and senior undergraduate students in computer science, or from the biological sciences who already have a substantial background in programming and algorithm design, are welcome to take CPSC 445. Because the course involves a significant project, a solid background in computer programming is required. Background in discrete mathematics or in probability theory, such as can be obtained in a college level course in Mathematics or Statistics, is especially relevant to the course content. Students should also be comfortable with mathematical reasoning. Solid basic knowledge in molcular biology is required or will need to be ackquired during the course.

Note to students: Due to the interdisciplinary and advanced nature of the material covered, you should expect the course to be very challenging and time-consuming. It will probably involve more work per credit than most other courses you have taken.

Class assignments will familiarise students with biological data and tools for understanding this data and will help students gain a solid understanding of principles for design and analysis of algorithms. Some assignments will involve the use and extension of software tools, and others will involve written studies of algorithms and their analysis. Class projects will bring together students with different backgrounds to apply ideas from the course to a problem in molecular biology. Students in CPSC 445, the undergraduate version of the course, will work on smaller projects or project components and get additional homework assignments.

Course Outline

A course outline can be found here.

Student Evaluation and Grading

Final grades will be determined approximately as follows:

homework assignments (problems and questions; hands-on use of tools, literature research; approx. five overall) - ca. 45%
in-class quizzes (cover lectures and assignments; approx five) - ca. 20%
final examination - ca. 35%

Policy on late assignments and missed course work:

Late hand-ins of assignments will not be accepted in this course.
Missed course work (assignments, quizzes, etc.) can only be excused in the case of officially documented medical reasons (doctor's note required).

Assignments

Reading Assignment: Douglas R. Hofstadter: Metamagical Themas, Chapter 27: The Genetic Code: Arbitrary? Bantam Books, 1986. [Available from the CPSC 445/545 box in the ICICS Reading Room] (by Thu, 06/01/12)

Assignment 1 (due Tue, 06/01/31; covers Module 1)
Assignment 2 (due Tue, 06/02/21; covers Module 2)
Reading Assignment: p.169-173 (material on neighbour joining, rooting trees) from Durbin, Eddy, Krogh, Mitchison: Biological Sequence Analysis, Cambridge University Press, 1998, [The book is available from the CPSC 445/545 box in the ICICS Reading Room] (by Tue, 06/02/28)
Assignment 3 (due Tue, 06/03/07; covers Module 3)
Reading Assignment: p.??-?? (material on backward method for HMMs) from Durbin, Eddy, Krogh, Mitchison: Biological Sequence Analysis, Cambridge University Press, 1998, [The book is available from the CPSC 445/545 box in the ICICS Reading Room] (by Tue, 06/03/21)
Assignment 4 (due Thu, 06/03/23; covers Module 4)
Assignment 5 (due Thu, 06/04/06; covers Module 5)

Resources

Reading:

Durbin, Eddy, Krogh, Mitchison: Biological Sequence Analysis. Cambridge University Press, 1998 (Ch. 2-3, 7-8)

Baldi, Brunak: Bioinformatics - The Machine Learning Approach. MIT Press, 1998 (Ch. 1)

Lecture notes from CSE 527, Winter 2000 (Martin Tompa) at U Washington on RNA secondary structure prediction: [1], [2]
Gheorghe Paun: Introduction to Membrane Computing [An introduction to P-Systems]
L.Adleman: Molecular Computation of Solutions to Combinatorial Problems. Science 266(5187):1021-1024 [Seminal paper on DNA computing]

Links:

Animations by Patty Hain and Nathan Wambaugh (U Nebraska) on protein biosynthesis: [1] [2] [3]
Animated illustration of chromatin structure (BioStudio)
Interactive animation of MAP kinase signal transduciton (Davidson College, USA)
Animated illustration of PCR (Sumanas, Inc.)
Animated illustration of DNA sequencing (Sanger method) (BioStudio)
Sequence alignment applet (Penfei Liu, York University, Canada)

last update 06/04/15, hh