Algorithms for Bioinformatics (CPSC 445)
· [Course Outline]
· [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.
in DMP 201
First class: Thu, 2012/01/05
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.
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.
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
Durbin, Eddy, Krogh, Mitchison: Biological Sequence Analysis.
Cambridge University Press, 1998
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:
policy and departmental
guidelines on incompletes and academic misconduct will be followed
- 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).
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)
- 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.
last update 12/04/10, hh