69443 - Algorithms and Data Structures for Computational Biology

Learning outcomes

At the end of the course, the student has the basic Knoledge in design and analysis of correct and efficient algorithms and data structures. In particular, the student has basic knowledge on algorithms and data structures. The student will be able to: design correct and efficient algorithm for common computational tasks; analyze existing algorithms and data structures; design and analyze new algorithms and data structures.

Course contents

Algorithm design: incremental algorithm design, divide-and-conquer algorithm design, greedy algorithm design, dynamic programming algorithm design

Algorithm analysis: runtime analysis, asymptotic behaviour of algorithms, functions in asymptotic analysis, solving recurrence equations for runtime analysis of recursive algorithms

Sorting algorithms: insertion sort, merge sort, quick sort, lower bounds of comparison based sorting, sorting in linear time, counting sort and radix sort

Data structures: array, decision tree, binary tree, stack, queue, linked list, rooted tree as linked list, hash table, graphs, merge-find sets, suffix tries, trees and arrays, Burrows-Wheeler transform

Trees and graphs algorithms: visits, Kruskal's algorithm for the minimum spanning tree problem

String algorithms: exact and approximate string matching, global sequence alignment, local sequence alignment, semiglobal sequence alignment

Algorithms for NP-complete problems: brute force algorithms, approximation algorithms, branch-&-bound, heuristics (based on greedy / local search), examples for the traveling salesperson problem

Readings/Bibliography

It is fundamental to use the electronic slides and material provided during the classes, including live exercises. The slides will be made available on the course web page.

The readings below are suggested, but need not to be necessarily purchased.

Books more specific on computational biology topics:

- Carlos Setubal, Joao Meidanis, Introduction to computational molecular biology, Cengage Learning eds., 1997;
- C. Gibas, P. Jambeck, Developing Bioinformatics Computer Skills, O'Reilly media, 2001

Books more general on computer algorithms and data structures topics:

- Alfred V. Aho, Jeffrey D. Ullman, John E. Hopcroft. Data Structures and Algorithms. Addison Wesley, 1983.
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms. McGraw-Hill, 2001.
- Donald E. Knuth. The Art of Computer Programming, Volumes 1-3. Addison-Wesley Professional, 1998.
- S.B. Kishor Data Structures, Edition 3. Das Ganu Prakashan, Nagpur, 2008.

Teaching methods

The teaching methods consist of frontal lectures (supported by slides and whiteboard) and the discussion of exercises to be solved on the paper, using the student laptops or the whiteboard.

Assessment methods

The final exam is composed of a written part (3 hours) and possibly an oral part (30 minutes). During the written part, it is NOT allowed the use of books and notes. The teacher may require a further orals exam if the student’s score in the written part is close to 18/30.

Teaching tools

Electronic slides and projector.
Personal computer.
White board.

Office hours

See the website of Pietro Di Lena