Bioinformatica

Nadia Pisanti        Tel. 0502213152

Nozioni di base di algoritmi e complessita'

L'obiettivo del corso e' di fornire allo studente una panoramica di algoritmi non banali concepiti per lo studio di sequenze genomiche. Verra' prestata attenzione sia agli aspetti teorici e combinatori che a quelli pratici posti dai vari problemi, che variano dal sequenziamento di interi genomi, all'allineamento di sequenze e altri problemi biologicamente rilevanti per lo studio di sequenze molecolari.

The general goal of the course is to provide an overview to the fields of bioinformatics and genomics. The focus will be on the theoretical and computational aspects of the fields, as well as on practical description of the topics, tools, issues and current trends in these and related fields.

- BREVE INTRODUZIONE ALLA BIOLOGIA MOLECOLARE: Il DNA. Le proteine. La cellula. La sintesi proteica.

- PATTERN MATCHING: Matching Esatto. Algoritmo Boyer-Moore. Algoritmo MP e KMP.

- ESTRAZIONE DI MOTIVI: Algoritmo KMR per l'estrazione di motivi esatti e sue varianti per i motivi approssimati. La struttura dati suffix tree e suo uso nell'estrazione di motivi esatti e approssimati.

- 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.

- DINAMICA DEI SISTEMI BIOLOGI (dr.P.Milazzo) Modelli matematici della dinamica dei sistemi biologici; L'algoritmo di Gillespie (e varianti) per la simulazione stocastica di reazioni (bio)chimiche; Formalismi e tecniche di analisi per la Systems Biology.

- GENOME REARRANGEMENT: Problemi di sorting: (signed) reversal e transposition. Breakpoint distance. Transformation distance.

Seminario