Algoritmi per la bioinformatica

Nadia Pisanti        Tel. 0502213152

Un corso di base di Algoritmica.

L'obiettivo del corso è di fornire allo studente una panoramica di algoritmi concepiti per l'analisi 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 di analisi di sequenze biologiche.

Conoscenze.

This course will focus on algorithmic approaches to the management, storage, and investigation of biological sequences. We will describe problems raising in molecular biology research that can be modeled as problem on strings, or trees, or graphs whose solution could give insights to molecular biologists on the investigated data. We will describe algorithmic solutions for them analyzing the critical aspects of the various applications and the practical impact of the possible solutions.

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

ALLINEAMENTI DI SEQUENZE: Metodo di Programmazione dinamica per allineamento locale e globale. Longest Common Subsequence. Allineamenti multipli.

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.

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.

• MOLECULAR BIOLOGY FOR COMPUTER SCIENTISTS, L.Hunter, 1993.
• JEWELS OF STRINGOLOGY, M.Crochemore and W.Rytter, World Scientific, 2002.
• INTRODUCTION TO COMPUTATIONAL MOLECULAR BIOLOGY, J.Setubal and J.Meidanis, PWS, 1997.