1.Algorithms and Complexity Computational complexity of algorithms and programs - Fast versus Slow Algorithms - Big-O Notation - Algorithm Design Techniques – Tractable versus Intractable Problems - NP-complete problems. 2. Algoritmic Techniques Greedy Algorithms - Dynamic Programming - Exhaustive Search - Branch-and-Bound Algorithms - Heuristics – Branch and Bound (these techniques are introduced when they are applied in solving problems considered in sections 4-6). 3. Graph Algorithms Basic definition on Graphs – Memory representation – Connectivity - Shortest path, Eulerian path, Traveling Salesmna problem, Hamiltonia path. 4. DNA Assembling Shortest Superstring Problem - DNA Arrays as an Alternative Sequencing Technique - Sequencing by Hybridization - SBH as a Hamiltonian Path Problem - SBH as an Eulerian Path Problem - Fragment Assembly in DNA Sequencing – Overlap-Layout-Consensus assembly- De Bruijn graph assembly – Scaffolding. 5. HiddenMarkovModels CG-Islands and the “Fair Bet Casino” – Definition of Hidden Markov Models - Decoding Algorithm - HMM Parameter Estimation. 6. Clustering and Trees Gene Expression Analysis - Hierarchical Clustering - k-Means Clustering - Clustering and Corrupted Cliques - Evolutionary Trees - Distance-Based Tree Reconstruction - Reconstructing Trees from Additive Matrices - Evolutionary Trees and Hierarchical Clustering - Character-Based Tree Reconstruction - Small Parsimony Problem - Large Parsimony Problem. 7. Advanced topics in large networks and phylogenetic recontructions.

Libro di Testo Neil C. Jones, Pavel A. Pevzner: An Introduction to Bioinformatics Algorithms, MIT Press (capp. 2,5.1-5.3, 6, 8,10, 11) Altri testi distribuiti in classe e disponibili sulla piattaforma e-learning Martin Vingron, Jens Stoye, Hannes Luz Algorithms for Phylogenetic Reconstructions, Notes Slides delle lezioni Materiale (suggerito) per i seminari