Course Syllabus
Obiettivi
Conoscenze e comprensione
ll corso si propone di introdurre lo studente ad una recente disciplina, la Bioinformatica. Questa disciplina nasce dalla necessità di sviluppare adeguati strumenti computazionali per la soluzione di molteplici problemi legati alla biologia. Tali strumenti trovano comunque applicazione anche in altri ambiti caratterizzati da elementi comuni alla Bioinformatica, quali il trattamento di grandi moli di dati di sequenze.
L'obiettivo principale del corso è quello di fornire allo studente la padronanza delle tecniche algoritmiche e delle strutture dati per poter affrontare lo studio e la soluzione di problemi computazionali di analisi e confronto di genomi multipli anche considerando gli aspetti di genomica comparativa mediante la costruzione di alberi filogenetici.
Capacità di applicare conoscenza e comprensione
In particolare verrano forniti allo studente gli strumenti per:
- progettare la soluzione algoritmica di problemi di analisi di genomi multipli o di confronto e ricostruzione di alberi filogenetici,
- progettare strutture dati adeguate a trattare grandi quantità di sequenze,
- modellare la soluzione di problemi biologici su sequenze genomiche mediante la formulazione di problemi combinatoriì,
- utilizzare le banche dati genomiche e il software disponibile per estrarre le informazioni di interesse dal genoma umano, quali le variazioni che caratterizzano una popolazione di individui.
Autonomia di giudizio
Lo studente sarà in grado di comprendere la rilevanza di un metodo computazionale dal punto di vista delle rcihieste di risorse spazio e tempo.
Dovrà essere in grado di comprendere se una data struttura dati è adeguata per la soluzione di problemi su sequenze genomiche, in funzione della dimensione del dato
Capacità comunicativa
Lo studente acquisirà il linguaggio e formalismo tipo della disciplina informatica
Capacità di apprendere
Lo studente deve essere in grado di leggere e capier autonomamente un articolo di bioinformatica che tratta le tematiche affrontate nel corso
Contenuti sintetici
Introduzione alla biologia computazionale: motivazioni e metodologie.
L'importanza del confronto e dell'analisi di sequenze biologiche. Tecniche di allineamento di sequenze (allineamento globale e locale e allineamento multiplo). Algoritmi per l’allineamento di sequenze nella predizione della struttura di un gene (splicing alternativo). Assemblaggio di dati di sequenziamento NGS con grafi di de Bruijn compressi. Grafi di de Bruijn e grafi di overlap e loro applicazioni.
La ricerca di motivi in sequenze biologiche. Il problema generale del matching esatto. Gli alberi suffisso, i suffix array e la trasformata di Burrows-Wheeler e la loro applicazione nella ricerca di pattern nelle sequenze biologiche.
Lo studio delle variazioni (mutazioni) geniche nella popolazione. Alberi evoluzionari. Ricostruzione della storia evolutiva di specie con alberi evoluzionari: metodi principali. Applicazione alla genomica tumorale. L'aplotipizzazione di individui: metodi combinatori basati sul modello coalescente e il criterio di massima parsimonia.
Internet e la post-genomica. Le banche dati e il software per l’analisi del genoma.
Programma esteso
1. L'importanza del confronto e dell'analisi di sequenze biologiche. Tecniche di allineamento di sequenze (allineamento globale e locale e multiplo). Algoritmi per l’allineamento di sequenze nella predizione della struttura di un gene (splicing alternativo).
2. Strutture dati e algoritmi su grafi in bioinformatica: grafi di de Bruijn, grafi di overlap e indicizzazione. Applicazioni al problema del sequenziamento di dati NGS e assemblaggio dati.
3. La ricerca di motivi in sequenze biologiche. Il problema generale del matching esatto. Gli alberi suffisso, i suffix array e la trasformata di Burrows-Wheeler e la loro applicazione nella ricerca di pattern nelle sequenze biologiche.
4. Lo studio delle variazioni (mutazioni) geniche nella popolazione. Alberi evoluzionari. Ricostruzione della storia evolutiva di specie con alberi evoluzionari: metodi principali. Assemblaggio di aplotipi: metodi combinatori.
5. Metodi combinatori in Cancer genomics.
6. Internet e la post-genomica. Le banche dati e il software per l’analisi del genoma. La pangenomica computazionale.
Prerequisiti
Nesssuno
Modalità didattica
Tutte le ore di lezione si compongono di una prima parte svolta in modalità erogativa (erogazione dei contenuti) e una seconda parte invece svolta in modalità interattiva.
Materiale didattico
(1) Slides e dispense
(2) An Introduction to Bioinformatics Algorithms N.C Jones, P.A. Pevzner.
(3) Introduction to Computational molecular biology - Carlos Setubal, Joao Meidanis.
(4) Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology -Dan Gusfield.
Periodo di erogazione dell'insegnamento
Secondo semestre
Modalità di verifica del profitto e valutazione
In itinere viene assegnata una prova intermedia da svolgere relativa alle diverse parti del corso. E' prevista poi una prova scritta finale. Il voto finale è determinato dalla valutazione della prova intermedia e della prova scritta finale.
Orario di ricevimento
Per appuntamento
Sustainable Development Goals
Aims
The main goal of the course is to introduce the student to the new discipline that is Bioinformatics. This new research field is strongly motivated by the need of finding the solution of computational problems arising from biological systems. The course will provide the main algorithmic techniques and data structures that the student can use to solve computational problems related to genome sequence analysis or to the reconstruction of the evolutionary history. The student will achieve the ability of solving simple problems of sequence analysis, phylogenetic reconstruction and will learn how to get information from the genome databases.
Contents
Introduction to computational biology: motivations and methodologies. Sequence camparison and analysis and its relevance. Alignment techniques (local and global alignment, multiple alignment). The prediction of the gene structure and the alternative splicing prediction problem. Assembly from NGS data, de Bruijn graphs, overlap graphs and their applications.
The search of motifs and patterns in biological sequences. The pattern matching problem and data structures, such as suffix arrays, suffux trees and BWT transform and their application to pattern search in biological sequences. Applications to cancer genomics. The study of genomic variations in the population. The reconstruction of the evolutionary history. Phylogenetic trees and different methods for reconstructing trees. Haplotyping: methods based on maximum parsimony and the coalescent model.
The genome databases and the use of software tools for genome analysis.
Detailed program
- Introduction to computational biology: motivations and methodologies. Sequence comaprison and analysis and its relevance- Alignment techniques (locan and global alignment, multiple alignment)- The prediction of the gene structure and the alternative splicing prediction problem.
2. Algorithms and data structures in bioinformatics: De Brujin graphs, overlap graphs and indexing of NGS data. Applications to the assembly from NGS data.
3. The prediction of the gene structure and the alternative splicing prediction problem. The search of motifs and patters in biological sequences. The pattern matching problem and data structures, such as suffix arrays, suffux trees and BWT tranform and their application to pattern search in biological sequences.
4. The study of genomic variations in the population.The reconstruction of the evolutionary history. Phylogenetic trees and different methods for reconstructing trees. Haplotyping: methods based on maximum parsimony and the coalescent model.
5. Metodi combinatori in Cancer genomics.
6. The genome databases and the use of software tools for genome analysis. Computational pangenomics.
Prerequisites
None
Teaching form
All the lectures consist of a first part in lecturing format and then in an interactive format
Textbook and teaching resource
(1) Slides and notes
(2) An Introduction to Bioinformatics Algorithms N.C Jones, P.A. Pevzner.
(3) Introduction to Computational molecular biology - Carlos Setubal, Joao Meidanis.
(4) Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology -Dan Gusfield.
Semester
Second semester
Assessment method
A written assignment is given during the course, concerning the different topics of the course. There is a final written test. The final grade is determined by the evaluation of the witten assignment and the written test.
Office hours
By appointment
Sustainable Development Goals
Staff
-
Paola Bonizzoni
