CISC-471: Computational Biology

(also known as: CMPE-471)

(Winter 2017)


Last Modified:


Education is not the filling of a pail, but the lighting of a fire. Plutarch.

Quick Links

Grading
Homework
Outline and Schedule

Course Instructor

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

Class Hours

Monday 13:30-14:30 Goodwin 247
Wednesday 12:30-13:30 Goodwin 247
Friday 11:30-12:30 Goodwin 247

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 are powerpoint slides available on-line to supplement this text book.
Bioinformatics Algorithms: An Active Learning Approach is an enhanced electronic textbook developed by the author of the course text. You can access some 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

There will be a new homework assignment almost every week. Open the PDF for the homework due date.
Homework 1.
Homework 2.
Homework 3.
Homework 4.
Homework 5.
Homework 6.
Homework 7.
Homework 8.

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 topics covered this year will be similar to last year, but may differ slightly at times. You can see a fairly detailed record on last year's web page: http://research.cs.queensu.ca/home/daver/471/2016W/
The following table will be updated as the term progresses.

Monday Wednesday Friday
Week 1
Introduction.
January 9
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. Homework 1.
January 11
Finding most frequent k-mers, continued. Review of Big-Ο, Big-Ω, Big-Θ
January 13
Making Change See Section 2.3 of the text.
Week 2
Exhaustive Search. (Chapter 4)
January 16
Be prepared to share your homework solutions in class.
January 18
Restriction Mapping. See section 4.1-4.3 of the text. Homework 2.
January 20
Week 3
Exhaustive Search. (Chapter 4) Greedy Algorithms (Chapter 5)
January 23
Solutions to homework 1. Note: there will be a quiz next week so there will be no homework assigned this week.
January 25
January 27
I will be out of town, so there will be a guest lecture. Details to follow. My trip has been cancelled. I will be here. The guest lecture will occur next Friday February 3.
Week 4
Greedy Algorithms (Chapter 5) and Dynamic Programming Algorithms (Chapter 6)
January 30
Quiz #1, based on homework 1 and 2. Please arrive a bit early so that we can start the quiz at 1:30 sharp. Late comers run the risk of not being admitted into the room. No calculators are permitted for this quiz, or any of the others.
February 1
Homework 3.
February 3
Guest lecture by Qingling Duan.
Week 5
Dynamic Programming Algorithms (Chapter 6)
February 6
Homework 4.
February 8
Making Change, Dynamic Programming Algorithm.
February 10
Edit distance and sequence alignment.
Homework 5. Due March 1.
Week 6
Dynamic Programming Algorithms (Chapter 6)
February 13
Be prepared to share your homework #4 solutions in class. If you want to arrange presenting ahead of time send me an email message, or talk to me after class.
February 15
Global sequence alignment and scoring alignments sections 6.6 and 6.7.
February 17

Reading week
February 20
February 22
February 24
Week 7
Dynamic Programming Sequence Alignment (Chapter 6)
February 27
March 1
Be prepared to share your 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.
March 3
Quiz #2 based on Homework 3,4, and 5. Please arrive a bit early so that we can start the quiz at 11:30 sharp. Late comers run the risk of not being admitted into the room. No calculators are permitted for this quiz, or any of the others.
Week 8
Divide and Conquer (Space efficient Sequence Alignment)
March 6
Homework 6. Due March 13.
March 8
March 10
Week 9
Graph Algorithms
March 13
Homework 7. Due March 20.
March 15
DNA sequencing, Shortest Superstring Problem, Traveling Salesman Problem.
DNA sequencing presentation.
March 17
Week 10
Combinatorial Pattern Matching Suffix Tree
March 20
Homework 8. Due March 27.
March 22
March 24
Week 11
March 27
March 29
March 31
Week 12
April 3
Quiz #3. I will test your knowledge of material that is related to homework 6,7, 8. Please try to arrive early so that you can start the quiz at 1:30 sharp. The duration of the quiz is 50 minutes.
April 5
April 7

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, Jan. 30.
Quiz 2: Monday, Feb. 27 Wednesday March 1 Friday March 3
Quiz 3: Monday, April 3.
Please note the use of a calculator will not be needed and will not be permitted for any of the quizzes. Quizzes will be held in Class.

All components of this course will receive numerical percentage marks.The final grade you receive for the course will be derived by converting your numerical course average to a letter according to Queen's Official Grade Conversion Scale:

Numeric Range Letter Grade GPA
90-100 A+ 4.3
85-89 A 4.0
80-84 A- 3.7
77-79 B+ 3.3
73-76 B 3.0
70-72 B- 2.7
67-69 C+ 2.3
63-66 C 2.0
60-62 C- 1.7
57-59 D+ 1.3
53-56 D 1.0
50-52 D- 0.7
0-49 F 0

Location and Timing of Final Examinations

As noted in Academic Regulation 8.2.1, "the final examination in any class offered in a term or session (including Summer Term) must be written on the campus on which it was taken, at the end of the appropriate term or session at the time scheduled by the Examinations Office." The exam period is listed in the key dates prior to the start of the academic year in the Faculty of Arts and Science Academic Calendar and on the Office of the University Registrar's webpage. A detailed exam schedule for the Fall Term is posted before the Thanksgiving holiday; for the Winter Term it is posted the Friday before Reading Week, and for the Summer Term the window of dates is noted on the Arts and Science Online syllabus prior to the start of the course. Students should delay finalizing any travel plans until after the examination schedule has been posted. Exams will not be moved or deferred to accommodate employment, travel /holiday plans or flight reservations.

Accessibility Statement

Queen's is committed to an inclusive campus community with accessible goods, services, and facilities that respect the dignity and independence of persons with disabilities. This webpage is available in an accessible format or with appropriate communication supports upon request.
Please contact:
The Equity Office
B513 Mackintosh-Corry Hall
Phone: (613) 533-2563
Fax: (613) 533-2031
E-mail: equity@queensu.ca

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.

Accommodation Statement

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 Student Wellness Services (SWS) and register as early as possible. For more information, including important deadlines, please visit the Student Wellness website at: http://www.queensu.ca/studentwellness/accessibility-services/