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 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:

Missed Course Work and Academic Misconduct:


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:

    Reading:

    Links:


    last update 08/03/25, andrew