Docente: Nadia Pisanti

[Febbraio 2014] Dal giorno 4 Marzo le lezioni si terranno in aula D3.

[Maggio 2013] Creata la pagina del Corso per l'anno accademico 2013-2014.

L'obiettivo del corso è di fornire allo studente una panoramica di algoritmi concepiti per lo studio di sequenze genomiche. Verra' prestata attenzione sia agli aspetti teorici e combinatori che a quelli pratici posti dai vari problemi quali il sequenziamento di interi genomi, l'allineamento di sequenze, la ricerca di pattern ripetuti e di lunghe ripetizioni approssimate, il calcolo di distanze genomiche, e altri problemi biologicamente rilevanti per lo studio di sequenze molecolari.

LA COMPLESSITA' COMPUTAZIONALE Complessita' in tempo e spazio di un algoritmo. Complessita' e trattabilita' di un problema.

ALLINEAMENTI DI SEQUENZE Problema dell'allineamento di sequenze: algoritmo di programmazione dinamica per l'allineamento globale, locale, e semi-globale di coppie di sequenze, e sue possibili ottimizzazioni. Allineamento con 'affine gap penalty function'. Allineamenti multipli.

RICERCA DI PATTERN IN UN DATA BASE Problema della ricerca di un pattern in un data base: possibili soluzioni e analisi comparativa delle loro performance e complessita'. Metodi che fanno preprocessing del pattern: Knuth-Morris-Pratt, Boyer-Moore, Karp-Rabin. Metodi di indicizzazione del data base.

FRAGMENT ASSEMBLY Ricostruzione di sequenze biologiche 'in silico' dopo il sequenziamento: algoritmi e strutture dati per il metodo Sanger e loro limiti. Che cosa cambia con le tecniche di sequenziamento del “New Generation Sequencing”.

PER LA PARTE DI COMPLESSITA': parte dei capitoli 1 e 2 del libro “An Introduction to Bioinformatics Algorithms” di Neil C.Jones e Pavel A.Pevzner, MIT Press, 2004.

PER LA PARTE DI ALLINEAMENTI DI SEQUENZE: parte del capitolo di libro allineamenti.pdf

PER LA PARTE DI FRAGMENT ASSEMBLY: parte del capitolo di libro fragmentassembly.pdf

PER LA PARTE DI PATTERN MATCHING: patternmatching1.pdf e patternmatching2.pdf

• REGISTRO DELLE LEZIONI