85301 - Algorithms and Data Structures in Biology

Academic Year 2019/2020

  • Docente: Ugo Dal Lago
  • Credits: 6
  • SSD: INF/01
  • Language: English
  • Moduli: Ugo Dal Lago (Modulo 1) Ugo Dal Lago (Modulo 2)
  • Teaching Mode: Traditional lectures (Modulo 1) Traditional lectures (Modulo 2)
  • Campus: Bologna
  • Corso: First cycle degree programme (L) in Genomics (cod. 9211)

Learning outcomes

By the end of the course, the student his familiar with the design and analysis of correct and efficient algorithms and data structures. In particular, the student has basic knowledge of algorithms and data structures. The student is able to design correct and efficient algorithms for common computational tasks in biology and to analyse existing algorithms and data structures.

Course contents

  • The concept of an Algorithm and the computational complexity of it: definition, recursion and iteration, asymptotic notation, design techniques.
  • Exhaustive Search: restriction mapping, motif finding.
  • Greedy Algorithms: reversal sorting, approximate algorithms.
  • Dynamic Programming: edit distance, Manhattan distance.
  • Divide and Conquer.
  • Graph Algorithms.
  • Pattern Matching.

Readings/Bibliography

Neil C. Jones and Pavel A. Pevzner. An Introduction to Bioinformatics Algorithms. MIT Press, 2004.

Teaching methods

Class Lectures.

Assessment methods

The exam consists in a sequence of exercises by which the teacher can verify that the student has acquired the an ability in designing efficient algorithm. Moreover, basic theoretical knowledge will also be tested.

Links to further information

http://www.cs.unibo.it/~dallago/ADSB1920

Office hours

See the website of Ugo Dal Lago