Fundamental algorithms for bioinformatics (2020/2021)



Codice insegnamento
4S004550
Crediti
12
Coordinatore
Zsuzsanna Liptak
Altri corsi di studio in cui è offerto
Altri corsi di studio in cui è offerto
    Settore disciplinare
    INF/01 - INFORMATICA
    Lingua di erogazione
    Inglese
    L'insegnamento è organizzato come segue:
    Attività Crediti Periodo Docenti Orario
    Algorithm design 6 I semestre Ferdinando Cicalese, Zsuzsanna Liptak

    Vai all'orario delle lezioni

    Bioinformatics algorithms 6 II semestre Zsuzsanna Liptak

    Vai all'orario delle lezioni

    Obiettivi formativi

    Il corso permetterà agli studenti di acquisire un bagaglio di strumenti analitici avanzati alla base delle soluzioni algoritmiche di problemi fondamentali in bioinformatica. Conoscenza e capacità di comprensione Fornire le conoscenze e le competenze necessarie per l'analisi e la progettazione di soluzioni algoritmiche a problemi fondamentali in bioinformatica. Conoscenze applicate e capacità di comprensione Capacità di progettare soluzioni algoritmiche per problemi tipici di bionformatica e biologia computazionale, quali l'analisi di sequenze omiche. Autonomia di giudizio Capacità di individuare le componenti strutturali critiche e quindi gli approcci più idonei nel trattamento di problemi complessi di bioinformatica. Abilità comunicative Capacità di descrivere con l'adeguata precisione e chiarezza un problema bioinformatico, la sua modellizzazione e la soluzione associata sia ad interlocutori esperti che in contesti meno specialistici e multidisciplinari. Capacità di apprendere Capacità di ampliare le proprie conoscenze in ambito bioinformatico anche in maniera autonoma, utilizzando le nozioni apprese per leggere comprendere ed eventualmente rielaborare autonomamente articoli e testi scientifici di livello avanzato.

    Programma

    ------------------------
    MM: Algorithm design
    ------------------------
    1. Concetti di base di analisi degli algoritmi e complessità: ricapitolazione di algoritmi per la visita di grafi; problemi di cammini minimi; alberi minimi ricoprenti; elementi di teoria della complessità computazionale e NP-completezza. 2. Modelli di Genome Rearrangement: (i) algoritmi di approssimazione per modelli basati su inversioni (permutazioni senza segno); (ii) il modello DCJ; (iii) algoritmi di approssimazione per la "Synteny Distance". 3. Modelli per DNA assembly: (i) Il problema della superstringa più corta (SCS), relazioni con il problema del max-cost TSP, approssimazione della massimia compressione mediante matching pesato in grafi bipartiti; (ii) Assembly mediate cicli Euleriani; algoritmi efficienti per costruire cicli e cammini Euleriani. 4. Misure di distanza tra sequenza biologiche: (i) edit distance, (ii) LCS-distance, (iii) q-gram distance, (iv) possibilmente ulteriori distanze. 5. Introduzione di strutture dati per sequenze genomiche: (i) cenni di suffix tree e suffix array, (ii) qualche applicazione.
    ------------------------
    MM: Bioinformatics algorithms
    ------------------------
    1. Confronto di coppie di sequenze: (i) Allineamento di coppie di sequenze (globale, locale); (ii) varianti: allineamento ottimale in spazio lineare, allineamento semiglobale, affine gap penalties; (iii) similarità vs. distanza; (iv) allineamento di coppie di sequenze in pratica: dotplot, BLAST, matrici di punteggio 2. Allineamento di sequenze multiple: (i) Soluzione esatta DP; (ii) Riduzione dello spazio di ricerca con il metodo Carillo-Lipman; (iii) approssimazioni, euristiche 3. RNA secondary structure prediction 4. Riconstruzione filogenetica: (i) dati di tipo distanza: alberi ultrametrici e UPGMA; (ii) dati di tipo distanza: alberi additivi e Neighbor Joining; (iii) dati di tipo carattere: Filogenetica perfetta (PP); (iv) dati di tipo carattere: Small Parsimony (Fitch' algorithm); (v) dati di tipo carattere: euristiche per Large Parsimony

    Modalità d'esame

    ------------------------
    MM: Algorithm design
    ------------------------
    L'esame è volto ad accertare che gli studenti abbiano acquisito padronanza delle tecniche fondamentali per l'analisi e la progettazione di algoritmi e che conoscano il loro utilizzo per la soluzione di alcuni problemi computazionali classici in bioinformatica. Per il superamento dell'esame è necessario sostenere una prova scritta con quesiti aperti e/o a risposta multipla. Tali esercizi verificano le conoscenze relative all'analisi di algoritmi e alle soluzioni di problemi classici analizzati durante il corso e la capacità dello studente di modellare un nuovo problema e progettare e descrivere una soluzione algoritmica. Se si consegue un risultato superiore a 25 nella prova scritta è necessario sostenere un colloquio orale. Il voto finale per l'intero esame di "Fundamental Algorithms for Bioinformatics" è dato dalla media aritmetica dei voti conseguiti nei due moduli.
    ------------------------
    MM: Bioinformatics algorithms
    ------------------------
    Per il superamento dell'esame è necessario sostenere una prova scritta. Se si consegue un risultato superiore a 25 nella prova scritta è necessario sostenere un colloquio orale. La prova scritta include domande teoriche (problemi visti a lezione; analisi di algoritmi visti a lezione; proprietà matematiche di tali problemi e algoritmi; quali algoritmi esistono per un dato problema, etc), ed applicazione di algoritmi a problemi concreti (calcolo di un allineamento mediante l'algoritmo DP, etc). Nel colloquio orale, gli studenti dovranno anche dettagliare le soluzioni presentate nella prova scritta, e dimostrare padronanza delle conoscenze acquisite. Il voto finale per l'intero esame di "Fundamental Algorithms for Bioinformatics" è dato dalla media aritmetica dei voti conseguiti nei due moduli. Gli studenti del Masters in Molecular e medical biotechnology sostengono una prova con quesiti differenti. Non sono previsti esami diversi per studenti frequentanti e no.

    Testi di riferimento
    Attività Autore Titolo Casa editrice Anno ISBN Note
    Algorithm design H.J. Böckenhauer, D. Bongartz Algorithmic Aspects of Bioinformatics Springer 2007
    Algorithm design Enno Ohlebusch Bioinformatics Algorithms 2013 978-3-00-041316-2
    Algorithm design Stein, Drysdale, Bogart Discrete Mathematics for Computer Scientists Pearson 2011 978-0-13-137710-3
    Algorithm design V. Mäkinen, D. Belazzougui, F. Cunial, and A.I. Tomescu Genome Scale Algorithm Design (Edizione 1) Cambridge University Press 2015 ISBN 978-1-107-07853-6
    Algorithm design J.C. Setubal, J. Meidanis Introduction to Computational Biology Pws Pub Co 1997
    Bioinformatics algorithms H.J. Böckenhauer, D. Bongartz Algorithmic Aspects of Bioinformatics Springer 2007
    Bioinformatics algorithms Enno Ohlebusch Bioinformatics Algorithms 2013 978-3-00-041316-2
    Bioinformatics algorithms V. Mäkinen, D. Belazzougui, F. Cunial, and A.I. Tomescu Genome Scale Algorithm Design (Edizione 1) Cambridge University Press 2015 ISBN 978-1-107-07853-6
    Bioinformatics algorithms Joao Setubal and Joao Meidanis Introduction to Computational Biology 1997