Algorithms for Bioinformatics (CPSC 445)

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

Latest news (2008/04/17):
Assignment 4 is available to be picked up in front of Holger's office (X541). Any old assignments and quizzes not yet picked up will also be there. Any of the material from the assignments and quizzes may be included on the final exam.
Latest news (2008/04/15):
Oral exams will take place on the Monday the 21th and Tuesday the 22st of April, 2008 in room X541 (Holger's office). Oral exams will be around 15 minutes long, and a 5 minute extension is allowed if the instructor deems it necessary. If you cannot attend your given time slot, contact Holger immediately.
We strongly encourage you to arrive 15 minutes prior to your exam start time, and plan your trip to campus carefully. You are responsible for arriving to your exam on time. Because of the tight schedule, we won't be able to accommodate any reschedule delays.
The final exam schedule can be found here.
Latest news (2008/04/11):
Holger and Andrew are holding extended office hours for the week of April the 14th. Check here for details. If you can't make these times, please get in touch with us.
[news archive]

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

Instructor:
   Holger H. Hoos
   E-mail: hoos "at" cs.ubc.ca
   Office: ICICS/CS complex, Room X541
   New office hours for week of April 14th:
   Tue and Thurs, 11:00-12:30
   If I'm not in my office, check X530.

Teaching Assistant:
   Andrew Carbonetto (acarbo "at" cs.ubc.ca)
   New office hours for week of April 14th:
   Wed, 14:00-16:00 (ICICS/CS X530)

Final Exams:

Oral exams will take place on the Monday the 21th and Tuesday the 22st of April, 2008 in room X541 (Holger's office). Oral exams will be around 15 minutes long, and a 5 minute extension is allowed if the instructor deems it necessary. If you cannot attend your given time slot, contact Holger immediately.

We strongly encourage you to arrive 15 minutes prior to your exam start time, and plan your trip to campus carefully. You are responsible for arriving to your exam on time. Because of the tight schedule, we won't be able to accommodate any reschedule delays.

The exams schedule is as follows:

April 21th

start time end time student

8:30 8:50 Paul Lu

8:50 9:10 Tracy Wilkinson

9:10 9:30 Adam Tarnowsky

break

9:45 10:05 Bryan Holland

10:05 10:25 Varun Ramraj

10:25 10:45 Michael Chuang

break

11:00 11:20 Lina Hu

11:20 11:40 Wang Yip

11:40 12:00 Nicholas Wiebe

lunch

13:00 13:20 Bill Wu

13:20 13:40 Adrian Cortes

13:40 14:00 Kaida Ning

break

14:15 14:35 John Cheu

14:35 14:55 Qin Zheng

14:55 15:15 Carla Reyes

break

15:30 15:50 Raymond Lim

15:50 16:10 Mark Sun

16:10 16:30 Lewis Zhou

April 21th
start time	end time	student
8:30	8:50	Paul Lu
8:50	9:10	Tracy Wilkinson
9:10	9:30	Adam Tarnowsky
break
9:45	10:05	Bryan Holland
10:05	10:25	Varun Ramraj
10:25	10:45	Michael Chuang
break
11:00	11:20	Lina Hu
11:20	11:40	Wang Yip
11:40	12:00	Nicholas Wiebe
lunch
13:00	13:20	Bill Wu
13:20	13:40	Adrian Cortes
13:40	14:00	Kaida Ning
break
14:15	14:35	John Cheu
14:35	14:55	Qin Zheng
14:55	15:15	Carla Reyes
break
15:30	15:50	Raymond Lim
15:50	16:10	Mark Sun
16:10	16:30	Lewis Zhou

April 22th

start time end time student

8:30 8:50 Keane Lim

8:50 9:10 Ernest Tsang

9:10 9:30 Ben Vander Valk

break

9:45 10:05 Michael Joya

10:05 10:25 Cheyenne Kamran

10:25 10:45 Wendy Leung

break

11:00 11:20 Tracy Mew

11:20 11:40 King Long Tse

11:40 12:00 Vaneet Lotay

lunch

13:00 13:20 Jenny Qing Qian

13:20 13:40 Sarah Batara

13:40 14:00 Elena Surkova

April 22th
start time	end time	student
8:30	8:50	Keane Lim
8:50	9:10	Ernest Tsang
9:10	9:30	Ben Vander Valk
break
9:45	10:05	Michael Joya
10:05	10:25	Cheyenne Kamran
10:25	10:45	Wendy Leung
break
11:00	11:20	Tracy Mew
11:20	11:40	King Long Tse
11:40	12:00	Vaneet Lotay
lunch
13:00	13:20	Jenny Qing Qian
13:20	13:40	Sarah Batara
13:40	14:00	Elena Surkova

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

These pages are currently viewable by anyone. All members of the course may edit these topic pages and attach shared material. To do so, your CS TWikiName (a registered ID of the form of FirstnameLastname) must be added to the course access list by the instructor or TA.

To get a CS TWikiName:

Students with CS Undergrad Accounts (ex a1a1): register here and then forward the TWikiName you used to Andrew (or Holger). NOTE: when you log in, you'll use your registered email address and password, not your TWikiName.

Students with CS Grad Accounts: your cs login and password gains you some levels of access throughout the CS Twiki, however your TWikiName is how you are granted access to particular protected areas. Register here and forward your TWikiName to Andrew (or Holger).

Once you've been added to the group access list, you should be able to edit as well as view the cs445 web pages. However, you still need to authenticate yourself for any given session. To trigger the logon dialog, use e.g.
https://bugs.cs.ubc.ca/cgi-bin/twiki/logon/CS445/
rather than https://bugs.cs.ubc.ca/cgi-bin/twiki/view/CS445/

Remember that the login dialog wants your email address (the one you registered if it's non-cs, otherwise your department logon) not your twikiname. Users don't ever have to explictly use their twikinames, which are for internal authentication.

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 Tue, 2008/02/12)

Assignment 2 (due Thr, 2008/02/28)

Assignment 3 (due Tue, 2008/04/01)

Assignment 4 (due Thr, 2008/04/10)

Mini-Projects

Students will prepare a mini-project on a subject related to the course (computer science and bioinformatics). Students will form a group of 2, and no other sized group will be accepted except under strict circumstances. The mini-projects will include a 1/2 page topic outline, a 10 minute presentation (+ up to 5 minutes of questions), and a 3 page report.

Due Thursday, March 6th - Mini-Project Topic Outline. Each group will hand in a project outline. The outline will include a 1/2 page project topic proposal, references and title. The project topic proposal should include a quick summary of the topic (as understood by the group members) and how the topic is related to the course.
Groups should include 2 references. References should either be a literature paper or similar reputable source (ie not wikipedia). If you are unsure whether a reference is acceptable, please consult either Holger or Andrew. The names and student numbers of both groups members should be included. No two groups may select the same reference or topic. Overlap will be resolved on a "first come, first served" basis.
The topic selected should be related to the course material (see the course outline), a topic from any of the text references (including the course textbook) or a topic pertaining to algorithms in bioinformatics. Topics should be above and beyond the material explained in class. If you unsure whether a topic is acceptable, do not hesitate to contact either Holger or Andrew.
Due Thursday April 3rd - Project Report. Each group will prepare a 3 page project report (text; figures, tables, etc not included in the 3 page limit). The report should outline the motivation, results and discussion of each reference and how both relate. Group members should also discuss the importance of each reference to the topic selected and what the group members learned from each reference.

Presentation Dates: April 1,3 & 8 - Project Presentation Each group will give a 10 minute presentation on their selected topic. Group members should share the presentation time equally. Prepare for a 5 minute question/discussion period preceding your presentation. Presentation slides are recommended.

April 1st, 2008
1.	Michael Chuang John Cheu	FASTA vs BLAST
2.	Lingxiao Lewis Zhou Paul Lu	How to Find Optimal Alignments in Linear Space
3.	Vaneet Lotay Michael Joya	Neighbor Joining Method: A Popular Algorithm for Constructing the Topology of Phylogenetic Trees
4.	Lina Hu Wang Yip	MSAID: multiple sequence alignment based on a measure of information discrepancy
5.	Adrian Cortes Ben Vander Valk	Using Sequence Alignment to Discern Germline Gene Fragments of Antibody Sequences
April 3rd, 2008
1.	Jenny Qing Qian Kaida Ning	Algorithms for Short Sequence Assembling
2.	King Long Tse Qin Zheng	PSI-BLAST
3.	Elena Surkova Bryan Holland	Protein Secondary Structure Prediction
4.	Sarah Batara Cheyenne Kamran Keane Lim	The Evolution of Multiple Sequence Alignment Programs
April 8th, 2008
1.	Bill Wu Ernest Tsang	Parital Order Multiple Sequence Alignment
2.	Varun Ramraj Carla Reyes	Parallel Strategies for Sequence Alignment
3.	Raymond Lim Nick Wiebe	Prediction of Conserved RNA Secondary Structure within Protein-coding Regions
4.	Adam Tarnowsky Tracy Wilkinson	Haplotype Inference Algorithms
5.	Mark Sun Tracy Mew	Local Multiple Sequence Alignment using the Biclustering Technique

Note: If two groups would like to switch presentation slots, please send an email to Andrew or Holger cc'ing members of both groups.

Resources

Handouts:

Course information (from class 1)
Introduction to string matching (including KMP algorithm) (class 2+3)
Protein Folding Slides (Guest: Chris Thachuk) (class 22)

Reading:

Alberts, Bruce et al. Molecular Biology of the Cell (4th edition). Garland Publishing, 2002,
Baldi, Brunak. Bioinformatics - The Machine Learning Approach. MIT Press, 1998.
Cormen, Thomas H., Leiserson, Charles, E., and Rivest, Ronald L. Introduction to Algorithms. The MIT Press 1992.
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:

CBC News: Chromosome abnormality linked to autism, study finds (class 3)

Animation of the KMP-Algorithm: http://www.ics.uci.edu/~goodrich/dsa/11strings/demos/pattern/ (class 3)

Java applet illustrating sequence alignment algorithms: http://www.iro.umontreal.ca/~casagran/baba.html (class 5)

Self-Assessment on Multiple Alignment (by Georg Fuellen, University of Bielefeld, Germany): http://www.techfak.uni-bielefeld.de/bcd/Curric/SelfA/mulali1.html" (Class 11)

Java applet for phylogenetic tree inference (UPGMA) by Peter Sestoft (IT University of Copenhagen, Denmark): http://www.itu.dk/~sestoft/bsa/Match7Applet.html (Class 13)

last update 08/03/25, andrew