Programma

  1. Introduzione agli algoritmi

    La nozione di algoritmo. Dagli algoritmi ai programmi: le strutture di controllo fondamentali (sequenza, selezione e iterazione); variabili e assegnamenti.
    Il tempo e lo spazio: introduzione alla complessità degli algoritmi e alla classificazione dei problemi. La nozione di problema NP-completo.
    Tecniche fondamentali per lo sviluppo di algoritmi: divide-et-impera, programmazione dinamica, ricerca locale. Nozioni e problemi di stringhe e grafi.

  2. Problemi di Biologia Computazionale Molecolare

    Allineamento di sequenze nucleotidiche e proteiche:
    • algoritmi di confronto fra due sequenze (allineamento locale, globale e semiglobale);
    • algoritmi di confronto fra più sequenze (allineamento multiplo);
    • metodi euristici e cenni ai programmi di allineamento (BLAST, FASTA, ALIGN, ClustalW).
    Metodi e modelli per la previsione di strutture molecolari:
    • la struttura secondaria di molecole di RNA;
    • il problema dell'avvolgimento delle proteine e tecniche di soluzione (protein threading, modelli reticolari e algoritmi genetici).
    DNA Computing:
    • l'esperimento di L. Adleman per la soluzione di problemi intrattabili tramite uso di molecole di DNA.