DM813: Algorithms for Biological Sequence Analysis (5 ECTS)

STADS: 15005201

Level
Master's level course approved as PhD course

Teaching period
The course is offered in the autumn semester.
Offered according to needs.

Teacher responsible
Email: daniel@imada.sdu.dk

Timetable
Show entire timetable
Show personal time table for this course.

Comment:
Ubegrænset deltagerantal. 2. kvartal.

Prerequisites:
None

Academic preconditions:
The contents of DM507 Algorithms and Datastructures and ST501 Science Statistics must be known.

Course introduction
To give a thorough understanding of the theory and computational techniques behind the most important algorithms in bioinformatics. The course is highly relevant for students who wish to write their Master or Ph.D. thesis within the area of bioinformatics.

Expected learning outcome
At the end of the course the student will be able to:
- use dynamic programming for pairwise alignment of DNA and protein sequences
- describe the BLAST and FASTA algorithms in short
- explain in short how the BLOSUM and PAM matrices are constructed
- construct and use simple HMMs for multiple alignment of DNA and protein sequences
- implement other simple algorithms for multiple alignment, e.g., using a guide tree
- describe strengths and weaknesses of the different kinds of alignment methods
- implement simple algorithms for constructing evolutionary trees, e.g., neighbor joining, UPGMA, and parsimony, and describe their strengths and weaknesses
- describe how to use dynamic programming to infer coevolutionary history of groups of species.
- implement a suffix tree and describe some of its applications
- compute the probability of a given evolutionary tree, based on simple probabilistic models of evolution.
- describe how combinational methods are used to reconstruct putative rearrangement scenarios in order to explain the evolutionary history of a set of species
- implement a Metropolis algorithm for evolutionary trees - implement Gibbs sampling
- describe the basic principles of the most common methods for protein structure prediction
- implement a simple algorithm for RNA structure prediction

Subject overview
- A short introduction to the relevant parts of biology
- Sequence alignment
- Evolutionary trees
- Coevolution
- Genome Rearrangements
- Protein structure
- Hidden Markov Models

Literature

Meddeles ved kursets start.

Website
This course uses e-learn (blackboard).

Prerequisites for participating in the exam
None

Assessment and marking:
(a) Oral examination, Danish 7 mark scale, external examiner. In this course the student elaborate a project, which has to be defended at an oral examination. A single grade is given for both the project and the oral examinatíon.

Reexamination will appear from the curriculum.

Expected working hours
The teaching method is based on three phase model.

Forelæsninger: 21 timer
Educational activities

Language
This course is taught in Danish or English, depending on the lecturer. However, if international students participate, the teaching language will always be English.

Course enrollment
See deadline of enrolment.

Tuition fees for single courses
See fees for single courses.