Docente
|
MARCHETTI SPACCAMELA ALBERTO
(programma)
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
|