B5782 - ALGORITHMS AND DATA STRUCTURES FOR COMPUTATIONAL BIOLOGY

Conoscenze e abilità da conseguire

Al termine del corso, lo studente ha le conoscenze di base nella progettazione e analisi di algoritmi e strutture dati corretti ed efficienti. In particolare, lo studente ha conoscenze di base su algoritmi e strutture dati. Lo studente sarà in grado di: progettare algoritmi corretti ed efficienti per comuni attività computazionali; analizzare algoritmi e strutture dati esistenti; progettare e analizzare nuovi algoritmi e strutture dati.

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.
  
• 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

L'esame finale consiste in una prova scritta della durata di 3 ore e comprende sei esercizi che coprono l'intero contenuto del corso. In particolare, almeno due esercizi saranno basati sulla Parte 2 del corso, mentre i restanti riguarderanno la Parte 1. Tra i sei esercizi, almeno uno sarà dedicato all’analisi della complessità computazionale e almeno uno riguarderà la programmazione.

Ogni esercizio vale 5 punti. Inoltre, 2 punti bonus saranno assegnati all’esercizio più impegnativo oppure suddivisi tra i due esercizi più difficili. Il punteggio massimo raggiungibile è 32 punti. La lode può essere assegnata solo agli studenti che ottengono un punteggio superiore a 30.

Durante la prova scritta è severamente vietato l’uso di libri, appunti o qualsiasi altro materiale di consultazione.

 

Studenti/sse con DSA o disabilità temporanee o permanenti: si raccomanda di contattare per tempo l’Ufficio di Ateneo competente (https://site.unibo.it/studenti-con-disabilita-e-dsa/it). Sarà sua cura proporre agli/lle studenti/sse interessati/e eventuali adattamenti, che dovranno comunque essere sottoposti, con almeno 15 giorni di anticipo, all’approvazione del/della docente, il/la quale ne valuterà l'opportunità anche in relazione agli obiettivi formativi dell’insegnamento.

Strumenti a supporto della didattica

• Slide in formato elettronico e proiettore
• Personal computer
• Tablet
• Lavagna

Orario di ricevimento

Consulta il sito web di Pietro Di Lena