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/2026.Il 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.
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 (2016/2017)
Codice insegnamento
4S004556
Docente
Coordinatore
Crediti
6
Lingua di erogazione
Inglese
Settore Scientifico Disciplinare (SSD)
INF/01 - INFORMATICA
Periodo
II sem. dal 1 mar 2017 al 9 giu 2017.
Obiettivi formativi
Nel corso studieremo strutture dati ed algoritmi per dati testuali (sequenze, stringhe). 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).
Nel recente avanzamento della ricerca in biologia computazionale, l'uso di queste strutture dati è stato fondamentale, e inoltre i metodi si applicano anche a tutti gli altri tipi di dati testuali.
Il corso fornirà
- le conoscenze necessarie per comprendere le sfide fondamentali collegate all'elaborazione di dati testuali,
- conoscenza dei problemi computazionali più frequenti che si devono risolvere su dati testuali (pattern matching, repeat finding, string statistics, etc.),
- familiarità con degli indici testuali più comuni.
Al termine dell’insegnamento lo studente sarà in grado di
- scegliere la struttura dati adatta per un'applicazione su dati testuali,
- risolvere nuovi problemi usando le strutture dati studiate,
- essere cosciente degli argomenti di cui tenere conto quanto si sceglie un algoritmo o una struttura dati (per es., dimensione dell'alfabeto, spazio richiesto, compressibilità).
Programma
Dopo un'introduzione alle stringhe (sequenze), le loro proprietà e delle questioni fondamentali al riguardo (dimensione dell'alfabeto, confronto dei caratteri, ordinamento delle stringhe), studieremo
- tries
- suffix trees
- suffix arrays, enhanced suffix arrays
- Burrows-Wheeler Transform (BWT)
Per ognuno di questi, studieremo le loro caratteristiche, algoritmi di costruzione efficienti ed applicazioni ai problemi specifici.
Il corso prevede anche una breve trattazione di algoritmi classici di pattern matching non basati su indici.
Libri di testo di riferimento:
1) Enno Ohlebusch, Bioinformatics Algorithms, 2013
2) Dan Gusfield, Algorithms on Strings, Trees, and Sequences, 1997
| 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 |
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 ordinamento delle stringhe
- 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, ecc.
