Computer Laboratory

Course pages 2014–15


Principal lecturer: Dr Pietro Lio
Taken by: Part II
Past exam questions
Information for supervisors (contact lecturer for access permission)

No. of lectures: 12
Suggested hours of supervisions: 3


This course focuses on algorithms used in Bioinformatics and System Biology. Most of the algorithms are general and can be applied in other fields on multidimensional and noisy data. All the necessary biological terms and concepts useful for the course and the examination will be given in the lectures. The most important software implementing the described algorithms will be demonstrated.


  • Introduction to biological data: Bioinformatics as an interesting field in computer science.

  • Dynamic programming. Longest common subsequence, DNA, RNA, protein structure alignment, linear space alignment, heuristics for multiple alignment.

  • Sequence database search. Blast, Patternhunter.

  • Next Generation Sequencing. De Bruijn graph, Burrows–Wheeler transform.

  • Phylogeny - parsimony-based. Fitch, Wagner, Sankoff parsimony.

  • Phylogeny - distance-based. UPGMA, Neighbour Joining.

  • Clustering. K-means, Markov Clustering algorithm.

  • Applications of Hidden Markov Models.

  • Searching motifs in sequence alignment. Gibbs sampling.

  • Biological networks: reverse engineering algorithms and dynamics; Wagner, Gillespie.


At the end of this course students should

  • understand Bioinformatics terminology;

  • have mastered the most important algorithms in the field;

  • be able to work with bioinformaticians and biologists;

  • be able to find data and literature in repositories.

Recommended reading

* Durbin, R., Eddy, S., Krough, A. & Mitchison, G. (1998). Biological sequence analysis: probabilistic models of proteins and nucleic acids. Cambridge University Press.
Jones, N.C. & Pevzner, P.A. (2004). An introduction to bioinformatics algorithms. MIT Press.
Felsenstein, J. (2003). Inferring phylogenies. Sinauer Associates.