Computational Complexity in Biology

Course Contents (Syllabus):

Introduction to Algorithms and Complexity. Design and Analysis Techniques: Greedy, Divide and Conquer, Dynamic Programming. Graph Algorithms: Depth First Search, Breadth First Search, Minimum Spanning Tree, Shortest Paths. Sorting Algorithms. Polynomial Complexity and NP-hard problems. Decision problems. Combinatorial Optimization. Complexity Classes P and NP. NP-complete problems and Polynomial Reductions. The Protein Folding problem in the Hydrophobic-Polar model and the Levinthal’s paradox (NP-hardness results and approximation algorithms). The Longest Common Subsequence problem (known algorithms and hardness in P).

Post-graduate course. 

Prerequisites and/or related courses: 

Discrete Mathematics, Algorithms and Complexity, Graph Theory, Theory of Computation, Computational Biology

Bibliography:

- Introduction to Algorithms, T. Cormen, C. Leiserson, R. Rivest, C. Stein, Panepistimiakes Ekdosis Kritis, 2012  (in Greek).

- Algorithm Design, J. Kleinberg, E. Tardos, Ekdosis Klidarithmos EPE, 2009 (in Greek)

- Algorithms, S. Dasgupta, C. Papadimitriou, U. Vazirani, Ekdosis Klidarithmos EPE, 2009 (in Greek)

- Algorithms and Complexity, E. Zachos, Notes, National Technical University of Athens, 2007 (in Greek).

- Algorithms, P. Bozanis, Ekdosis A. Tziola and Sons A. E., 2006 (in Greek).

- Design and Analysis of Algorithms, L. Anany, Ekdosis A. Tziola and Sons A. E., 2008 (in Greek).

- The design and Analysis of Computer Algorithms, A. Aho, J. Hopcroft, J. Ullman. Addison-Wesley Publishing Company, 1974.

- Computers and Intractability: A Guide to the Theory of NP-Completeness, M. Garey, D. Johnson. W. H. Freeman and Company, 1979

Graph Theory, A. Papaioannou, Notes, National Technical University of Athens, 2010 (in Greek).

- Graph Theory and Algorithms, I. Manolopoulos, A. Papadopoulos, K. Tsichlas, Ekdosis Neon Technologion Mon. EPE, 2013  (in Greek).

- Introduction to Graphs, L. Kirousis, X. Mpouras, P. Spirakis, Y, Stamatiou, Ekdosis G. Dardanos - K. Dardanos O.E., 1999  (in Greek).

- An Introduction to Bioinformatics Algorithms, N. C. Jones, P. A. Pevzner, Ekdosis Klidarithmos EPE, 2010 (in Greek).

- Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids, R. Durbin, S. R. Eddy, A. Krogh, Gr. Mitchison, Scientific Editor I. Emiris, Ekdosis Pedio A. E., 2015.

- Algorithms in Structural Bioinformatics, I. Emirs, Notes, National and Kapodistrian University of Athens, 2015.

Updated: 4-Oct-2017                                                                               email: emarkou@ucg.gr