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 Python di modeste dimensioni per risolvere problemi in bioinformatica utilizzando anche dati presenti su basi di dati pubbliche
Conoscenza e capacità di comprensione
Questo insegnamento fornisce 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 Pyhton in campo bioinformatico
- Formati di file usati in bioinformatica
Conoscenza e capacità di comprensione applicate
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 in Python in campo bioinformatico
- Costruire semplici pipeline di analisi di dati bioinformatici
Autonomia di giudizio
Alla fine dell'insegnamento gli studenti saranno in grado di interpretare i risultati di un'analisi bioinformatica.
Abilità comunicative
Alla fine dell'insegnamento gli studenti saranno in grado di comunicare i risultati di un'analisi bioinformatica.
Capacità di apprendere
Alla fine dell'insegnamento gli studenti avranno competenze per:
- apprendere autonomamente nuove librerie e strumenti software in bioinformatica.
- affrontare nuovi problemi computazionali nel campo della genomica.
Contenuti sintetici
Principali problemi e algoritmi in bioinformatica. Pattern Matching. Allineamento di sequenze. Sequenziamento di DNA. Storie evolutive. Gestione di dati (formati standard in Bioinformatica) e banche dati genomiche.
Programma esteso
- Introduzione ai dati genomici: sequenze primarie di DNA, RNA e proteine (formato standard FASTA).
- Espressione genica e splicing alternativo (formati standard BED e GTF).
- Sequenziamento di un genoma e qualità del dato di sequenziamento (formato standard FASTQ).
- Allineamento globale e locale di due sequenze: algoritmi di Needleman-Wunsch, Smith-Waterman e Gotoh.
- Allineamento semi-globale di due sequenze.
- Allineamento con banda di due sequenze.
- Allineamento multiplo.
- Pattern matching esatto: algoritmi di Rabin-Karp e di Dömölki (paradigma shift-and).
- Indicizzazione di testi: suffix tree, suffix array e loro utilizzo per risolvere problemi su stringhe (tra cui pattern matching esatto e ricerca della sottostringa comune più lunga).
- Assemblaggio di un genoma: grafo di overlap e grafo 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.
- Introduzione a Python.
- Pandas (manipolazione di data frame).
- Biopython.
Prerequisiti
- Complessità in tempo e spazio.
- Strutture dati fondamentali: liste, array, alberi di ricerca, dizionari
- Algoritmi di ordinamento: radix sort, merge sort.
- Gerarchia delle memorie.
- Capacità di scrivere un breve programma in qualunque linguaggio di programmazione.
Modalità didattica
Lezioni in aula e attività di laboratorio. Viene utilizzata la 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.
Tutte le attività sono tenute in presenza e vengono registrate, ma non trasmesse in streaming. L'insegnamento è erogato in Italiano. Le attività previste sono:
- 36 ore di lezioni in aula da 2/3 ore svolte in modalità erogativa
- 24 attività di laboratorio da 2 ore svolte in modalità erogativa nella parte iniziale ed in modalità interattiva nella parte successiva
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.
Per quanto riguarda Python fare riferimento a Pensare in Python di A. B. Downey (versione inglese Think Python).
Per la parte relativa a Pandas il libro di riferimento è Python Data Science Handbook di VanderPlas
Periodo di erogazione dell'insegnamento
Secondo 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 aperta relative ai contenuti del corso di natura algoritmica. La prova scritta dura un'ora e contiene 4 domande, tra cui lo studente dovrà sceglierne 3 a cui rispondere.
Le competenze che vengono valutate sono: capacità di astrazione, conoscenza degli algoritmi trattati, capacità di analisi della complessità computazionale.
La prova scritta viene valutata in trentesimi in base alla correttezza e completezza delle risposte e alla capacità di individuare gli elementi essenziali di un argomento.
La parte progettuale consiste nella scrittura di un programma in Python e viene svolta individualmente, con successiva presentazione del lavoro fatto. Gli studenti possono scegliere il testo del progetto tra temi alternativi proposti dal docente al termine delle lezioni.
La discussione del progetto avviene dopo avere superato la prova scritta ed entro un anno da tale superamento.
La valutazione finale viene ottenuta tramite media pesata delle votazioni (in trentesimi) ottenute nelle due parti, con peso 50% per la prova scritta e 50% per il progetto. Entrambe le parti devono avere valutazione positiva.
Si ricorda che è necessario essere iscritti alle prove d'esame tramite segreterie online. Non ci saranno eccezioni al riguardo.
Non sono previste prove in itinere.
Orario di ricevimento
Il ricevimento con la prof.ssa Rizzi è in presenza e su appuntamento (scrivere una email a raffaella.rizzi@unimib.it)
Il ricevimento con il prof. Della Vedova è online e su appuntamento: https://www.unimib.it/gianluca-della-vedova
Aims
The student will know some fundamental problems and algorithms in bioinformatics. The student will be able to write small Python 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.
- Python programming in bioinformatics.
- File Formats used in bioinformatics.
Applied 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 Python programs for bioinformatics problems.
- write small pipelines that process bioinformatics data.
Independent Judgment
At the end of the course, the students will be able to interpret the results of a bioinformatics analysis.
Communication skills
At the end of the course, the students will be able to communicate the results of a bioinformatics analysis.
Learning skills
At the end of the course, the students will have developed the ability to:
- learn new libraries and software tools in bioinformatics.
- tackle new computational problems in genomics.
Contents
Fundamental problems and algorithms in bioinformatics. Pattern matching.Sequence Alignment. DNA sequencing. Evolutionary histories. Managing biological data (standard formats in Bioinformatics) and genomic databases.
Detailed program
- Introduction to genomic data: primary sequences of DNA, RNA, and protein sequences (standard FASTA format).
- Gene expression and alternative splicing (standard BED and GTF formats).
- Genome sequencing and sequencing data quality (standard FASTQ format).
- Global and local alignment of two sequences: Needleman–Wunsch, Smith–Waterman, and Gotoh algorithms.
- Semi-global alignment of two sequences.
- Banded alignment of two sequences.
- Multiple sequence alignment.
- Exact pattern matching: Rabin–Karp and Dömölki algorithms (shift-and paradigm).
- Text indexing: suffix trees, suffix arrays, and their applications to string problems (including exact pattern matching and longest common substring search).
- Genome assembly: overlap graphs and de Bruijn graphs.
- Evolutionary trees (phylogenetic trees). Character-based models: Gusfield’s algorithm for perfect phylogeny. Distance-based models: ultrametric and additive distances. UPGMA and Neighbor Joining algorithms. Introduction to maximum likelihood reconstruction.
- Genotypes and haplotypes. Distinction between a single individual and a pedigree.
- Introduction to Python.
- Pandas (data frame manipulation).
- Biopython.
Prerequisites
- Time and space complexity.
- Basic data structures: lists, arrays, search trees, dictionaries.
- Sorting algorithms: radix sort, merge sort.
- Memory hierarchy.
- Wiriting a short program, in any programming language.
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.
All activities are in-person and will be recorded but not streamed. The teaching language of this course is Italian. The activities will be:
- 36 hours of lectures, delivered in 2–3-hour sessions in unidirectional mode
- 24 lab activities, 2 hours each, with an initial part in unidirectional mode and a second part in interactive mode
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.
The book Think Python by A. B. Downey is used for introducing the Python language.
The Pandas library is covered in the book Python Data Science Handbook by VanderPlas.
Semester
Second semester
Assessment method
The assessment has a written exam and a project work.
The written exam is taken individually, on the algorithmic 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 competencies evaluated are: the ability to abstract a model, knowledge of the algorithms covered in the course, and the ability to analyze computational complexity.
The evaluation of the written exam is is graded out of thirty (30) based on the correctness and completeness of the answers, and on the ability to identify the essential elements of a topic.
The project work consists of devloping a Python program by a single student. Students can choose the topic of the project among alternatives proposed by the teacher at the end of the course.
The project will be discussed after the student has passed the written exam and within a year since the date of the written exam.
The final grade is obtained by weighting 50% of the degree (on a 30-point scale) of the written exam and 50% the project work, but you have to pass both parts. There are no in-progress written exams.
Beware that you must be registered via "segreterie online" to take the exam. If you are not registered, you will not allowed to take the exam. No exceptions will be made.
There will be no midterm assessments.
Office hours
Office hours with Professor Raffaella Rizzi will be held in person. Yoi can send an email to raffaella.rizzi@unimib.it.
Office hours with Professor Della Vedova will be held online. You can book a meeting at https://www.unimib.it/gianluca-della-vedova
Staff
-
Gianluca Della Vedova
-
Raffaella Rizzi