Fundamental algorithms for bioinformatics (2016/2017)



Codice insegnamento
4S004550
Crediti
12
Coordinatore
Ferdinando Cicalese
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
    Algorithm design 6 I sem. Ferdinando Cicalese
    Bioinformatics algorithms 6 II sem. Zsuzsanna Liptak

    Orario lezioni

    I sem.
    Attività Giorno Ora Tipo Luogo Note
    Algorithm design martedì 8.30 - 10.30 lezione Aula G  
    Algorithm design giovedì 10.30 - 12.30 lezione Aula G dal 3-ott-2016  al 7-ott-2016
    Algorithm design giovedì 10.30 - 12.30 lezione Aula G dal 12-nov-2016  al 31-gen-2017
    Algorithm design giovedì 10.30 - 12.30 lezione Sala Verde dal 10-ott-2016  al 11-nov-2016
    II sem.
    Attività Giorno Ora Tipo Luogo Note
    Bioinformatics algorithms lunedì 11.30 - 13.30 lezione Aula G dal 11-mar-2017  al 9-giu-2017
    Bioinformatics algorithms lunedì 14.30 - 16.30 lezione Aula C dal 8-mag-2017  al 5-giu-2017
    Bioinformatics algorithms giovedì 8.30 - 10.30 lezione Aula G dal 9-mar-2017  al 9-giu-2017

    Obiettivi formativi

    ------------------------
    MM: Algorithm design
    ------------------------
    Scopo del corso è fornire le competenze necessarie per l'analisi e la progettazione di soluzioni algoritmiche a problemi fondamentali in bioinformatica. Il modulo "Algorithm Design" sarà dedicato ai principi fondamentali della progettazione di algoritmi "avanzati", esemplificati dalle soluzioni a problemi classici in bioiformatica. Con riferimento agli obiettivi del percorso formativo del CdS il corso permetterà agli studenti di acquisire: un bagaglio di strumenti avanzati per affrontare problemi non banali nel settore della bioinformatica; la capacità di progettare soluzioni algoritmiche per problemi tipici della analisi dei genomi; la capacità di individuare le componenti strutturali critiche e quindi gli approcci più idonei nel trattamento di problemi complessi di bioinformatica.
    ------------------------
    MM: Bioinformatics algorithms
    ------------------------
    Scopo di questo modulo è acquisire conoscenza delle soluzioni a problemi algoritmici fondamentali che sono alla base di applicazioni in bioinformatica (allineamento di sequence, similarità tra sequenze, assemblaggio di sequenze, RNA-folding).

    Programma

    ------------------------
    MM: Algorithm design
    ------------------------
    Ricapitolazione di: concetti di base di analisi degli algoritmi; algoritmi per la visita di grafi; cammini minimi; alberi minimi ricoprenti; programmazione dinamica. Elementi di teoria della complessità computazionale e NP-completezza. Modelli di "Genome Rearrangement": algoritmo esatto per l'ordinamento di permutazini con segno; (ii) algoritmi di approssimazione per l'ordinamento di permutazioni senza segno; arossimazione della "Synteny Distance". Problemi computazionali su grafi: (i) Cicli Hamiltoniani e Cicli Euleriani; algoritmi polinomiali per problemi Euleriani; il problema del commesso viaggiatore (TSP) e sue relazioni col problema del ciclo hamiltoniano; inapprossimabilità di TSP e 2-approssimazine per le istanze metriche. Modelli per"Physical Map": (i) algoritmo efficiente per il problema degli uni consecutivi in una matrice (C1P); (ii) approssimazione per il problema della minimizzazione dei gap basato su TSP metrico. Modelli per "DNA assembly: Il problema della superstringa più corta; approssimazione basata sulla massimizzazione della compressione, mediante coperture di un grafo e matching pesato in grafi bipartiti. Reti di Flusso: problemi di massimo flusso e minimo taglio; matching massimo in grafi bipartiti; scomposizione del flusso in cammini disgiunti; perfect matching di massimo/minimo peso in grafi bipartiti pesati. Modelli per Motif Finding: (i) il problema della stringa consenso; (ii) Schemi di approssimazione polinomiale Modelli per "Haplotyping": algorithmi per il problema dell'haplotyping per un singolo individuo su dati senza gap; estensioni e parametrizzazione per il caso con gap.
    ------------------------
    MM: Bioinformatics algorithms
    ------------------------
    Il seguente è un sommario dei principali argomenti trattati in questo modulo: * Introduzione Parte I: Confronto di coppie di sequenze * Allineamento di coppie di sequenze * Distanza tra stringhe * Allineamento di coppie di sequence in pratica: BLAST, matrici di "score" Parte II: Allineamento di più sequenze * Soluzione esatta DP * Riduzione dello spazio di ricerca con il metodo Carillo-Lipman * approssimazione, euristiche Parte III: RNA folding * Algoritmi di Nussinov e Zuker, * approssimazione Parte IV: Algoritmi per "sequence assembly" * Shotgun sequencing: SCS e altri modelli * Sequenziamento mediante ibridazione e NGS: grafi di de Bruijn graphs, tour euleriani

    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. L'esame consiste in una prova scritta con quesiti aperti. Tipicamente la prova include alcuni esercizi obbligatori ed altri esercizi a scelta. Gli esercizi obbligatori verificano le conoscenze relative all'analisi di algoritmi e alle soluzioni di problemi classici analizzati durante il corso; gli esercizi a scelta verificano la capacità dello studente di modellare un nuovo problema e progettarne una soluzione algoritmica. Al voto finale per il modulo Algorithm Design concorre la soluzione di esercizi periodici assegnati durante il corso. 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
    ------------------------
    Una prova scritta, seguita da una orale. Il superamento della prova scritta è prerequisito necessario al sostenimento dell'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 per la prova scritta, e dimostrare padronanza delle conoscenze acquisite. Gli studenti del Masters in Molecular e medical biotechnology sostengono una prova con quesiti differenti.

    Testi di riferimento
    Attività Autore Titolo Casa editrice Anno ISBN Note
    Algorithm design J. Kleinberg, É. Tardos Algorithm Design (Edizione 1) Addison Wesley 2006 978-0321295354
    Algorithm design H.J. Böckenhauer, D. Bongartz Algorithmic Aspects of Bioinformatics Springer 2007
    Algorithm design Neil C. Jones, Pavel A. Pevzner An introduction to bioinformatics algorithms (Edizione 1) MIT Press 2004 0-262-10106-8
    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
    Bioinformatics algorithms Joao Setubal and Joao Meidanis Introduction to Computational Biology 1997

    Opinione studenti frequentanti - 2015/2016


    Statistiche per i requisiti di trasparenza (Attuazione Art. 2 del D.M. 31/10/2007, n. 544)

    I dati relativi all'AA 2016/2017 non sono ancora disponibili