69443 - ALGORITHMS AND DATA STRUCTURES FOR COMPUTATIONAL BIOLOGY

Conoscenze e abilità da conseguire

At the end of the course, the student has the basic knowledge in design and analysis of correct and efficient algorithms and data structures. In particular, the student has basic knowledge on algorithms and data structures. The student will be able to: design correct and efficient algorithm for common computational tasks; analyze existing algorithms and data structures; design and analyze new algorithms and data structures.

Contenuti

Il corso è suddiviso in due parti principali, ognuna delle quali copre argomenti fondamentali di algoritmi e strutture dati.

Parte 1: Fondamenti degli Algoritmi e delle Strutture Dati

• Introduzione all'Analisi della Complessità degli Algoritmi: esploreremo il concetto di complessità computazionale, compresa la notazione asintotica.
• Algoritmi di Ordinamento: approfondiremo vari algoritmi di ordinamento come l'insertion sort, merge sort, quick sort e discuteremo i limiti inferiori degli ordinamenti basati su confronti. Inoltre, vedremo come ordinare in tempo lineare utilizzando counting sort e radix sort.
• Strutture Dati Elementari: acquisiremo una comprensione approfondita delle strutture dati fondamentali come array, liste concatenate, pile e code.
• Strutture Dati Avanzate: approfondiremo strutture dati più complesse come alberi binari, alberi generici, tabelle hash e grafi.
• Analisi dettagliata delle Strutture Dati integrate in Python: comprenderemo il funzionamento interno delle strutture dati integrate in Python.
• Tecniche Algoritmiche: esploreremo paradigmi algoritmici essenziali, tra cui brute force, divide-et-impera, programmazione dinamica e algoritmi greedy.
• Gestione di Problemi Hard: studieremo approcci algoritmici per problemi complessi, come algoritmi di approssimazione, branch-and-bound ed algoritmi euristici.

Parte 2: Algoritmi e Strutture Dati per la Biologia Computazionale

• String matching esatto e approssimato: impareremo tecniche per confrontare stringhe in modo esatto o con un certo grado di flessibilità.
• Allineamento di Sequenze: approfondiremo tecniche algoritmiche per  gli allineamenti locali e globali tra coppie di sequenze, così come per l'allineamento multiplo di sequenze.
• Strutture Dati di tipo Suffix: discuteremo suffix tree, suffix trie e suffix array, che giocano un ruolo fondamentale nello sviluppo di algoritmi per l'analisi di stringhe.
• Burrows-Wheeler Transform: esploreremo la tecnica nota come Burrows-Wheeler Transform, una trasformazione reversibile per stringhe che ha diverse applicazioni nella biologia computazionale.
• Sequence assembly: vedremo come approcciare il problema Hard noto come de-novo assembly per sequenze genomiche utilizzando gli overlap graph e algoritmi greedy.

Durante il corso, gli algoritmi verranno presentati con l'ausilio di pseudocodice e verranno fornite anche concrete implementazioni in Python.

Testi/Bibliografia

È fondamentale fare riferimento al materiale elettronico (slide con nozioni teoriche ed esercizi svolti) fornito durante il corso. Tale materiale sarà disponibile sulla pagina web del corso.

I libri di testo indicati sotto sono consigliati ma non necessari.

Testi specifici per la biologia computazionale:

- Carlos Setubal, Joao Meidanis, Introduction to computational molecular biology, Cengage Learning eds., 1997;
- C. Gibas, P. Jambeck, Developing Bioinformatics Computer Skills, O'Reilly media, 2001

Testi più generali su algoritmi e strutture dati: 

- Alfred V. Aho, Jeffrey D. Ullman, John E. Hopcroft. Data Structures and Algorithms. Addison Wesley, 1983.
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms. McGraw-Hill, 2001.
- Donald E. Knuth. The Art of Computer Programming, Volumes 1-3. Addison-Wesley Professional, 1998.
- S.B. Kishor Data Structures, Edition 3. Das Ganu Prakashan, Nagpur, 2008.

Metodi didattici

Il metodo didattico consiste di lezioni frontali (supportate da slide e lavagna) e risoluzione di tipologie di esercizi che potrebbero essere richiesti in sede d’esame

Modalità di verifica e valutazione dell'apprendimento

La prova finale è composta da una parte scritta (3 ore) ed eventualmente da un orale (30 minuti). Durante la prova scritta non è possibile usare appunti o libri. La prova orale viene richiesta dal docente solo nel caso in cui la prova scritta abbia ottenuto una valutazione vicina al 18/30

Strumenti a supporto della didattica

Slide in formato elettronico e proiettore.
Personal computer.
Lavagna

Orario di ricevimento

Consulta il sito web di Pietro Di Lena