Subject: Course Announcement: Algorithms in Molec. BIo.

From: Richard Karp <[email-masked]>
Date: Fri, 23 Dec 94 9:56:02 PST

COURSE  ANNOUNCEMENT (SPRING, 1995)
              CS 294-3  Algorithms in Molecular Biology
              
          Time: Tuesday and Thursday, 12:30-2:00
          Location: 310 Soda
          Prerequisites: Introductory courses in algorithms and probability,
          or consent of instructor. Background in biology is helpful but not
          required.
          Units: 3
          
   The chromosomal DNA in the cells of living organisms contains the 
hereditary information that they pass on to their offspring and serves 
as an insruction manual for the production of proteins that control the
chemical processes of the cell. Recent developments in biotechnology open
the possibility of acquiring vast volumes of DNA and protein sequence 
data. This data will be a powerful tool for understanding our evolutionary
history, identifying genes and diagnosing genetic diseases. This course is
concerned with the challenges for algorithm designers that are posed by
the problems of acquiring and interpreting such data. 

The principal topics in the course will be:
(1) Essential background from genetics, molecular biology and biotechnology.
(2) Searching for similarities among strings: exact and approximate matches,
 parametric sequence comparison, genome rearrangements and inversion distance,
 multiple alignments.
(3) Physical mapping based on sequence tagged sites or multiple complete
 digests; partial digest and multiple digest problems; applications of 
 interval graphs and the consecutive ones property.
(4) Genetic mapping.
(5) Sequence assembly and the shortest superstring problem; sequencing
 by hybridization.
(6) Construction of evolutionary trees.
(7) Identification of coding and promoter regions in DNA.