CISC-471: Computational Biology

(also known as: CMPE-471)

(Winter 2015)

Last Modified:

Education is not the filling of a pail, but the lighting of a fire. William Butler Yeats.

Quick Links

Grading
Homework
Outline and Schedule

Course Instructor

David Rappaport
GOODWIN HALL Room 532
E-MAIL: daver AT cs dot queensu dot ca
OFFICE HOURS: TBD.

Class Hours

Monday	12:30-13:30	Goodwin 521
Wednesday	11:30-12:30	Goodwin 521
Thursday	13:30-14:30	Goodwin 521

Tutorial

Monday 2:30-4:30 GOODWIN RM248

Text

Neil C. Jones and Pavel A. Pevzner (2004) An Introduction to Bioinformatics Algorithms, MIT Press.
I will be following this book and referring to it as the "text". If you want to purchase a textbook this is the one that I would recommend as a first choice.
There is a wealth of material available on-line to supplement this text book.
Powerpoint slides are provided.
Bioinformatics Algorithms: An Active Learning Approach. is an enhanced electronic textbook developed by the author of the course text. You can access free videos and Powerpoint slides.
Rosalind is a platform for learning bioinformatics through problem solving.

Arthur M. Lesk (2002) Introduction to Bioinformatics, Oxford University Press.

An electronic copy of this book is available from the Queen's Library .
Other books that I have on my desk are:
Wing-Kin Sung (2010) Algorithms in Bioinformatics: A Practical Introduction, CRC Press
Pavel A. Pevzner (2001) Computational Molecular Biology: An Algorithmic Approach

Homework

Homework 1.
Homework 2.
Homework 3.
Homework 4.
Homework 5. Note that homework 5 is the same as 4.
Homework 6.
Homework 7.
Homework 8.
Homework 9.

Course Description

Calendar Description of CISC-471

Advanced computational approaches to the problems in molecular biology. Techniques and algorithms for sequence analysis and alignment; molecular databases; protein structure prediction and molecular data mining.

Prerequisites: CISC-271/3.0, CISC-352/3.0, CISC-365/3.0, BCHM 218/3.0 (or MBIO-218/3.0), BIOL-334/3.0 (or BCHM-315/3.0).

This course is required in the Biomedical Computing (BMCO) program.

My Description of CISC-471(David Rappaport)

Advances in computer hardware and algorithmic techniques have opened many avenues of inquiry that are driven by computation. The fields of Biology and Medicine are two high profile examples where stunning scientific breakthroughs have occurred within the past few years. In this course I will follow the course text An Introduction to Bioinformatics Algorithms by Neil C. Jones and Pavel A. Pevzner by reviewing standard algorithmic techniques and how they are applied to scientific discovery in biology and bioinformatics. The emphasis will be on the strengths and limitations of these techniques.

Learning outcomes

Knowledge of state of the art algorithms in Bioinformatics with emphasis on the strengths and limitations of these techniques.
Ability to distill information provided by a biologist and discern appropriate and effective algorithmic solutions.
By the end of the course students should be able to:
critically assess an algorithm for its correctness and efficiency, and argue about the algorithms correctness, performance bounds, and approximation ratio as appropriate
obtain an ability to make sensible pragmatic algorithmic choices of standard packages or implementations for specific applications

Outline and Schedule

Chapters numbers correspond to Neil C. Jones and Pavel A. Pevzner (2004) An Introduction to Bioinformatics Algorithms, MIT Press.

Week 1: Jan. 5-9 - Introductory topics. Chapters 1-3.
Week 2-3: Jan. 12-23 - Exhaustive search, branch and bound. Chapter 4.
Week 4-5: Jan. 26- Feb. 6 - Greedy algorithms. Chapter 5.
Week 6-7: Feb. 16 - 27 - Dynamic programming, sequence alignment Chapter 6.
Week 8-9: March 2-13 - Divide and conquer, sequence alignment Chapter 7.
Week 10-12 March 16 - April 3. To be discussed, and review.

The following table will be updated as the term progresses.

	Monday	Wednesday	Thursday
Week 1 Introduction.	January 5 Introduction/ Finding most frequent k-mers Watch this video: The Search for Hidden Messages in the Replication Origin (Part 1). In particular near the 10 minute mark he discusses different approaches to solve the most frequent k-mer problem.	January 7 Finding most frequent k-mers, continued. Review of Big-Ο, Big-Ω, Big-Θ	January 8 Making Change See Section 2.3 of the text.
Week 2 Exhaustive Search. (Chapter 4)	January 12 Be prepared to share your homework solutions in class.	January 14 Restriction Mapping. See section 4.1-4.3 of the text.	January 15 Restriction Mapping. See section 4.1-4.3 of the text.
Week 3 Exhaustive Search. (Chapter 4) Greedy Algorithms (Chapter 5)	January 19 Be prepared to share your homework #2 solutions in class. Stef presented solutions in class today. I have appointed Jacob and Curtis to be presenters next week. If you want to be arrange presenting ahead of time send me an email message, or talk to me after class.	January 21 Motif finding. See section 4.4-4.9 of the text.	January 22 Genome Rearrangements See section 5.1-5.3
Week 4 Greedy Algorithms (Chapter 5) and Dynamic Programming Algorithms (Chapter 6)	January 26 Be prepared to share your homework #3 solutions in class. If you want to arrange presenting ahead of time send me an email message, or talk to me after class.	January 28 Genome Rearrangements See section 5.4-5.5	January 29 Dynamic programming algorithms, sequence alignment Chapter 6 sections 6.1-6.2
Week 5 Dynamic Programming Algorithms (Chapter 6)	February 2 Quiz #1. I will test your knowledge of material that is related to Homeworks 1 -3. The Quiz will be held in Goodwin Hall Room 254.	February 4 Solutions to Quiz #1. Edit distance and sequence alignment	February 5 Edit distance and and sequence alignment, Chapter 6 sections 6.4-6.5
Week 6 Dynamic Programming Algorithms (Chapter 6)	February 9 Be prepared to share your homework #4 a.k.a. homework #5 solutions in class. If you want to arrange presenting ahead of time send me an email message, or talk to me after class.	February 11 Global sequence alignment and scoring alignments sections 6.6 and 6.7.	February 12 Local sequence alignment section 6.8
Reading week	February 16	February 18	February 19
Week 7 Dynamic Programming Sequence Alignment (Chapter 6)	February 23 Be prepared to share your homework #6 solutions in class. If you want to arrange presenting ahead of time send me an email message, or talk to me after class.	February 25 Alignment with Gap Penalties. I have prepared an example that illustrates an algorithm that performs global alignment with affine gap penalties.	February 26 Multiple Alignment
Week 8 Divide and Conquer (Space efficient Sequence Alignment)	March 2 Note that homework is due on Wednesday this week. Space efficient sequence alignment.	March 4 Be prepared to share your homework #7 solutions in class. If you want to arrange presenting ahead of time send me an email message, or talk to me after class.	March 5 DNA sequencing, Shortest Superstring Problem, Traveling Salesman Problem.
Week 9 Graph Algorithms	March 9 Quiz #2. I will test your knowledge of material that is related to Homeworks 4 - 7. The Quiz will be held in Goodwin Hall Room 254.	March 11 Presentation on NP-complete problems. Sequencing by Hybridization, Euler tours	March 12 Euler tours, Interval graphs
Week 10 Combinatorial Pattern Matching Suffix Tree	March 16 Solutions to Quiz 2. Exact pattern matching, Trie	March 18 Suffix Tree	March 19 Be prepared to share your homework #8 solutions in class. If you want to arrange presenting ahead of time send me an email message, or talk to me after class.
Week 11 Gene Database Search	March 23 Quiz #3.	March 25 Approximate pattern matching using filtration, Gene Database Search, the BLAST algorithm.	March 26 The BLAST algorithm, k-means clustering.
Week 12 Review	March 30 Solutions to Quiz #3 Review.	April 1 Class is cancelled to allow participation in the School of Computing "Creative Computing Showcase.	April 2 Be prepared to share your homework #9 solutions in class. If you want to arrange presenting ahead of time send me an email message, or talk to me after class. Final review. The Final will be based on homework 1-9.

Grading

Grades will be made up of classroom participation, midterm quizzes and a final. Assigned homework will include some programming exercises. A large component of the course will involve students solving assigned problems in class.
In class participation: 15%
Three in class midterm quizzes, each worth 15%, total: 45%
Final exam: 40%
The quizzes will be scheduled as follows:
Quiz 1: Monday Feb. 2.
Quiz 2: Monday March 9.
Quiz 3: Monday March 23.
Quizzes will be held in Goodwin Hall Room 254.

Please make every effort to be present for the midterm quizzes. If you miss quizzes then the marking scheme will be revised for you as follows:
1 missed - 2 quizzes 20% each 45% final.
2 missed - 1 quiz 30%, and 55% final.
3 missed - 85% final.

Academic Integrity

Academic integrity is constituted by the five core fundamental values of honesty, trust, fairness, respect and responsibility (see www.academicintegrity.org). These values are central to the building, nurturing and sustaining of an academic community in which all members of the community will thrive. Adherence to the values expressed through academic integrity forms a foundation for the "freedom of inquiry and exchange of ideas" essential to the intellectual life of the University (see the Senate Report on Principles and Priorities).
Students are responsible for familiarizing themselves with the regulations concerning academic integrity and for ensuring that their assignments conform to the principles of academic integrity. Information on academic integrity is available in the Arts and Science Calendar (see Academic Regulation 1 ), on the Arts and Science website (see Academic Integrity ), and from the instructor of this course. Departures from academic integrity include plagiarism, use of unauthorized materials, facilitation, forgery and falsification, and are antithetical to the development of an academic community at Queen's. Given the seriousness of these matters, actions which contravene the regulation on academic integrity carry sanctions that can range from a warning or the loss of grades on an assignment to the failure of a course to a requirement to withdraw from the university.

Disability Accommodations

Queen's University is committed to achieving full accessibility for persons with disabilities. Part of this commitment includes arranging academic accommodations for students with disabilities to ensure they have an equitable opportunity to participate in all of their academic activities. If you are a student with a disability and think you may need accommodations, you are strongly encouraged to contact the Disability Services Office (DSO) and register as early as possible. For more information, including important deadlines, please visit the DSO website at: HCDS

Accommodation Requests

Please let me know if you require any special accommodations.