UNIVERSITA’ DI MILANO-BICOCCA LAUREA MAGISTRALE IN BIOINFORMATICA Corso di BIOINFORMATICA: TECNICHE DI BASE Prof. Giancarlo Mauri Lezione 1-2 Introduzione agli algoritmi Informatica e biologia XX Secolo FISICA INFORMATICA XXI Secolo INFORMATICA BIOLOGIA 2 Informatica e biologia: amore o interesse? Bioinformatica: Biologia Databases di sequenze Bioinspired computing: Analisi di sequenze Reti neurali Folding di Proteine Progr. evolutiva Simulazione di processi biologici DNA Computing Ant computing … … Informatica 3 Perché la bioinformatica? 4 QuickTime™ and a TIFF (Uncompressed) decompressor are needed to see this picture. QuickTime™ and a TIF F (Uncompressed) decompressor are needed to see this picture. QuickTi me™ a nd a TIFF (Uncompre ssed ) decomp resso r are need ed to se e th is p icture. Qu i c k T i m e ™ a n d a TIF F (Un c o m p re s s e d ) d e c o m p re s s o r a re n e e d e d to s e e th i s p i c tu re . “Every attempt to employ mathematical methods in the study of biological questions must be considered profoundly irrational and contrary to the spirit of biology.” “If mathematical analysis should ever hold a prominent place in biology – an aberration which is happily almost impossible – it would occasion a rapid and widespread degeneration of that science.” Auguste Comte, Pilosophie Positive, 1830 QuickTime™ and a TIFF (Uncompressed) decompressor are needed to see this picture. QuickTime™ and a TIFF (Uncompressed) decompressor are needed to see this picture. QuickTi me™ a nd a TIFF (Uncompre ssed ) decomp resso r are need ed to se e th is p icture. Perché i computer in biologia Le esigenze: Gestione di grandi banche dati di sequenze non omogenee distribuite e accessibili via rete Analisi dei dati (data mining) Gli obiettivi: Ricerca Genomica comparata Genomica funzionale Proteomica … Riduzione del “time to market” per l’industria farmaceutica 6 Le fasi Generare i dati Assemblaggio dei frammenti di DNA Estrarre un significato dai dati Capire la struttura del DNA nel nucleo (identificazione di geni) Capire come questa struttura governa la trascrizione del DNA Capire l’espressione genica Capire l’evoluzione Capire le proteine Predizione della struttura delle proteine 7 Le fasi Usare la conoscenza Riparazione o sostituzione dei geni Progettazione di farmaci con un reale impatto sulla malattia senza alterare il delicato equilibrio dell’organismo 8 Livelli di Astrazione Sequenze Motivi Geni e genoma Evoluzione - Alberi filogenetici Espressione Tecniche per l’analisi di dati da microarrays Proteoma Struttura e funzione delle proteine Sistema Reti regolatorie Feedback e controllo 9 Le principali sfide computazionali Assemblaggio di sequenze Analisi di sequenze Mappaggio dei geni Confronto di sequenze (allineamento …) Ricerca di segnali Memorizzazione e recupero dell’informazione Organizzazione di dati di espressione genica Ricostruzione di alberi evolutivi Classificazione delle proteine Inferenza di reti regolatorie 10 Tecniche algoritmiche Il software per la bioinformatica richiede tecniche algoritmiche sofisticate programmazione dinamica algoritmi probabilistici/approssimati data mining algoritmi di apprendimento gestione di “Very Large DataBases” progetto di GUI ottimizzazione combinatoria inferenza statistica ……. 11 Il gergo …DEL BIOLOGO MOLECOLARE …DELL’INFORMATICO Nucleotidi Lettere, Simboli Sequenze Stringhe, Parole Oligonucleotidi Motivi Programmi Algoritmi Mutazioni Mismatches 12 Gli algoritmi Algoritmo (dal nome del matematico persiano Mohammed ibn-Musa alKhowarismi - IX secolo d.C.) Successione finita non ambigua deterministica eseguibile di istruzioni la cui esecuzione permette di portare a termine un compito assegnato o di risolvere un problema 13 Gli algoritmi L’algoritmo deve essere Dati iniziali comprensibile al suo esecutore corretto Manipolazione (algoritmo) efficiente Risultati 14 Gli algoritmi Esempi di problemi Calcolare la potenza n-esima di a Disporre in ordine crescente n interi assegnati Stabilire se, data una formula del calcolo proposizionale con n variabili, esiste una n-upla di valori booleani che la renda vera Stabilire se un polinomio in n variabili a coefficienti interi ammette radici intere 15 Gli algoritmi Questione logica Dato un problema P, esiste almeno un algoritmo di soluzione di P? Esempio di problema indecidibile: 10° problema di Hilbert Questione Computazionale Che consuma poche “risorse” Dato un problema decidibile P, esiste almeno un buon algoritmo di soluzione per P? 16 Complessità degli algoritmi Quanto costa risolvere un problema? Analisi degli Algoritmi E’ possibile diminuire questo costo? Disegno di algoritmi efficienti Determinazione di estremi inferiori di complessità 17 Complessità degli algoritmi Problema: calcolo di an Algoritmo A2 Algoritmo A1 begin x:=1; z:=n; while z > 0 do begin x:=x*a; z:=z-1; end end begin x:=a; y:=1; u:=0; z:=n; while z > 0 do begin u:=z mod 2; z:=z div 2; if u = 1 then y:=x*y; x:=x*x; end end 18 Complessità degli algoritmi A1 sfrutta la definizione di potenza come iterazione del prodotto A2 sfrutta la rappresentazione binaria di n n log 2 n bi 2 i1 i1 e la proprietà delle potenze ak+j = akaj 19 Complessità degli algoritmi Il confronto di efficienza tra A1 e A2 avviene scegliendo: il criterio di confronto Tempo di computazione Occupazione di memoria il metodo di confronto Empirico: tempo di calcolo su macchina reale che dipende da macchina dati iniziali Ideale: numero di istruzioni eseguite in funzione della dimensione dei dati iniziali 20 Complessità degli algoritmi Analisi di A1 Conteggio delle operazioni aritmetiche nel caso peggiore begin x:=1; z:=n; while z > 0 do begin x:=x*a; z:=z-1; end end Tp1 (n) 2 2n z0 NB: Ogni esecuzione di repeat decrementa z di 1 => n esecuzioni per avere z=0 21 Complessità degli algoritmi Analisi di A2 Conteggio delle operazioni aritmetiche nel caso peggiore begin x:=a; y:=1; u:=0; z:=n; while z > 0 do begin u:=z mod 2; z:=z div 2; if u = 1 then y := x * y; x:=x*x; end end Tp (n) 4 4([log 2 n] 1) 2 z0 NB: ogni esecuzione dimezza z => [log n ]+1 esecuzioni per avere z=0 22 Complessità degli algoritmi Confronto di efficienza tra A1 e A2 Per n < 8, è più efficiente A1 Per n > 8 , è più efficiente A2 23 Complessità degli algoritmi L’efficienza di un algoritmo è misurata dalla complessità in tempo e spazio La complessità è funzione della dimensione dell’input n O(nk): tempo polinomiale rispetto alla dimensione dell’input (fattibile) O(kn): tempo esponenziale rispetto alla dimensione dell’input (infattibile) 24 Complessità degli algoritmi Dim. Comp. 20 50 100 200 500 1000 1000n 0,02’’ 0,05’’ 0,1’’ 0,2’’ 0,5’’ 1’’ 1000 nlogn 0,09’’ 0,3’’ 0,6’’ 1,5’’ 4,5’’ 10’ 100 n2 0,04’’ 0,25’’ 1’’ 4’’ 25’’ 2’ 10 n3 0,02’’ 1’’ 10’’ 1’’ 21’ 2,7 h. nlogn 0,4’’ 1,1 h. 220 g. 125 102 a. 5 1010 a. 2n/3 0,0001” 0,1’’ 2,7 h 2n 1’’ 35 a. 3 106 a. 3n 58’ 2 1011 a. 3 106 a. 1 operazione 10 –6 secondi 25 Complessità degli algoritmi I problemi si possono dividere in trattabili hanno almeno un algoritmo di soluzione di complessità polinomiale intrattabili non hanno algoritmi di soluzione di complessità polinomiale 26 Un po’ di gergo Def: Problema di decisione P L’output di P è YES o NO P nella classe P P risolto da un algoritmo polinomiale (efficiente in tempo) P nella classe NP Si verifica, tramite un certificato, in tempo polinomiale se una istanza di P ammette risposta YES P NP-Completo Ogni altro problema in NP può essere risolto tramite un algoritmo polinomiale che risolve P, e P è nella classe NP 27 Un po’ di gergo Def: Problema di ottimizzazione P Tra l’insieme delle soluzioni possibili, si sceglie quella di costo minimo (o di beneficio massimo). Esempio: allineamento di minimo costo tra due sequenze Algoritmo di approssimazione per P Un algoritmo A è di approssimazione per P, se per ogni input I di P, A produce in tempo polinomiale una soluzione S tale che il valore della funzione costo c su S verifichi la relazione: c(S) ≤ r(|I|) x OPTP(I) (r ≥ 1) Esempio: algoritmo 2-approssimante se r=2 28