B363:
Bioinformatics Algorithms
Fall Semester 2017
Lecture : Tuesdays and Thursdays, 9:30a-10:45a, Rm: BH 148
Lab: Fridays, 11:15a-12:30p, Rm: Student Building (SB) 221
Office Hour: Thursdays 1-3:30p or by appointment (Tang, LH 301D);
Mondays 3-5p or by appointment (MohammedIsmail, LH 316)
Instructor: Haixu Tang.
AI: Wazim MohammedIsmail (wazimoha@indiana.edu)
Midterm exam (8th week): 10/12, Thursday, in class
Final exam: 8:30-10a, Tuesday, 12/12, BH 148
Synopsis: In the past few decades, modern biology has become a critical resource of new computational problems inspiring the development of novel algorithmic ideas. A preeminent example is the development of efficient string pattern matching algorithms based on suffix trees and suffix arrays emerging from the comparison of long genomic sequences, which are later applied to other fields such as text searching and mining. The course will introduce the algorithmic ideas used for addressing real-world biological questions, including brute-force search, greedy algorithms, dynamic programming, randomized algorithms, graph algorithms, clustering algorithms and Hidden Markov Models (HMMs), etc. For each algorithmic idea, we will start with an important biological question, such as “Which DNA Patterns Play the Role of Molecular Clocks?” and “How Did Yeast Become a Wine Brewer?”, and then gradually present algorithms to answer this question. In addition to algorithmic ideas, the course will concentrate on the useful intuition to formulate the right algorithmic problem from a biological question. We hope to motivate an algorithmic thinking through the solutions of modern biological problems, which will help to develop problem-solving skills for not only the students interested in bioinformatics, but also the students interested in other fields. The course will offer a lab session, in which the students will practice the implementation of bioinformatics algorithms in C or Java (depending on their previous experience), selected from the Rosalind (http://rosalind.info).
Textbook: :
Bioinformatics Algorithms: an Active Learning Approach, Volume I and II, 2nd Edition, by Phillip Compeau and Pavel Pevzner,
, 2015. The textbook was recently developed for the Massive Open Online Course (MOOC) offered by the authors on Coursera.
Last updated : 8/11/2017
Assignments: We will have 5 take-home
assignments.
Grading: Combined
assignments (15%), Quiz (10%), Lab/programming exercise (20%), One mid-term exam (25%), Final exam (30%).
Office hour: Haixu Tang: R 1-3:30pm, or upon appointment, LH 301D;
Wazim MohammedIsmail (AI): M 3-5pm or upon appointment, LH 316.
Prerequisites: One programming class or equivalent programming experience in C/C++, Java or Python required. No biology background is assumed.
Learning outcomes:
1. Understand basic principles of computational biology and commonly used bioinformatics algorithms;
2. Develop algorithmic thinking to address practical problems through computational formulation;
3. Develop programming skills to implement efficient algorithms to solve computational problems such as biological problems.
Important As your instructor, one of my responsibilities is
to help create a safe learning environment on our campus.
Title IX and our own Sexual Misconduct policy prohibit sexual misconduct.
If you have experienced sexual misconduct, or know someone who has, the University can help.
I encourage you to visit http://stopsexualviolence.iu.edu/ to learn more.
If you are seeking help and would like to speak to someone confidentially,
you can make an appointment with a Mental Health Counselor on campus
(contact information available at http://stopsexualviolence.iu.edu/employee/confidential.html).
It is also important that you know that federal regulations and University policy require me to promptly
convey any information about potential sexual misconduct known to me to our Deputy
Title IX Coordinator or IU’s Title IX Coordinator. In that event, they will
work with a small number of others on campus to ensure that appropriate measures are
taken and resources are made available to the student who may have been harmed.
Protecting a student’s privacy is of utmost concern, and all involved will only share information
with those that need to know to ensure the University can respond and assist.
Writing Tutorial Services (WTS) For free help at any phase of the writing process—from brainstorming to polishing the final draft—call Writing Tutorial Services (WTS, pronounced “wits”) at 812-855-6738 for an appointment. When you visit WTS, you’ll find a tutor who is a sympathetic and helpful reader of your prose. To be assured of an appointment with the tutor who will know most about your class, please call in advance.
WTS, in the new Learning Commons on the first floor of the West Tower of Wells Library, is open Monday-Thursday 10:00 a.m. to 8:00 p.m. and Friday 10:00 a.m. to 5:00 p.m. WTS tutors are also available for walk-in appointments in the Academic Support Centers in Briscoe, Forest, and Teter residence halls, in the Neal-Marshall Black Culture Center, at La Casa, and at the Groups Scholars Program Office in Maxwell. Call WTS or check our Web site for hours.
Labs : A tentative schedule for the lab session will be available here
Preliminary syllabus [This may change!]:
Week
Contents
Lecture
notes
1
Basic molecular biology
2
Algorithm warm-up: where in the genome does DNA start to replicate?
3
Greedy and randomized algorithms: how do we find regulatory patterns in DNA?
4
Graph algorithms: how do we assemble genomes?
5
Brute-force algorithms: how do we sequence antibiotics?
6
Dynamic programming: how do we compare biological sequences?
7
(continue) Dynamic programming: how do we compare biological sequences?
8
Mid-term exam
9
Combinatorial algorithms: are there fragile regions in human genome?
10
Evolutionary tree reconstruction: which animal gives us SARS?
11
(Continue) Evolutionary tree reconstruction: which animal gives us SARS?
12
Clustering algorithms: how did yeast become a wine-maker?
13
Combinatorial pattern matching: how do we locate disease-causing mutations?
14
Hidden Markov Models (HMMs): why have biologists still not developed an HIV vaccine?
15
review
16
Final exam: 8:30-10a, Tuesday, 12/12, BH 148