ALGORITHMS AND COMPLEXITY IN BIOLOGY

Description:
The purpose of the course is to introduce basic algorithms and algorithm design methods, to deepen the analysis of an algorithm and to familiarize students with the concepts of correctness and computational complexity, to introduce the NP class and computationally difficult problems, the presentation of the polynomial reduction method, the presentation of the Protein Folding problem, its analysis and the presentation of NP-hardness results and approximate algorithms and finally the introduction to parallel and distributed algorithms.

After successfully completing the course, students will be able to:

• Do the mathematical modelling of a decision or optimisation problem
• Design an algorithm and analyse it (proof of correctness and computational complexity)
• Prove that a decision problem is NP-hard Design approximate algorithms
• Methods of designing good algorithms:
• “divide and conquer”, dynamic programming, greedy algorithms.
• Applications in graph theory (depth-first search, breadth-first search, minimum tree-skeleton, least-cost path).
• Data processing (layout and search).
• Polynomial-time algorithms and NP-complete problems. Easy and difficult combinatorial optimization problems, decision problems, P and NP classes, NP-complete problems and reductions.
• The Protein folding problem, the Hydrophobic-Polar model, Levinthal paradox, NP-hardness results and approximate algorithms.
• Parallel and distributed algorithms.

Bibliography:
1. Introduction to Algorithms (in one volume), T. Cormen, C. Leiserson, R. Rivest, C. Stein, University Publications of Crete, 2012.
2. Algorithm Design, J. Kleinberg, E. Tardos, Cleydarithmos Publications, 2009 – Algorithms, S. Dasgupta, C. Papadimitriou, U. Vazirani, Cleydarithmos Publications, 2009.
3. Algorithms and Complexity, E. Zachos, Notes, National Technical University of Athens, 2007.
4. Algorithms, P. Bozanis, A. Tziola Publications & Sons S.A., 2006.
5. Analysis and design of algorithms, L. Anany, A. Giola Publications. Sons S.A., 2008.
6. The design and Analysis of Computer Algorithms, A. Aho, J. Hopcroft, J. Ullman. Addison-Wesley Publishing Company, 1974.
7. Computers and Intractability: A Guide to the Theory of NP-Completeness, M. Garey, D. Johnson. W. H. Freeman and Company, 1979
8. Graph Theory, A. Papaioannou, Notes, National Technical University of Athens, 2010.
9. Θεωρία και Αλγόριθμοι Γράφων, Ι. Μανωλόπουλος, Α. Παπαδόπουλος, Κ. Τσίχλας, Εκδόσεις Νέων Τεχνολογιών Μον. ΕΠΕ, 2013.
10. Εισαγωγή στους γράφους, Λ. Κυρούσης, Χ. Μπούρας, Π. Σπυράκης, Γ. Σταματίου, Εκδόσεις Γ. Δαρδάνος – Κ. Δαρδάνος Ο. Ε., 1999.
11. Εισαγωγή στους Αλγόριθμους Βιοπληροφορικής, N. C. Jones, P. A. Pevzner, Εκδόσεις Κλειδάριθμος ΕΠΕ, 2010.
12. Ανάλυση Βιολογικών Αλληλουχιών, R. Durbin, S. R. Eddy, A. Krogh, Gr. Mitchison, Επιστ. Επιμ. Γ. Εμίρης, Εκδόσεις Πεδίο Α. Ε., 2015.
13. Αλγόριθμοι στη Δομική Βιοπληροφορική, Γ. Εμίρης, Σημειώσεις, Εθνικό και Καποδιστριακό Πανεπιστήμιο Αθηνών, 2015