Docente: Nadia Pisanti
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.
BREVE INTRODUZIONE ALLA BIOLOGIA MOLECOLARE: Il DNA. Le proteine. La cellula. La sintesi proteica.
ESTRAZIONE DI MOTIVI: Algoritmo KMR per l'estrazione di motivi esatti e sue varianti per i motivi approssimati. Impiego del suffix tree nell'estrazione di motivi esatti e approssimati e nello studio di sequenze genomiche.
RICERCA DI RIPETIZIONI: Algoritmi per la ricerca di lunghe ripetizioni approssimate. Filtri per preprocessing.
ALLINEAMENTI DI SEQUENZE: Metodo di Programmazione dinamica per allineamento locale e globale. Longest Common Subsequence. Allineamenti multipli.
FRAGMENT ASSEMBLY: Importanza del problema nel sequenziameno di genomi. Possibili approcci e complicazioni. Suo legame con il problema “Shortest common superstring”. Soluzione greedy. Problemi algoritmici posti dalle nuove tecnologie di sequenziamento.
GENOME REARRANGEMENT: Problemi di sorting: (signed) reversal e transposition. Breakpoint distance. Transformation distance.
SUFFIX TREE tre.pdf
FRAGMENT ASSEMBLY fragmentassembly.pdf
ALLINEAMENTI DI SEQUENZE allineamenti.pdf
NEW GENERATION SEQUENCING illumina-assembly.pdf