Latest update: 21.05.04
Computational Biology, Spring 2004 

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.

Book: J. Setubal and J. Meidanis, Introduction to Computational Molecular Biology, PWS 1997. Ganske ligetil introduktion til emnet. Vil blive suppleret med artikler og kapitler fra andre bøger.


Time and Place
Wednesdays, 10.15-12.00 in N034 at DIKU

Presentations, Onsdag den 26. maj, kl. 10.15 in N034

Lecturers
David Pisinger
Martin Zachariasen
Pawel Winter (kursusansvarlig)


Lectures and Seminars (tentative)

Date
 		Subject
 		Lecturer
 		Main Reference
S+M = Setubal and Maidanis
 		Other  References/Transparencies
 		Homework
 		Projektemner
4/2
 Introduction
Sequence Alignment
  • Pairwise Alignment (PA)
  • Global Alignment
  • Local Alignment
  • Semiglobal Alignment
  • Gap Penalty Models
 PW
 Chapter 1, S+M
Chapter 3, S+M
 Introduction
Pairwise alignment
 Enten opgave 3.9 fra bogen eller implementer i C++ pairwise alignment som kræver lineær plads.
Aflevering: 18/2, udsat til 25/2
11/2
 Sequence Alignment and Phylogentic Trees
  • Multiple Sequence Alignment (MSA)
  • Generalized Tree Alignment (GTA)
 MZ
SL
 Chapter 3, S+M
article: Jiang & Wang "Algorithmic Methods for MSA"
article: Schwikowski & Vingron "Weighted Sequence Graphs"
 plancher - Martin
plancher - Stinus
 1. Perform experiments with the MSA algorithms on the web-page:  http://searchlauncher.bcm.tmc.edu/multi-align/multi-align.html

Use at least 2 different algorithms on 2 different input sequence
sets. Give a short introduction to the algorithms used and comment their output. Examples of input sequence are given on: http://www.people.virginia.edu/~wrp/cshl99/smith_ex.html

2. Give your own description of the uniformly lifted tree algorithm for tree alignment which is described in Section 2 in:

L. Wang, D. Gusfield, Improved Approximation Algorithms for Tree Alignment, Journal of Algorithms 25, 255-273, 1997. http://dx.doi.org/10.1006/jagm.1997.0882

Deadline: February 25.
18/2
 Phylogenetic Trees
  • Character-Based Methods
  • Distance-Based Methods
  • Quartet-Based Methods
 PW
 Chapter 6, S+M
6.5, 6.9, 6.14
Aflevering: 3/3
  1. Quartets
  2. Suboptimal/efficient  distance-based methods
25/2
 Sequence Assembly
  • Shortest Superstring
 PW
 Chapter 4, S+M
article
 plancher
artikel

3/3
 Physical Mapping (PM)
  • Restriction site mapping
  • Hybridization mapping
 PW
 Chapter 5, S+M
5.2, 5.14, 5.16
Aflevering: 17/3
10/3
 Sorting by Reversals
 PW
 Chapter 7, S+M
 plancher
 7.3, 7.4, 7.5, 7.6, 7.8, 7.13
Aflevering: 24/3
17/3
 Protein Folding (PF)
  • General Introduction
  • Lattice Models
 MZ
BP+ESF
 Chapter 8, S+M
 plancher

24/3
 Approximate String Matching
 DP
 article: Wu, Manber & Myers
 slides
 opgave
31/3
 Project Assignment
 all





Projects

Any of the topics covered in the lectures can be selected as a projects. Projects can be of various type. For example survey, implementation of algorithm(s), application to real-life problem, tutorial to www-resources related to the selected topic.

There are many topics not covered in the lectures. Projects can of course address any of such topics. Examples include:

Protein Secondary Structure (PSS)
DNA Compters 
Students
Name
 4/2
 11/2
 18/2
 25/2
 3/3
 10/3
 17/3
 24/3
Morten Bjerre



x


Rune Funch Søltoft
 x






Poul Johsnnis Clementsen
 x
 x
 x




Emil Støvring
 x






Kenneth Lyneborg Hvam
 x-A
x-G-90%
 x
 x-G-90%
 x
 x
Emil Soelberg Frisendal
 E
 G-80%
 G-60%
 x
 x
 x
 x
 x
Andre Lindskov Andersen
x





Sune Jens B. Christensen
 x-A
 x-G-80%
 x-G-50%
 x
 x-G-50%
 x
 x
 x
Anders Erik Petersen
 x
x
 x



Peter Krogh
 x
 x
 x
 x/2
 x
x
 x
Magdalena Maria Otap
x
 x
 x
 x
 x

Mathias Bertelsen
 x-E
 x
 G-80%
G-60%
 x-A
 x
 x-G
Nynne Nylander
 x






Mads Hvelplund
 x-E
 x
 x




Lone Marner
 x-A
 x-G-100%
 x-G-100%
 x
 x-G-60%
 x-A
 x
 x-G
Per Munk Jacobsen
 A
 x-G-100%
 x-G-100%
 x
 x-G-75%
 x-A
 x
 x-G