BIOINFORMATICA

Descrizione del Corso

Il corso vale 6 CFU (circa 48 ore).
La frequenza è obbligatoria (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.

• RICOSTRUZIONE DI ALBERI FILOGENETICI: Metodi basati su caratteri. Metodi basati su distanze.

Orario delle lezioni

Lunedì dalle ore 16 alle ore 18 in aula C1.

Martedì dalle ore 16 alle ore 18 in aula E.

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-3 persone da svolgersi prioritariamente entro Natale (2007!).
Questi saranno rivolti a tutti gli studenti di questo corso e del corso omonimo della laurea Specialistica in Scienze e Tecnologie Biomolecolari.

I tempi assegnati per i seminari sono di mezzora a persona; pertanto, i gruppi di tre persone hanno assegnati 90 minuti, quelli di due persone 60 minuti, e quelli di una sola persona 30 minuti.

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

Argomenti per i seminari:

• Algoritmo Boyer Moore in versione approssimata per sequenze geniche: articoli 1. A Fast Algorithm for Approximate String Matching on Gene Sequences, di Z.Liu, X.Chen, J.Borneman, T,Jiang, 17th Combinatorial Pattern Matching (CPM), 79-90, 2005. 2. Tuning Approximate Boyer-Moore for Gene Sequences, di P.Kalsi, L.Salmela, J.Tarhio, proceedings of 14th International Symposium on String Processing and Information Retrieval (SPIRE), 173-183, 2007. ASSEGNATO a MARCON Lorenzo, VANDONI Riccardo, BROCCOLO Daniele. TENUTO il 26 Novembre alle ore 16 in aula C1. Lucidi
  

• Allineamento multiplo: tool a confronto: MLAGAN, GLAM, CLUSTAL. ASSEGNATO a TANCA Matteo, RENIERI Andrea. DA TENUTO l'11 Dicembre alle ore 16 in aula E. Lucidi
  

• Allineamento di sequenze in tempo subquadratico: articolo A sub-quadratic Sequence Alignment for Unrestricted Scoring Matrices, di M.Crochemore, G.M.Landau, M.Ziv-Ukelson, SIAM Journal of Computing 32(6): 1654-1673, 2003. ASSEGNATO A SARTI Francesco. DA TENERSI IN DATA DA STABILIRE.
  

• Automi di Aho Corasick per matching di insiemi di pattern e di espressioni regolari. Estensione al caso bidimensionale. ASSEGNATO a TANI Alice, ADDEA Simonetta, CAMAROTO Alessio. TENUTO il 13 Novembre alle ore 14 in aula PS1 (palazzo presidenza della facoltà). Lucidi
  

• Filtri per allineamento multiplo locale: articoli 1. Lossless filter for multiple repetitions with Hamming Distance, di P.Peterlongo, N.Pisanti, F.Boyer, A.Pereira do Lago, M.-F.Sagot, Journal of Discrete Algorithms, 2007. 2. Lossless Filter for Long Multiple repetitions with Edit Distance di P.Peterlongo e N.Pisanti e A.Pereira do Lago e M.-F.Sagot, TR-06-11, University of Pisa. ASSEGNATO a GOLINO Giovanni, GALDI Liliana, SOLLANO Giuseppe. TENUTO il 4 Dicembre alle ore 16 in aula E. Lucidi
  

• [per al piu' due persone] Filtro per pattern matching approssimato: articolo Efficient q-gram Filters for finding all epsilon-matches over a given length, di K.R.Rasmussen, J.Stoye, E.W.Myers, Journal of Computational Biology 13(2): 296-308, 2006. ASSEGNATO a PRATESI Francesca, RIGHETTI Giacomo. TENUTO il 3 Dicembre alle ore 16 in aula C1. Lucidi
  

• Ricerca di ripetizioni colineari in cDNA: articoli 1. Match Chaining Algorithms for cDNA Mapping di T.Shibuya e I.Kurochkin, proceedings of 3rd Workshop on Algorithms in Bioinformatics (WABI), 462-475, 2003. 2. Chaining Algorithms and applications to comparative genomics di M.I.Abouelhoda e E.Ohlebusch, Journal of Discrete Algorithms 3(2-4), 321-341, 2005. 3. A chaining Algorithm for Mapping cDNA Sequences to Multiple Genomic Sequences di M.Abouelhoda, proceedings of 14th International Symposium on String Processing and Information Retrieval (SPIRE), 1-13, 2007. ASSEGNATO A RUSTICI Flavia, ORBINI MICHELUCCI Michele, GUTIERREZ Miguel. TENUTO il 12 Dicembre alle ore 14 in Sala Seminari EST del Dipartimento di Informatica. Lucidi
  

• FANMOD: tool per l'inferenza di network motifs. ASSEGNATO A CROCI Elisa. TENUTO il 13 Dicembre alle ore 14 in Sala Seminari EST del Dipartimento di Informatica.
  

• MAVISTO: Motif Analysis and VISualization TOol. ASSEGNATO a GUO Chuan, SHI Jiayi. TENUTO il 13 Dicembre alle ore 14 in Sala Seminari EST del Dipartimento di Informatica. Lucidi
  

• MFINDER: network motifs by building blocks. ASSEGNATO a ALECI Claudia. TENUTO l'11 Dicembre alle ore 16 in aula E.
  

• Fragment Assembly: articoli 1. Human Whole-Genome Shotgun Sequencing di G.L.Weber and E.W.Myers, Genome Research 7, 401-409, 1997. 2. The Fragment Assembly string graph di E.W.Myers, Bioinformtics 21(2) ii79-ii85, 2005. 3. Computability of Models for Sequence Assembly di P.Medvedev and K.Georgiou and E.W.Myers and M.Brudno, 7th Workshop on Algorithms in Bioinformatics (WABI), 289-301, 2007. ASSEGNATO a VITALE Daniele, SOTTILE Michele, SAMMARTINO Matteo. TENUTO il 10 Dicembre alle ore 16 in aula C1. Lucidi
  

• Ricerca di blocchi di sintenia: articoli 1. Models in comparative genomics: genome correspondence, gene identification and motif discovery di M.Kellis and N.Patterson and B.Birren and B.Berger and E.S.Lander, Journal of Computational Biology 11(2) 319-355, 2004 2. Removing Noise and Ambiguities from Comparative Maps in Rearrangement Analysis di C.Zheng and Q.Zhu and D.Sankoff, to appear in IEEE/ACM Transactions on Computational Biology and Bioinformatics, 2007. 3. Algorithms for the extraction of Synteny Blocks from Comparative Maps di V.Choi and C.Zheng and Q.Zhu and D.Sankoff, 7th Workshop on Algorithms in Bioinformatics (WABI), 277-288, 2007. ASSEGNATO a SANTORO Roberto, RAGLIANTI Marco. TENUTO il 27 Novembre alle ore 16 in aula E. Lucidi

Sommario delle lezioni