Computational analysis of genomic sequences (2016/2017)

Codice insegnamento
4S004556
Docente
Zsuzsanna Liptak
Coordinatore
Zsuzsanna Liptak
crediti
6
Settore disciplinare
INF/01 - INFORMATICA
Lingua di erogazione
Inglese
Periodo
II sem. dal 1-mar-2017 al 9-giu-2017.

Orario lezioni

II sem.
Giorno Ora Tipo Luogo Note
martedì 16.30 - 18.30 lezione Aula M dal 14-mar-2017  al 9-giu-2017
mercoledì 14.30 - 16.30 lezione Aula B dal 8-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

Testi di riferimento
Autore Titolo Casa editrice Anno ISBN Note
Dan Gusfield Algorithms on Strings, Trees, and Sequences 1997
Enno Ohlebusch Bioinformatics Algorithms 2013

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.

Opinione studenti frequentanti - 2015/2016


Statistiche per i requisiti di trasparenza (Attuazione Art. 2 del D.M. 31/10/2007, n. 544)

I dati relativi all'AA 2016/2017 non sono ancora disponibili