Syllabus del corso
Obiettivi
Alla fine del corso lo studente avrà compreso le principali problematiche computazionali e tecniche algoritmiche in bioinformatica. Sarà in grado di scrivere programmi di modeste dimensioni per risolvere problemi in bioinformatica utilizzando anche dati presenti su basi di dati pubbliche
Conoscenza e comprensione
Questo insegnamento fornisce le conoscenze basilari e capacità di comprensione relativamente a:
- Algoritmi su sequenze biologiche.
- Strutture dati per l'indicizzazione di sequenze
- Algoritmi per la ricostruzione di storie evolutive
- Programmazione in C in campo bioinformatico
- Shell di Unix
- Controllo di versione
- Programmazione in Pyhton in campo bioinformatico
- Formati di file usati in bioinformatica
Capacità di applicare conoscenza e comprensione
Alla fine dell'insegnamento gli studenti saranno in grado di:
- Comprendere quali algoritmi e strutture dati utilizzare per affrontare alcuni problemi in bioinformatica
- Scrivere programmi efficienti in C in campo bioinformatico
- Scrivere programmi in Python in campo bioinformatico
Contenuti sintetici
Principali problemi e algoritmi in bioinformatica. Pattern Matching. Allineamento di sequenze. Sequenziamento di DNA. Storie evolutive. Gestione di dati e basi di dati biologici
Programma esteso
- Algoritmi
e strutture dati per il pattern matching. Algoritmi di Karp-Rabin, Dömölki.
- Suffix tree e suffix array: gestione, pattern matching e loro utilizzo per la ricerca della sottostringa più lunga.
- Allineamento di due sequenze. Allineamento globale, locale, con banda. Costi di gap lineare e generico. Allineamento multiplo.
- Sequenziamento di DNA. Grafi di overlap e grafi di de Bruijn.
- Alberi evolutivi. Modelli a partire da caratteri: algoritmo di Gusfield per la filogenesi perfetta. Modelli a partire da distanze: distanze ultrametriche e distanze additive. Algorithmi UPGMA e Neighbor Joining. Cenni di ricostruzione tramite massima verosimiglianza
- Genotipi e Aplotipi. Distinzione fra singolo individuo e pedigree.
- Formati di file di dati biologici
- Banche dati biologiche
- Metodologie di sviluppo software open source per la bioinformatica
- Cenni di shell
- Cenni di git
Prerequisiti
Algoritmi e strutture dati; Linguaggi di programmazione;
Modalità didattica
Lezioni
in aula e attività di laboratorio. Utilizzo della piattaforma di
e-learning per integrare lo studio individuale tramite arricchimento
delle attività in aula e per autovalutazioni in itinere del livello
di preparazione ottenuto. Durante l'emergenza le lezioni si tengono tramite videolezioni sincrone.
Il corso è erogato in Italiano.
Materiale didattico
Il libro di testo seguito per quasi tutte le lezioni è “Algorithms on Strings, Trees and Sequences”, di Daniel Gusfield, Cambridge Univ. Press. La biblioteca tiene alcune copie del libro di testo, anche come ebook.
Il
libro "An Introduction to Bioinformatics Algorithms" di N. Jones, P.
Pevzner viene usato esclusivamente come approfondimento per la parte di
ricostruzione di filogenesi e di sequenziamento.
Il libro "Theoretical Evolutionary Genetics" di J. Felsenstein viene usato esclusivamente come approfondimento per la parte di ricostruzione di filogenesi. Un libro analogo è Population and Quantitative Genetics by Graham Coop.
Periodo di erogazione dell'insegnamento
primo semestre
Modalità di verifica del profitto e valutazione
La verifica dell'apprendimento consiste di una prova scritta e di una parte progettuale.
La prova scritta è individuale, basata su domande a risposta aperte relativa alle nozioni presentate nel corso relative ai contenuti di natura algoritmica. La prova scritta dura un'ora e contiene 4 domande, ma bisogna rispondere solo a 3 delle 4 domande.
La parte progettuale può essere superata in due modi:
- project work da svolgere individualmente o in piccoli gruppi (max 3 persone), riguardanti gli aspetti di programmazione. Ogni studente decide se svolgerlo in Python o C, mentre il testo viene deciso dai docenti. I gruppi sono formati autonomamente dagli studenti. Ogni studente (o gruppo) riceve un testo personalizzato che viene comunicato al termine del corso. Il progetto viene poi discusso dopo avere superato la prova scritta.
- svolgendo con successo tre esercizi in itinere durante il corso. Gli esercizi devono essere svolti individualmente e consistono nello scrivere programmi in Python (2 esercizi) e C (1 esercizio) entro delle scadenze fissate. Per svolgere con successo l'esercizio, il programma deve superare alcuni test che possono includere un controllo su tempi di calcolo o occupazione di memoria. Chi supera tutte e tre le prove riceve una valutazione di 30/30 per la parte progettuale. Non vengono riconosciuti superamenti parziali (ad esempio, avere svolto 2 esercizi su 3).
La valutazione finale viene ottenuta tramite media pesata delle votazioni ottenute nelle due parti, con peso 50% per la prova scritta e 50% per il project work, ma entrambe le parti devono avere valutazione positiva.
Per la parte scritta non sono previste prove in itinere.
Orario di ricevimento
Su appuntamento per email. Durante l'emergenza il ricevimento viene garantito e gestito tramite videoconferenza.
Aims
The student will know some fundamental problems and algorithms in bioinformatics. The student will be able to write small size programs to solve some problems in bioinformatics, using also data originating from publicly available databases.
Knowledge and understanding
This course provides basic knowledge and understanding on:
- Algorithms on biological sequences
- Data structures to index biological sequencing
- Algorithms for phylogeny reconstruction
- C programming in bioinformatics
- Unix shell
- Version control
- Python programming in bioinformatics
- File Formats used in bioinformatics
Ability to apply knowledge and understanding
At the end of the course the students will be able to:
- decide which algorithms and data structures can be used to solve some problems in bioinformatics
- write efficient C programs for bioinformatics problems
- write Python programs for bioinformatics problems
Contents
Fundamental problems and algorithms in bioinformatics. Pattern matching.Sequence Alignment. DNA sequencing. Evolutionary histories. Managing biological data and databases.
Detailed program
- Pattern matching: Algorithms and Data Structures. Karp-Rabin algorithm, Dömölki algorithm.
- Suffix trees and suffix arrays: management, pattern matching and applications to the longest substring problem.
- Sequence Alignment of two strings. Global alignment, local alignment, band alignment. Linear and generic gap cost. Multiple sequence alignment.
- DNA Sequencing. Overlap graphs and de Bruijn graphs.
- Evolutionary trees. Character-based models. Gusfield's algorithm for the perfect phylogeny. Distance-based models: ultrametrics and additive distance. UPGMA and Neighbor Joining algorithms. Max likelihood.
- Genotypes and haplotypes. Single individual and pedigree cases.
- Biological Data: file formats
- Biological Databases
- Bionformatics open source software development methodologies
- Linux shell
- Git
Prerequisites
Algorithms
and data structures; Programming Languages
Teaching form
Lectures and Laboratory. The individual study can use the
e-learning platform to enrich the standard activities and to self
assess the level of competence acquired during the course. During the emergency, lectures will be with synchronous videoconferences.
This course is taught in Italian.
Textbook and teaching resource
The adopted textbook is “Algorithms on Strings, Trees and Sequences”, by Daniel Gusfield, Cambridge Univ. Press. The library has some copies, also as ebook.
The book "An Introduction to Bioinformatics Algorithms" by N. Jones, P.
Pevzner is used only for some parts on phylogeny reconstruction and on genome sequencing.
The books "Theoretical Evolutionary Genetics" by J. Felsenstein and Population and Quantitative Genetics by Graham Coop are used for some topics on phylogeny reconstruction and on haplotypes.
Semester
First semester
Assessment method
The assessment has a written exam and a project work.
The written exam is taken individually, on the algorithms topics presented during the lectures. This part consists of open-ended questions. The written exam is 1 hour long and contains 4 questions. Of those questions, you have to answer to 3 of them.
The project work can be taken in two alternative ways.
- a project work, mainly consisting of programming, that can be done by a single individual or a small group (max 3 students). Each student decides if they want to write Python or C code. Students decide the group composition. The specification of the project is decided by the lecturers. Each student (or each group) will receive a personalized text after the last lecture. The project will be discussed after the student has passed the written exam.
- Solving three different exercises during the course. Such exercises have to solved individually. Two exercises will consist of writing Python programs, while 1 exercise will be a C program. All exercises will have a strict deadline. To successfully solve an exercise, the program will have to pass some tests, possibly within a specific time limit or wihing a memory constraint. Who successfully completes all exercise will receive a 30/30 evaluation for the project part. No credit will be given for partial exercises (included if you pass 2 exercises out of 3).
The final grade is obtained by weighting 50% of the degree of the written exam and 50% the project work, but you have to pass both parts.
There are no in-progress written exams.
Office hours
Staff
-
Gianluca Della Vedova
-
Raffaella Rizzi