Logo Dipartimento di Informatica Sistemistica e Comunicazione - Università degli Studi di Milano - Bicocca

Department of Informatics, Systems and Communications

Algorithms in Computational Biology  - spring 06


Instructor: Paola Bonizzoni
Language:Italian
Schedule: Mon (9.30:11.30), Fri (14.30:17.30)
from April 28 to the end of May
Place: Sala Riunioni

Communication

You can   send your questions by email to
           bonizzoni@disco.unimib.it
There is a mailing list: dottorandixxi@disco.unimib.it. The main purpose of the list is for the instructors to make announcements, but it can also be used as a forum of discussion.

Course overview

The course is an introduction to basic algorithmic techniques used in Computational Biology to face NP-hard optimization problems. Topics
in Computational Biology  of  interest  for Computer Scientists  are 
presented  in the course.  A first goal of the course is to introduce  approximation algorithms for NP-hard optimization problems.
Techniques to be covered include greedy algorithms, randomized rounding, smooth-polynomial programming and primal-dual scheme.

Reading material and references

Books

Online lecture notes

References

Papers
  • (see list below)


Course contents

  • Introduction to approximation algorithms
  • combinatorial approximation: set cover, metric steiner tree, TSP and shortest superstring
  • Linear Programming based approximation algorithms: LP duality, primal-dual scheme and LP rounding
  • application  of LP approximation in Computational Biology: gene networks
  • combinatorial PTAS and via smooth polynomial programming:  PTAS  for tree-alignment and PTAS for  consensus  clustering
  • Hardness of approximation
  • Optimization problems in Computational Biology 


Seminars

April 6 Predicting Orthologous genes via Genome Rearrangement
Tao Jiang University of California at Riverside (USA)   (abstract)

Papers

  • A. Blum, T. Jiang, M. Li, J. Tromp and M. Yannakakis, Linear approximation of shortest superstrings, Proc. of the 23-th Ann. ACM Symp. on Theory of Computing (1991) 328-336. 
  • T Chen, V Filkov, and SS Skiena. Identifying Gene Regulatory Networks from Experimental Data. In RECOMB99:, pp 94-103. ACM, 1999
  • Ming Li, Bin Ma, Lusheng Wang. Near optimal alignment within a band in polynomial time. In Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing (STOC), pp. 425-434, Portland, Oregon, May 21-23 2000. Association for Computing Machinery,
  • Jonathan Badger, Paul Kearney, Ming Li, John Tsang, Tao Jiang. Selecting the branches for an evolutionary tree: a polynomial time approximation scheme. Journal of Algorithms, 51(1):1--14. 2004.
  • G. Robins and A. Zelikovsky, "Tighter Bounds for Graph Steiner Tree Approximation," SIAM Journal on Discrete Mathematics, 19(1), March 2005, pp. 122-134.
  • Mathieu Blanchette, Benno Schwikowski, Martin Tompa: Algorithms for Phylogenetic Footprinting. Journal of Computational Biology 9(2): 211-223 (2002)