Computational Biology - spring 06
- Instructor: Paola
- Schedule: Mon (9.30:11.30), Fri (14.30:17.30)
- from April 28 to the end of May
- Place: Sala Riunioni
- You can send your questions by email to
- There is a mailing list: email@example.com.
The main purpose of the list is for the instructors to make
announcements, but it can also be used as a forum of discussion.
- The course is an introduction to basic algorithmic techniques
used in Computational Biology to face NP-hard optimization problems.
- 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.
- Vijay V. Vazirani, Approximation Algorithms, Springer, 2002
- Michael R. Garey and David S. Johnson, Computers and Intractability, Freeman, 1979
- Online lecture notes
- Michael X. Goemans, Approximation Algorithms
- Rejeev Motwani, Lecture Notes on Approximation Algorithms - Volume I
- (see list below)
- 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:
- combinatorial PTAS and via smooth polynomial programming: PTAS for tree-alignment and PTAS for consensus clustering
- Hardness of approximation
- Optimization problems in Computational Biology
- 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.
Benno Schwikowski, Martin Tompa: Algorithms for Phylogenetic
Journal of Computational Biology 9(2): 211-223 (2002)
Reading material and references
SeminarsApril 6 Predicting Orthologous genes via Genome Rearrangement
Tao Jiang University of California at Riverside (USA) (abstract)