Course Syllabus
Obiettivi
ll corso si propone di introdurre lo studente ad una recente disciplina, la Bioinformatica. Questa disciplina nasce dalla necessità di comprendere, dal punto di vista dell’Informatica, i meccanismi che regolano le computazioni nei processi biologici per poi sviluppare adeguati strumenti computazionali per la soluzione di molteplici problemi ad essi legati.
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.
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.
- modellare la soluzione di problemi biologici su sequenze genomiche mediante la formulazione di problemi combinatori.
- utilizzare le banche dati genomiche per estrarre le informazioni di interesse sul genoma umano.
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,
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 understanding the mechanisms involved in biological processes in order to find the solution to computational problems arising from them. 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
