Tel Aviv University School of Computer Science

Fall 2002-2003

Computational Genomics


Benny Chor  and  Amos Tanay

Mondays 10:00-13:00, Dan David 106

Contact Info:
    Email Phone Office Office Hours
Instructor Prof. Benny Chor 640-5977 Schreiber  223 By  e-appointment 
Teaching Assistant and Solicitor 
     (J & A Tanai, Q.C.s)

Adv. Amos Tanay


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.


The course is opened to 3rd year and M.Sc. Computer Science students. Students from other disciplines are encouraged to contact the instructor or teaching assistant. A background in algorithms, probability, and programming is required.

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

  Introduction and administrativia  
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)
            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 Assigned Projects

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

General Submission Guidelines

         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.



Biology Background Books


Other On-line Courses

Orthogonal Bonus Points ( unrelated to problem sets or official golden stars)

Other Interesting On-line Resources