Contact Info:
 

		Email	Phone	Office	Office Hours
Instructor	Prof. Benny Chor	benny@cs.tau.ac.il	640-5977	Schreiber  223	By  e-appointment
Teaching Assistant and Solicitor       (J & A Tanai, Q.C.s)	Adv. Amos Tanay	amos@post.tau.ac.il	640-5394	Schreiber  011	By  e-appointment

 
 
 

Course Outline

The Human Genome Project has completed the sequencing of over 95 % of human DNA.  Other genome projects of various organisms (bacteria, fungi, worms, rice, wheat, flies, mice and primates) are either completed or in the process of advanced sequencing.  New bio-technologies produce huge amounts of biological data, whose manual analysis is not possible.  These advances have pushed for a new scientific discipline of bioinformatics, which integrates computer science, statistics, mathematics, and various biological fields.  In this  introductory course we concentrate on the algorithmic aspects of various computational tasks with biological origins.

Prerequisites

Course Plan (Tentative Schedule, Revised Dec. 2, 2002):
 
 

 
 

Lecture ___________	Date ______	Subject      ______________________________________	Reference(s)  __________________
1	14/10/02	Introduction and administrativia
2	21/10	Pairwise Sequence Alignment: Dynamic programming; Global Alignment.	Kanehisa, ch. 3  Speed's ppt slides
3	28/10	Pairwise Sequence Alignment: Local Alignment; Affine gap penalties; Linear space algorithm.	Gusfield, ch. 11
4	4/11	FASTA and BLAST heuristics; Cost matrices for amino acid substitutions: PAM and BLOSSUM. Multiple sequence alignment.	Gusfield, ch. 15  Speed's ppt slide
5	11/11	Multiple sequence alignment: Approximation algorithm; Heuristics in practical use.	Kanehisa, ch. 3, p. 79-80  Gusfield, ch. 14
6	18/11	Suffix trees. Pluto's Introduction to Machine Learning.	Dan Geiger slides (pdf) Schàlkopf-Smola,1.1,1.2
7	25/11	Machine learning: Kernels, and Support Vector Machines. Suffix Trees & SVM: Applications to protein classification.	Christina Leslie slides (ppt) String Kernel Papers:1,2
8	2/12	Hidden Markov Models: Basics. (ppt)   Hanuka Special: Levitation without Meditation	Rabiner's Tutorial R. Durbin et al. , ch. 3
9	9/12	Hidden Markov Models: Bioinfo applications.	R. Durbin et al. , ch. 4
10	16/12	An overview of the human genome project in general and various mapping techniques in particular.	Comparative Genomics
11	23/12	DNA Chips and Tools for Gene Expression Analysis.   Lecturer: Adv. Amos Tanai (J & A Tanai, Q.C.s)
12	30/12	Radiation Hybrid (RH) mapping	RHO  (Ben-Dor et. al.)
13	6/1/03	Constructing phylogenetic (evolutionary) trees: One hour introduction by Herr Prof. Dr. Dr. Hc. Dan Graur (aka Grand number 5 of the orthogonal bonus points session);  Character based  methods:  Maximum Parsimony and maximum likelihood.	Predicting the evolution of Human Influenza A virus: Walter Fitch's 1999 invitational lecture.
14	13/1	Three guest lectures, followed by brunch. 1) Dr. Dena Leshkowitz. 2) Prof. Nathan Nelson. 3) Prof. Michal Linial.

Projects  (Updated Dec. 7)

List of Projects (back by popular demand)

Schedules of meetings with the course staff to discuss your project's targets and general
design approach for the week of Dec. 10 to Dec. 12 will be discussed during Dec. 9 class.

Important: Project presentations deadline are on the 23/2. Please coordinate a meeting with the course staf. You are encouraged to
finish and present you projects beforehand, starting at the 5/2.

Problem Sets

         Problem set 1

         Problem Set 2

         Problem Set 3

        (It is now official: There will not be any Problem Set 4-5-6 and we are still considering regarding 7.)
 

IMPORANT:  Problem set 3 deadline is extented to the 23/2.

Administrativia

• Grade:  Based on five problem sets (55-65% of total grade ) and a project (35-45% ).

 

 
 
 
 
 
 
 

Homework submission in singles or pairs (no triplets, quartets, quintets etc.). There will be a total of 5 problem sets, involving both "dry" assignments and "wet" ones. The wet parts will require understanding and running existing software, but not writing any code. Homework should be done independently. External sources (books, journal articles, web pages) can be used but should be clearly quoted.

The project will involve coding a fairly large program,  testing it on simulated and actual biological data, and analyzing the results. The project specification will be given on November 3rd. Each group will prepare a two page written summary of its intended project and submit it no later than December 2nd. During the week of December 2nd to 9th the course staff will hold short interviews with each group. A written report, accompanied with the working software, is due on January 5, 2003.
 

Books

• Biological Sequence Analysis, R. Durbin et al. , Cambridge University Press, 1998.
• Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology, D. Gusfield, Cambridge University Press, 1997.
• Post-genome Informatics, M. Kanehisa , Oxford University Press, 2000.
• Introduction to Computational Molecular Biology, J. Meidanis and J. Setubal, Brooks/Cole Pub Co., 1997.
• Computational Molecular Biology : An Algorithmic Approach, P. Pevzner, MIT Press, 2000.
•  Learning with Kernels: Support Vector Machines, Regularization, Optimization and Beyond, Bernhard Schölkopf and Alex Smola, MIT Press, 2002.    Available on-line: Preface, Section 1.1, Section 1.2, and more.

Biology Background Books

• The Cartoon Guide to Genetics, by Larry Gonick and Mark Wheelis, Harper Perennial, 1991 (I have not read this book, but I was told it is gives a good popular overview. Some students complained the book spends way too much time before getting down to relevant business).

Ron Shamir course notes: Algorithms in Molecular Biology, Tel-Aviv University Fall 2001/2
Martin Tompa's course notes: Computational Biology, (CSE 527), University of Washington, Seattle, Winter 2000.
Nir Friedman's course slides: Computational Molecular Biology the Hebrew University, Jerusalem, Fall 1999.
Karp, Ruzzo and Tompa's course notes: Algorithms in Molecular Biology University of Washington, Seattle, Winter 1998.

•      Name 1  for pointing out to the lecturer that 2003 is not the same as 2002.
•      Name 2  for solving problem set I in class.
•      Names 3 & 4 for providing the first HMM presentation, lecture 8. Superb presentation, despite its software origin.
•      Grand Name 5 (a more realistic half picture) for offering some new golden star problems (unfortunately, the

                                                     best ones were censored by the committee for campus ethics &  safety )
•      Beware everybody. More names are on their way (and your check is in the mail...)

Other Interesting On-line Resources
 

•     Mother Jones: Alternative views on some world affairs