Lectures in Computational Biology

Computational Biology (426) Spring 1997

A review of computational methods used for the analysis of DNA and protein sequences. The main emphasis will be on algorithms. Some time will be devoted to study of databases and Internet resources available for computational biology research.

Introduction
Sequence Assembly
Sequence Alignment
Protein Folding
Phylogenetic Trees
Molecular Computers

Courses on Internet

BioComputing Hypertext Coursebook
Algorithms for molecular biology - Course at Univ. of Tel Aviv, Ron Shamir and Dalit Naor 1994 1995 1999
Algorithms in Melecular Biology, R. Karp et al., Univ. of Washington 1996 1998
Computational Biology, Univ. of New Mexico, Sorin Istrail
Representations and Algorithms for Computational Molecular Biology Koza and Altman, Stanford Univ.
Computational Biology - Course at Princeton, R. Lipton
USC Center for Computational Biology
Computational Biology Course
MIT Computational Biology - Bonnie Berger and Mona Singh 1998
Princeton - Computational Biology - Mona Singh 1999
Stanford - Representations and Algorithms for Computational Molecular Biology - Altman 1999
Stanford - Computational Molecular Biology - Brutlag and Kozar 1998

Some relevant links

Some general references

M.S. Waterman, Introduction to Computational Biology, Chapman and Hall, London, 1995.
P.A. Pevzner and M.S. Waterman, Open combinatorial problems in computational molecular biology, Proc. 3rd Israel Symp. Theory of Comput. and Systems (1995).
D. Sankoff and J.B. Kruskal (eds.), Time warps, string edits, and macromolecules: the theory and practice of sequence comparison, Addison-Wesley (1983).
F.B. Rudolph and L.V. McIntire (eds.) Biotechnology

Participants

Brian Ancher Madsen (BM)
Kristian de Lichtenberg (K) morat@diku.dk
Carsten Jørgensen (CJ) cape@diku.dk
Christan Tønsberg Jensen (CTJ) smash@diku.dk
Hans Henrik Staerfeldt (HHS), bombman@diku.dk, hhs@cbs.dtu.dk
Jacob Lavemøller (JL)
Henrik Thorndal Poulsen (HP)
Lars Kaae (LK) lkaae@diku.dk
Thomas Andersen (TA) thomasa@diku.dk
Ba Trung Do (BTD)
Jens Damgaard Andersen (JDA) jda@diku.dk
Pawel Winter (PW) pawel@diku.dk

Seminars (tentative)

	Date	Subject	By	Main References	Software
1	6/2/97	Introduction Overview Assignment of topics	PW	Introduction to Biocomputing Primer on Molecular Genetics Networking
2	13/2/97	Pairwise sequence alignment Global alignment - dynamic programming algorithm Local alignment and similarity Heuristics	LK	Giegerich and Wheeler Barton	BLAST FASTA BCM
3	20/2/97	Multiple sequence alignment Dynamic programming Carrillo-Lipman method Heuristics	PW	Fuellen	MSA, GKS-95 CLUSTALW 3D Visualization
4	27/2/97	Sequence Assembly Shortest superstring Hybridization	PW	Blum et al.	DNA-SPECTRUM
5	6/3/97	Physical Mapping PQ-trees Interval graphs	CTJ+CJ	Alizadeh et al.
6	13/3/97	Restriction Maps Double digest problem Uncertainty	PW	Pevzner	Double Digester
7	20/3/97	Sorting by reversals Exact algorithms Approximations	K+HHS	Kececioglu and Sankoff
	27/3/97	No Seminar
8	3/4/97	Protein Folding Hydrophobic-hydrophilic model	JDA	Hart and Istrail
9	10/4/97	Protein Folding Genetic algorithm	K+HHS	Schultze-Kremer Khimasia
10	17/4/97	Phylogenetic Trees Perfect phylogenies	HP+JL	Agarwala and Fernandez-Baca Applets	Tree of Life Visualization
11	24/4/97	Phylogenetic Trees Distance-based methods	TA	Farach et al.	Phylip
	1/5/97	No Seminar
	8/5/97	No Seminar
12	15/5/97	Molecular Computers	BM+BTD	Adleman Friedman
13	22/5/97	Evaluation	PW

Main References

R. Agarwala and D. Fernandez-Baca, A polynomial-time algorithm for the perfect phylogeny problem when the number of character states is fixed, Proc. of the 34-th Symp. on the Foundations of Computer Science (1993) 140-147. [10]
F. Alizadeh, R.M. Karp, L.A Newberg and D.K. Weisser, Physical mapping of chromosomes: A combinatorial problem in molecular biology, Algorithmica 13 (1995) 52-76. [5]
A. Blum, T. Jiang, M. Li, J. Tromp and M. Yannakakis, Linear approximation of shortest superstrings, Proc. of the 23-th Ann. ACM Symp. on Theory of Computing (1991) 328-336. [4]
M. Farach, S. Kannan and T. Warnow, A robust model for finding optimal evolutionary trees, Algorithmica 13 (1995) 155-179. [11]
W.E. Hart and S. Istrail, Fast protein Folding in the hydrophobic-hydrophylic model within 3/8 of optimal (extended abstract) Proc. of the 27-th Ann. ACM Symp. on Theory of Computing (1995) 157-168. [8]
J. Kececioglu and D. Sankoff, Exact and approximation algorithms for sorting by reversals, with application to genome rearrangement, Algorithmica 13 (1995) 180-210. [7]
P.A. Pevzner, DNA physical mapping and alternating Eulerian cycles in colored graphs, Algorithmica 13 (1995) 77-105. [6]

pawel@diku.dk