UNIVERSITA DI MILANO-BICOCCA LAUREA MAGISTRALE IN BIOINFORMATICA Corso di BIOINFORMATICA: TECNICHE...

UNIVERSITA’ DI MILANO-BICOCCAUNIVERSITA’ DI MILANO-BICOCCALAUREA MAGISTRALE IN LAUREA MAGISTRALE IN

BIOINFORMATICABIOINFORMATICA

Corso di

BIOINFORMATICA: TECNICHE DI BASE

Prof. Giancarlo Mauri

Lezione 1-2

Introduzione agli algoritmi

2

Informatica e biologia

FISICAFISICA

XXI Secolo

BIOLOGIABIOLOGIA

INFORMATICAINFORMATICA

INFORMATICAINFORMATICA

XX Secolo

3

Informatica e biologia: amore o interesse?

Biologia

Informatica

Bioinspired computing:

Reti neurali

Progr. evolutiva

DNA Computing

Ant computing

…

Bioinformatica:

Databases di sequenze

Analisi di sequenze

Folding di Proteine

Simulazione di processi biologici

…

4

Perché la bioinformatica?

QuickTime™ and aTIFF (Uncompressed) decompressorare needed to see this picture.QuickTime™ and a

TIFF (Uncompressed) decompressorare needed to see this picture.

QuickTime™ and aTIFF (Uncompressed) decompressor

are needed to see this picture.



“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







6

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

7

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

8

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

9

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

10

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

11

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

12

Il gergo

…DEL BIOLOGO MOLECOLARE

NucleotidiNucleotidi Lettere, Simboli Lettere, Simboli

…DELL’INFORMATICO

SequenzeSequenze Stringhe, Parole Stringhe, Parole

OligonucleotidiOligonucleotidi Motivi Motivi

ProgrammiProgrammi Algoritmi Algoritmi

MutazioniMutazioni Mismatches Mismatches

13

Gli algoritmi

AlgoritmoAlgoritmo

(dal nome del matematico persiano Mohammed ibn-Musa al-Khowarismi - IX secolo d.C.)

SuccessioneSuccessione

finita

non ambigua

deterministica

eseguibile

di istruzioni la cui esecuzione permette di portare a termine un compito assegnato o di risolvere un problema

14

Gli algoritmi

L’algoritmo deve essere

comprensibile al suo esecutore

corretto

efficiente

Dati inizialiDati iniziali

ManipolazioneManipolazione(algoritmo)(algoritmo)

RisultatiRisultati

15

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

16

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

Dato un problema decidibile P, esiste almeno un buon algoritmo di soluzione per P?

Che consuma poche “risorse”

17

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à

18


Algoritmo A1

Problema: calcolo di an Algoritmo A2

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;

endend

begin x:=1;z:=n;while z > 0 dobegin

x:=x*a;z:=z-1;

endend

19

n = bi ⋅2i−1

i=1

log2n

∑

e la proprietà delle potenze

ak+j = akaj


A1 sfrutta la definizione di potenza come iterazione del prodotto

A2 sfrutta la rappresentazione binaria di n

20


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

21


Analisi di A1

Conteggio delle operazioni aritmetiche nel caso peggiore

Tp1(n) = 2

z≠0∑ =2n

begin x:=1;z:=n;while z > 0 do begin x:=x*a; z:=z-1; end

endNB: Ogni esecuzione di repeatdecrementa z di 1 => n esecuzioniper avere z=0

NB: Ogni esecuzione di repeatdecrementa z di 1 => n esecuzioniper avere z=0

22


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;

endend

Tp2(n) = 4=4([log2

z ≠0∑ n]+1)

NB: ogni esecuzione dimezza z =>[log n ]+1 esecuzioni per avere z=0

NB: ogni esecuzione dimezza z =>[log n ]+1 esecuzioni per avere z=0

23


Confronto di efficienza tra A1 e A2

Per n < 8, è più efficiente A1

Per n > 8 , è più efficiente A2

24


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)

25


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 3 106 a.

2n 1’’ 35 a. 3 106 a.

3n 58’ 2 1011 a.

1 operazione ≡ 10 –6 secondi

26


I problemi si possono dividere in

trattabilihanno almeno un algoritmo di soluzione di complessità polinomiale

intrattabilinon hanno algoritmi di soluzione di complessità polinomiale

27

Un po’ di gergo

Def: Problema di decisione Def: Problema di decisione L’output di è YES o NO

nella classe Pnella classe P risolto da un algoritmo polinomiale (efficiente in tempo)

nella classe NPnella classe NPSi verifica, tramite un certificato, in tempo polinomiale se una istanza di ammette risposta YES

NP-CompletoNP-CompletoOgni altro problema in NP può essere risolto tramite un algoritmo polinomiale che risolve , e è nella classe NP

28

Un po’ di gergo

Def: Problema di ottimizzazione Def: Problema di ottimizzazione 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 Algoritmo di approssimazione per Un algoritmo A è di approssimazione per , se per ogni input I di , A produce in tempo polinomiale una soluzione S tale che il valore della funzione costo c su S verifichi la relazione:

c(S) ≤ (|I|) x OPTP(I) ( ≥ 1)

Esempio: algoritmo 2-approssimante se =2

UNIVERSITA DI MILANO-BICOCCA LAUREA MAGISTRALE IN BIOINFORMATICA Corso di BIOINFORMATICA: TECNICHE...

Documents

Transcript of UNIVERSITA DI MILANO-BICOCCA LAUREA MAGISTRALE IN BIOINFORMATICA Corso di BIOINFORMATICA: TECNICHE...