Studiare
In questa sezione è possibile reperire le informazioni riguardanti l'organizzazione pratica del corso, lo svolgimento delle attività didattiche, le opportunità formative e i contatti utili durante tutto il percorso di studi, fino al conseguimento del titolo finale.
Piano Didattico
Queste informazioni sono destinate esclusivamente agli studenti e alle studentesse già iscritti a questo corso.Se sei un nuovo studente interessato all'immatricolazione, trovi le informazioni sul percorso di studi alla pagina del corso:
Laurea magistrale in Medical bioinformatics - Immatricolazione dal 2025/2026Il piano didattico è l'elenco degli insegnamenti e delle altre attività formative che devono essere sostenute nel corso della propria carriera universitaria.
Selezionare il piano didattico in base all'anno accademico di iscrizione.
1° Anno
| Insegnamenti | Crediti | TAF | SSD |
|---|
One course to be chosen among the followingTwo courses to be chosen among the following2° Anno Attivato nell'A.A. 2020/2021
| Insegnamenti | Crediti | TAF | SSD |
|---|
Three courses to be chosen among the following| Insegnamenti | Crediti | TAF | SSD |
|---|
One course to be chosen among the followingTwo courses to be chosen among the following| Insegnamenti | Crediti | TAF | SSD |
|---|
Three courses to be chosen among the following| Insegnamenti | Crediti | TAF | SSD |
|---|
Legenda | Tipo Attività Formativa (TAF)
TAF (Tipologia Attività Formativa) Tutti gli insegnamenti e le attività sono classificate in diversi tipi di attività formativa, indicati da una lettera.
Computational analysis of genomic sequences (2020/2021)
Codice insegnamento
4S004556
Docente
Coordinatore
Crediti
6
Lingua di erogazione
Inglese
Settore Scientifico Disciplinare (SSD)
INF/01 - INFORMATICA
Periodo
I semestre dal 1 ott 2020 al 29 gen 2021.
Obiettivi formativi
Il corso mira a far conoscere agli studenti le principali strutture dati avanzati per l'analisi di sequenze genomiche ed in generale di dati testuali. Conoscenza e capacità di comprensione Fornire le conoscenze e le competenze necessarie per la comprensione dei parametri fondamentali nel campo di algoritmi su sequenze, delle soluzioni a problemi tipici di analisi di dati genomici usando diverse strutture dati avanzati su sequenze, insieme all'analisi dei costi computazionali (spazio e tempo) di tali soluzioni. Conoscenze applicate e capacità di comprensione Al termine del corso lo studente dovrà dimostrare di saper tradurre tipici problemi di analisi di sequenze genomiche in operazioni e algoritmi su indici testuali e valutarne il costo computazionale. Autonomia di giudizio Al termine del corso lo studente dovrà dimostrare di saper giudicare se un algoritmo o una struttura dati per un dato problema su sequenze genomiche sono adatti o meno, incluso la valutazione del costo computazionale. Abilità comunicative Alla fine del corso lo studente sarà in grado di formalizzare correttamente degli algoritmi su sequenze con o senza l'uso delle strutture dati avanzate. Capacità di apprendere Alla fine del corso lo studente sarà in grado di leggere e comprendere autonomamente articoli scientifici e testi specialistici che utilizzano strutture dati avanzate per l'analisi di dati testuali.
Programma
Nel recente avanzamento notevole della ricerca in biologia computazionale, l'uso delle strutture dati per sequenze genomiche e altre sequenze biologiche, e' stato fondamentale. Inoltre i metodi si applicano anche a tutti gli altri tipi di dati testuali.
La recente esplosione della quantità di dati a nostra disposizione ("big data") presenta una delle sfide più importanti in informatica oggi. Tanti di questi dati sono di carattere testuale (o facilmente si possono presentare in forma testuale): sequenze genomiche o di altri tipi provenienti dalla biologia computazionale; pagine web / web crawl data; grandi quantità di posta elettronica; libri scannerizzati; dati musicali; ecc. Per poter memorizzare ed elaborare questi dati, ma sopratutto per poter estrarne informazioni utili, abbiamo bisogno di strutture dati e algoritmi dedicati, cioè sviluppati specificamente per applicazioni su dati testuali di grandi dimensioni, cosidetti "indici testuali" (text indices).
Programma del corso:
1) introduzione alle stringhe (sequenze), le loro proprietà e delle questioni fondamentali al riguardo: dimensione dell'alfabeto, confronto dei caratteri, ordinamento delle stringhe
2) algoritmi classici di pattern matching non basati su indici: Knuth-Morris-Pratt, Boyer-Moore, Rabin-Karp, Aho-Corasick
3) Strutture dati per stringhe I:
- tries
- suffix trees
4) Strutture dati per stringhe II:
- suffix arrays, enhanced suffix arrays
- Burrows-Wheeler Transform (BWT), FM-index
Per ognuna delle strutture dati, studieremo le loro caratteristiche, algoritmi di costruzione efficienti ed applicazioni ai problemi specifici.
Non sono necessarie conoscenze di biologia per seguire il corso.
| Autore | Titolo | Casa editrice | Anno | ISBN | Note |
|---|---|---|---|---|---|
| Dan Gusfield | Algorithms on Strings, Trees, and Sequences | Cambridge University Press | 1997 | 0 521 58519 8 | |
| Enno Ohlebusch | Bioinformatics Algorithms | 2013 | 978-3-00-041316-2 | ||
| V. Mäkinen, D. Belazzougui, F. Cunial, and A.I. Tomescu | Genome Scale Algorithm Design (Edizione 1) | Cambridge University Press | 2015 | ISBN 978-1-107-07853-6 | |
| Maxime Crochemore and Wojciech Rytter | Jewels of Stringology | World Scientific | 2003 | 981-02-4782-6 |
Modalità d'esame
Esame finale: scritto e orale. Nello scritto saranno richieste sia proprieta' degli algoritmi e strutture dati studiati (per es. tempo e spazio richiesti), sia di applicarli su esempi concreti. Nell'orale saranno approfondite le domande dello scritto, tale che lo studente possa dimostrare le sue conoscenze.
L'esame accertera' che lo studente
- abbia acquisito conoscenze dei problemi principali riguardante la gestione delle sequenze e stringhe (alfabeto, confronto di stringhe, dimensioni di sequenze genomiche e altre)
- sappia applicare, spiegare, e analizzare gli algoritmi studiati per pattern matching non index-based
- sappia applicare, spiegare e analizzare le strutture dati studiate, lo spazio che richiedono e algoritmi di costruzione (inverted index, trie, suffix tree, suffix array, BWT)
- sappia applicare, spiegare e analizzare varie applicazioni di queste strutture dati: come usarle per risolvere problemi su stringhe, quali pattern matching, matching statistics, palindromes, LZ-compression ecc.
Non è previsto un esame specifico per studenti non-frequentanti.
