Algorithms for Bioinformatics (CPSC 445)

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

Latest news (2012/04/13):

All remaining quizzes and assignments have been marked and e-mailed to you (Assignment 4) or are available for pick-up from the box outside Holger's office (everything else). Good luck with your final preparations for the exams next week!
Finalised times for the final oral exams are now available here. All exams will take place in Holger's office (ICCS X541). Please make sure to be there on time (we highly recommend planning for contingencies). Final exams may cover any course materials from classes and assignments. Good luck with your preparations!
Holger and Joel will offer additional office hours between 10 and 13 April; these will be posted by the end of this week.
We expect the final exam schedule by 03/29, 14:00.

Classes:
Tue+Thu, 14:00-15:30 in DMP 201
First class: Thu, 2012/01/05

Instructor:
   Holger H. Hoos
   E-mail: hoos "at" cs.ubc.ca
   Office: ICICS/CS complex, Room X541
   Office hour: Wed, 9:00-10:00
   If I'm not in my office, check ICCS X530.

Teaching Assistant:
   Joel Ferstay (joelaf "at" cs.ubc.ca)
   Office: ICCS X468.
   Office hours: Mon, 10:00-12:00

About this course:

Bioinformatics involves the application of computational methods to answer or provide insight on questions in molecular biology. This course provides an introduction to the design and analysis of algorithms for bioinformatics applications. Topics covered will include sequence alignment, phylogenetic tree reconstruction (parsimony and distance-based methods), prediction of RNA and protein structure, gene finding, and motif finding. Algorithmic techniques that will be discussed include dynamic programming and heuristic search methods, as well as combinatorial algorithms for exploration of graphs and trees. Statistical models of molecular sequence and structure, such as hidden Markov models and stochastic context free grammars, and associated algorithms, will also be covered.

Prerequisites:

CPSC 320 and six credits of BIOL beyond BIOL 111, or equivalent. Experience with design and analysis of algorithms is essential for this course. Related texts listed below, such as “Molecular Biology of the Cell”, will be useful for those who need to catch up on biological background. The algorithms texts by Cormen et al. and by Kleinberg and Tardos provide useful background on combinatorial algorithms, including graph algorithms and dynamic programming algorithms. The text by Hoos and Stützle is a more advanced text which provides very useful background on local search techniques.

Recommended Textbook:

Durbin, Eddy, Krogh, Mitchison: Biological Sequence Analysis. Cambridge University Press, 1998

Course Wiki

You can access the course wiki here: Course Wiki

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. three) - ca. 20%
final examination - ca. 35%

Missed Course Work and Academic Misconduct:

University policy and departmental guidelines on incompletes and academic misconduct will be followed strictly.
All work on the quizzes and exams must be entirely your own, with no discussion or aid from anyone else.
Late hand-ins of assignments will not be accepted.
Missed course work (assignments, quizzes, etc.) can only be excused in the case of officially documented medical reasons (doctor's note required).

Assignments

Assignment 1 (due Fri, 2012/02/17)

Assignment 2 (due Tue, 2012/03/27)

Assignment 3 (due Tue, 2012/04/03)

Assignment 4 (due Tue, 2012/04/10)

Resources

Handouts:

Course information (from class 1)
Introduction to string matching (including KMP algorithm) (assigned reading for Thu, 01/12)

Reading:

Alberts, Bruce et al. Molecular Biology of the Cell (4th edition). Garland Publishing, 2002,
Baldi, Brunak. Bioinformatics - The Machine Learning Approach (1st/2nd edition). MIT Press, 1998/2001.
Cormen, Thomas H. et al. Introduction to Algorithms (3rd edition). The MIT Press 2009.
Gusfield, Dan. Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology. Cambridge University Press, 1997.
Hoos, Holger H. and Stützle, Thomas. Stochastic Local Search: Foundations and Applications. Morgan Kaufmann, 2005.
Kleinberg, Jon and Tardos, Eva. Algorithm Design. Addison Wesley, 2006.

Links:

The Human Genome Project Video - 3D Animation Introduction (class 2)

last update 12/04/10, hh