The web page for the Spring 2006 offering of CPSC 445 can be found here.

CPSC 545/445
Algorithms for Bioinformatics

[General Info] · [Course Outline] · [Course Calendar] · [Course Projects] · [Grading] · [Assignments] · [Resources]
Latest news: The programme of the CPSC 545 Mini-Workshop "Algorithms for Bioinformatics" can now been found here. Slots for talks have been extended to 35min, 10min of which are intended for discussion.

The CPSC 545 Mini-Workshop has been scheduled for Tuesday, 16 March 2004, 13:00-17:30 in McMillan 256.

Author instructions for workshop papers and guidelines for the talks are now available in the "Course Projects" section.

General / Administrative Information

Course number / title: 545 (101) / 445 (101): Algorithms for Bioinformatics

Time: Tue+Thu 9:30-11:00, first class: Tue, 03/09/09
Room: Tue: FSC 1001, Thu: Scarfe 204A

Instructor: Holger Hoos
TAs: Alena Shmygelska, Dan Tulpan

[Current official information on graduate courses in 2003/04 term 1 can be found here]

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 545/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 undergraduate students interested in taking CPSC 445: 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. Also, due to the nature of the course offering (together with 545), enrollment is restricted to a small number of dedicated and exceptionally qualified students.

Class assignments will familiarize 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

Course Projects (CPSC 545 only)

Projects in progress

  • Mario Enriquez, Zsuzsanna Hollander, Joseph Ajay Pathakamuri, Nan Zhang, and Jessica Zheng Zhao: Collecting and Characterizing RNA Molecules with Known Secondary Structure
  • Baharak Rastegari, Shelly Zhao, Mohammad Safari, and Jack Jia: Linear Time Algorithm for Calculating the Free Energy of the RNA Secondary Structure Including Pseudoknots (vs. other algorithms)
  • Mohammed Alam, Warren Cheung, Juan Estrada, and Jamie King: Improvement of the Projection Motif Finding Algorithm
  • Bojana Jankovic, Viet Le, Igor Naverniouk, and Timothy Chan: Comparison of HP and MJ Protein Folding Models on a 3-Dimensional Cubic Lattice

General Information

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

09/15 sample project descriptions are now available
09/22 students form groups and select project
10/06 students submit project proposal
11/03 students submit progress report
12/08 students submit final report

Project presentations will be on Tuesday, 16 March 2004, 13:00-17:30 in McMillan 256.

Preparation and Submission of Final Reports

Since we intend to combine the final reports into a proceedings volume for the mini-workshop, they need to be formatted uniformly. Please use LaTeX for preparing your final report and use this sample text as a template (PDF of the sample text available here). source of the sample text as a template for your report). Final reports have to be submitted as PDF files via e-mail to by 04/03/15, 9:00 PST.

Preparation and Format of Workshop Talks

Each paper will be assigned a 30min slot, 5-10 minutes of which are intended for discussion. An overhead projector as well as an LCD projector will be available in the workshop room. Presenters who want to use the LCD projector need to provide their own laptop or contact Holger about putting their presentation on his laptop (in HTML, PS, or PDF format, no PowerPoint support).

CPSC 545 Mini-Workshop page (includes programme).


Student evaluation and grading will differ between CPSC 445 and CPSC 545.

CPSC 445 Student Evaluation and Grading:

CPSC 545 Student Evaluation and Grading:

  • homework assignments (simple problems and questions; hands-on use of tools, literature research; approx. five overall) - ca. 30%
  • course project (proposal, reports, and presentation) - ca. 70%
Note: Homework assignments for CPSC 445 will be considerably more extensive than those for CPSC 545.



Lecture notes:
Background reading:
  • Alberts, Bray, Lewis, Raff, Roberts, Watson: Molecular Biology of the Cell. Garland Publishing, Inc., 1994 (Parts of Chapters 1-7)
    Note: Any introductory biochemistry text will cover similar information
  • Baldi, Brunak: Bioinformatics - The Machine Learning Approach. MIT Press, 1998 (Ch. 1)
  • Durbin, Eddy, Krogh, Mitchison: Biological Sequence Analysis. Cambridge University Press, 1998 (Ch. 2-3, 7-8)
  • Garret and Grisham: Biochemistry. Saunders College Publishing, 1995 (Parts of Chapters 1-7)
  • Benjamin Lewin: Genes V. Oxford University Press, 1994.
  • Griffiths, Miller, Suzuki, Lewontin, Gelbart: An Introduction to Genetic Analysis. Freeman and Company, 1993.
  • Watson, Gilman, Witkowsi, Zoller: Recombinant DNA. Scientific American Books, 1992.

last update 04/03/15, hh