SEMINAR MUSMACHIM: A sampling of algorithms in computational biology.
Lecturer :
Class Hours
HOMEWORK DUE: June 11 at class. NO EXTENSIONS!!
General :
The course will include both lectures given by me and lectures
given by the students. The first and last lectures will be given
by me.
Each student will select one or two items (depending on the number
of students) from the list of topics given below. Each student
will be required to prepare his/her lecture in coordination with
me. Each lecture will focus on a particular
algorithm applied to solve a current problem in biology.
The student will be required to present the algorithmic aspects
of the problem in a context understandable to students with no
biological background. However, the particular application to
biology will also be described (in coordination with me).
There will be two or three compulsory easy programming assignments,
which will allow the students to taste a little of the "flavor" of
these problems.
Attendance to all lectures is compulsory.
List of topics to choose from:
This list contains various algorithms for pattern matching, alignment
and prediction in one, two and three dimensions applied to various aspects
of proteins.
Due to many holidays, this semester we will have only 10 lectures.
- March 19: Introduction to Molecular Biology (DF).
- March 26, April 2:Some String Matching Algorithms (Olga).
- April 23, May 7: Dynamic Programming for sequence comparison (Aharon).
- May 14: Fast heuristic string matching: BLAST and FASTA series (Tzirlin A).
- May 21: Neural Networks for secondary structure prediction (Kreizlman A).
- May 28: Genetic Algorithms for ab-initio folding (A. Malamud).
- June 4, June 11: Geometric Hashing for structural comparison of proteins and docking (Boaz).
- Hidden Markov Models for sequence comparison.
- Threading or Fold Assignment.
- Double dynamic programming for structural comparison and threading.
- Bioinformatics, genomes, structural biology and evolution (DF).
MORE DETAILS ABOUT EACH TOPIC
- Introduction to Molecular Biology (DF).
- DNA, genes, proteins: sequence, structure and function.
- Some of the most important current computational problems in biology.
- Some String Matching Algorithms.
- Chapter 34 from "Algorithms" by Cormen et al.
- Dynamic Programming for sequence comparison.
- Chapter 11 from "Algorithms on Strings, Trees, and Sequences" by Gusfield plus supplementary material.
- One or two programming assignments will be given to implement
and taste this algorithm.
- Fast heuristic string matching: BLAST and FASTA series.
- Possible references: Altschul et al, Gapped BLAST, NAR 25, 3389, 1997.
- NP-completeness of the protein folding problem.
- Possible references: Unger & Moult, 1993: Bull. Math. Biology 55(6):1183; Fraenkel's proofs.
- Genetic Algorithms for ab-initio folding.
- Possible references:
Sun, 1993: Prot. Sci. 2:762-785;
Bowie & Eisenberg, 1991:
- Hidden Markov Models for sequence comparison.
- Krogh, ..., Haussler,
JMB, Hidden Markov models in computational biology: Applications to protein modeling, 235, 1501-1531, 1994
- Neural Networks for secondary structure prediction.
- Rost & Sander, Prediction of protein secondary structure at better than 70% accuracy,
JMB, 232, 584-599, 1993.
- Threading: 3D Structure prediction from sequence using sequence-structure compatibility.
- Geometric Hashing for structural comparison of proteins and docking.
- Other algorithms for structural comparison and threading.
- Genomes, evolution, structural biology and the future of bioinformatics (DF).
- What has been found after the first dozen organisms have already been fully
sequenced.
- What have we learned.
- What remains to be interpreted from these genomes.
- Main directions for future research in bioinformatics/computational biology
to aid in the interpretion of genomes.
A FEW GENERAL REFERENCES: