BIOINFORMATICA

Avvisi

[12/05/2009] Attenzione: i seminari del 1 Giugno sono rimandati al 4 Giugno alle ore 10.

[02/04/2009] Attenzione: le date dei seminari di Bevilacqua-Orru' e di Bonetta-Picci sono state scambiate.

[24/03/2009] Per permettere lo svolgimento delle discussioni delle lauree, la lezione del 3 Aprile si svolgera' in aula L1 anziche' in aula C1.

[23/03/2009] Sono pubblicarte sul sito le date dei seminari-esami.

[08/03/2009] L'assegnazione degli argomenti per i seminari avverrà Mercoledì 11 Marzo.

Descrizione del Corso

Il corso vale 6 CFU (circa 48 ore).
La frequenza è altamente consigliata (salvo che per gli studenti-lavoratori).

Obiettivi

L'obiettivo del corso è 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 quali il sequenziamento di interi genomi, l'allineamento di sequenze, la ricerca di pattern ripetiti e di lunghe ripetizioni approssimate, il calcolo di distange genomiche, e altri problemi biologicamente rilevanti per lo studio di sequenze molecolari.

Programma

BREVE INTRODUZIONE ALLA BIOLOGIA MOLECOLARE: Il DNA. Le proteine. La cellula. La sintesi proteica. I geni. Le mutazioni.
PATTERN MATCHING: Matching Esatto. Preprocessing del pattern: Algoritmo Boyer-Moore, Algoritmo Knuth-Morris-Pratt, Automa di Aho-Corasick. Metodo con funzione hash di Karp-Rabin Preprocessing del testo: indici con albero dei suffissi. Pattern matching Approssimato.
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.

Orario delle lezioni

Mercoledì dalle ore 14,30 alle ore 16 in aula C1.

Venerdì dalle ore 11,15 alle ore 12,45 in aula C1.

Ricevimento

Mercoledì 11-13 presso la stanza del docente, Dipartimento di Informatica.

Riferimenti

I riferimenti verranno indicati lezione per lezione in questa pagina e verranno resi disponibili agli studenti.
Saranno comunque parte dei seguenti testi:

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.

Modalità d'esame

Seminari a gruppi di 2 persone.
I tempi assegnati per i seminari sono venti-trenta minuti a persona.

Chiunque avesse bisogno di un computer per proiettare slides al seminario è pregato di contattare il docente con ragionevole anticipo.

Argomenti per i seminari:

Segment-based multiple sequence alignment, di T.Rausch, A.-K.Emde, D.Weese, A.Doring, C.Notredame, K.Reinert, ECCB 2008.
Assegnato a Letterio Galletta.
Seminario TENUTO il 22 Maggio alle 14:15 in Sala Seminari EST (Dipartimento di Informatica). Lucidi
The Fragile Breakage versus Random Breakage Models of Chromosome Evolution di Q.Peng, P.A.Pevzner, G.Tesler, PLOS Computational Biology 2(2), 2006.
Assegnato a Raffaella Brasino e Antonio Miraglia.
Seminario TENUTO il 15 Maggio alle 11:15 in aula C1. Lucidi
Analysis of Maximal Repetitions in Strings di M.Crochemore, L.Ilie, MFCS 2007 e Understanding Maximal Repetitions in Strings di M.Crochemore, L.Ilie, STACS 2008.
Assegnato a Nicola De Maio e Nino Cauli.
Seminario TENUTO il 29 Aprile alle ore 14:30 in aula C1. Lucidi
Two algorithms for LCS Consecutive Suffix Alignment di G.M.Landau, E.Myers, M.Ziv-Ukelson, Journal of Computer and System Science 73, 2007.
Assegnato a Gabriele Cocco.
Seminario TENUTO il 22 Maggio alle ore 11:15 in aula C1. Lucidi PDF Lucidi PPT (con animazioni).
Fixed-parameter algorithms for protein similarity search under mRNA structure constraints di G.Blin, G.fertin, D.Hermelin, S.Vialette, Journal of Discrete Algorithms 6, 2008.
Assegnato a Tiziano De Matteis e Andrea Bozzi.
Seminario TENUTO il 22 Maggio alle ore 14:15 in Sala Seminari EST (Dipartimento di Informatica). Lucidi
Analysis of Segmental Duplications via Duplication Distance di C.L.Kahn, B.J.Raphael, ECCB 2008 e A Parsimony Approach to analysis of human segmental duplications di C.L.Kahn, B.J.Raphael, PCB 2009.
Assegnato a Danilo Cimino.
Seminario TENUTO il 4 Giugno alle ore 10:00 in Sala Seminari EST (Dipartimento di Informatica). Lucidi
Motif Search in Graphs: Application to Metabolic Networks di V.Lacroix, C.G.Fernandes, M.-F.Sagot, IEEE/ACM Transactions on Computational Biology and Bioinformatics 3(4), 2006.
Assegnato a Luca Tomaino e Ilaria Clara Urciuoli.
Seminario TENUTO il 4 Giugno alle ore 10:00 in Sala Seminari EST (Dipartimento di Informatica). Lucidi
An Introduction to Metabolic Networks and Their Structural Analysis di V.Lacroix, L.Cottret, P.Thebault, M.-F.Sagot, IEEE/ACM Transactions on Computational Biology and Bioinformatics 5(4), 2008.
Assegnato a Luca Puccini e Saverio Del Priori.
Seminario TENUTO il 4 Giugno alle ore 10:00 in Sala Seminari EST (Dipartimento di Informatica). Lucidi
A small trip in the untranquil world of genomes. A survey on the detection and analysis of genome rearrangement breakpoints di C.Lemaitre, M.-F.Sagot, Theoretical Computer Science 395, 2008.
Assegnato ad Alice Fulgido e Giuseppe Cazzato.
Seminario TENUTO il 15 Maggio alle ore 14:15 in Sala Seminari EST (Dipartimento di Informatica). Lucidi
Assignment of orthologous genes via genome rearrangement di X.Chen, J.Zheng, Z.Fu, P.Nan, Y.Zhong, S.Lonardi, T.Jiang, IEEE/ACM Transactions on Computational Biology and Bioinformatics 2(4), 2005.
Assegnato a Selene Centi e ? Fabbretti.
Seminario TENUTO il 20 Maggio alle ore 14:30 in aula C1. Lucidi
Sorting signed permutations by inversions in O(n log n) time di K.M.Swenson, V.Rajan, Y.Lin, B.M.E.Moret, RECOMB 2009.
Assegnato a Daniele Bonetta e Paolo Picci.
Seminario TENUTO il 20 Maggio alle ore 14:30 in aula C1. Lucidi
Textual Data Compression and the -omic Science: A synopsis di R.Giancarlo, D.Scaturro, F.Utro, Bioinformatics 2008, e Supplementary Material for Textual Data Compression and the -omic Science: A synopsis di R.Giancarlo, D.Scaturro, F.Utro, Bioinformatics 2008.
Assegnato a Antonino Parisi. Lucidi ppt (con animazioni) Lucidi

Seminario da tenersi il 16 Giugno alle ore 10,30.
PatternHunter: faster and more sensitive homology search di B.Ma, J.tromp, M.Li, Bioinformatics 18(3), 2002.
Assegnato a Nicola Guido.
Seminario TENUTO il 4 Giugno alle ore 10:00 in Sala Seminari EST (Dipartimento di Informatica). Lucidi
Computation of Median Gene Clusters di S.Bocker, K.Jahn, J.Mixtacki, J.Stoye, RECOMB 2008.
Assegnato a Valentina Marioli e Marco Argiolas.
Seminario TENUTO il 15 Maggio alle ore 11:15 in aula C1. Lucidi
Multichromosomal genome median and halving problems di E.Tannier, C.Zheng, D.Sankoff, WABI 2008.
Assegnato a Daniele Bevilacqua e Linda Orru'.
Seminario TENUTO il 15 Maggio alle ore 14:15 in Sala Seminari EST (Dipartimento di Informatica). Lucidi
A Unifying View of Genome Rearrangements di A.Bergeron, J.Mixtacki, J.Stoye, WABI 2006.
Assegnato a Ortega Barbara Otzone.
Seminario TENUTO il 15 Maggio alle ore 14:15 in Sala Seminari EST (Dipartimento di Informatica). Lucidi
Detecting Repeat Families in Incompletely Sequences Genomes di J.A.Amgarten Quitzau, J.Stoye, WABI 2008.
Assegnato a Giuseppe Zichitella e Claudio Porta.
Seminario TENUTO il 22 Maggio alle ore 11:15 in aula C1. Lucidi

Su eventuale richiesta dello studente l'esame può essere svolto con altre modalità (scritto, orale, seminario non in gruppo, eccetera).

Corso di Laurea Specialistica in Informatica Corso di Laurea Specialistica in Tecnologie Informatiche anno accademico 2008-2009