Informatica per biotecnologia

REPEAT UNTIL

Sintassi = come si Semantica = significato

scrive l’istruzione viene sempre eseguita almeno

REPEAT una volta perché la condizione è valutata

istruzione in seguito; se la condizione risulta falsa,

l’istruzione viene eseguita nuovamente

UNTIL L’iterazione termina quando la condizione

condizione risulta vera 10

Alice Giussani massimo comun

:

WHILE DO

Sintassi = come si Semantica = significato

scrive

WHILE l’istruzione potrebbe non essere mai eseguita perché la condizione viene

valutata subito

condizione Se la condizione risulta vera, allora viene eseguita l’istruzione L’iterazione

DO termina quando la condizione risulta falsa (la condizione viene valutata

ogni volta dopo l’esecuzione dell’istruzione)

istruzione

Complessità computazionale

Dato un problema, è possibile definire più algoritmi per trovare una soluzione.

Bisogna scegliere quello che sfrutta al meglio le «risorse del computer», che definiamo in termini

di: • Tempo di calcolo

• Spazio di memoria

Il tempo di calcolo non è quello fisico (secondi, minuti) poiché dipenderebbe dal computer, ma è

determinato dal numero delle istruzioni che vengono eseguite dato un certo input.

Vogliamo quindi misurare la complessità di un algoritmo indipendentemente dalla sua

implementazione o dal computer sul quale viene eseguito.

• Quando si calcola la complessità computazionale bisogna analizzare il comportamento

asintotico Il numero di passaggi è approssimabile al

Complessità lineare O(n) numero di dati in input

Se raddoppia il numero in input, il tempo

2

n ¿

Complessità quadratica O( di calcolo necessario per completare

l’algoritmo è di 4 volte tanto

Qualsiasi input corrisponde allo stesso

Complessità lineare O(1) numero di passaggi

La complessità di un algoritmo va calcolata considerando il caso peggiore

Complessità ed efficienza

Algoritmo efficiente

Diciamo che un algoritmo è efficiente se la sua complessità è costante (1) oppure lineare (n), o

poco superiore (nlogn) 11

Alice Giussani k

n

Se La sua complessità è polinomiale ( ) l’efficienza dipende :

• Per bassi valori di k (2  k < 3) l’algoritmo è applicabile per dimensioni medie dell’input con

in un tempo (fisico) di calcolo ragionevole

• Se k  3, la dimensione dell’input processabile si riduce drasticamente e i tempi (fisici) di

calcolo diventano inaccettabili

Algoritmo inefficiente n

a

Diciamo che un algoritmo è inefficiente se la sua complessità è esponenziale  i tempi (fisici)

di calcolo sono proibitivi anche per input di dimensioni piccole

Classificazione dei problemi

Facili Problemi per cui esistono algoritmi efficienti

Intrattabili Problemi che non possono essere risolti mediante nessun algoritmo efficiente

NP-completi Problemi per i quali non sono stati trovati algoritmi efficienti ma, allo stesso

tempo, non c’è certezza che tali algoritmi non esistano

I problemi NP-completi sono problemi non deterministici polinomiali

DNA Computing

Nel 1994 Leonard Adleman effettua il primo esperimento di calcolo, usando molecole di DNA e

reazioni biochimiche. La struttura delle molecole di DNA viene usata per codificare i dati del

problema da risolvere e le reazioni biochimiche sul DNA costituiscono l’implementazione

molecolare dell’algoritmo per la risoluzione del problema

Operazioni sul DNA

• Denaturation  scissione delle due catene:

• Annealing  appaiamento di due catene complementari:

• PCR (Polymerase Chain Reaction)  completamento di una catena in direzione 5’-3’ tramite

una sequenza innesco (primer):

• Exonucleases  accorciamento alle estremità:

• Restriction enzymes  tagliano le molecole di DNA in siti specifici

• Ligases  riuniscono due catene con sticky ends complementari

• Gel electrophoresis  separazione di molecole di DNA in base alla loro lunghezza

• Filtering  separazione di molecole di DNA con sequenza nota tramite supporto solido

L’esperimento di Adleman

1) Generazione di un insieme di percorsi casuali attraverso il grafo delle città: 12

Alice Giussani sintesi di molecole complementari delle molecole che codificano per le città +

o sintesi di molecole che codificano per i collegamenti fra le città  tramite annealing e

ligasi si formano doppie catene di DNA che codificano percorsi casuali nel grafo

(le molecole dei collegamenti sono collegate fra loro e tenute insieme dalle

o molecole complementari delle città)

2) La codifica del grafo:

vertice vi  stringa casuale di 8 basi (4 basi per il

o “nome” e 4 basi per il “cognome”)

arco da vi a vj  stringa di 8 basi (4 basi

o corrispondono al cognome di vi e 4 basi

corrispondono al nome di vj )

3) generazione si percorsi

4) Verifica che ogni percorso inizi nella città iniziale e termini nella città finale

(altrimenti si scarta il percorso):

PCR (polymerase chain reaction) con 2 primer («cognome» città iniziale e

o complemento del «nome» della città finale) + cicli termici  duplicazione

esponenziale delle molecole che soddisfano questa condizione.

Le molecole che contengono sia la città iniziale che la città finale sono amplificate

o esponenzialmente mentre le molecole che contengono solo la città iniziale o solo la

città finale sono amplificate linearmente

5) Verifica vertici iniziale e finale:

PCR genera la copia complementare delle molecole che iniziano con il corretto

o vertice iniziale (agisce sulla catena formata dai complementi dei vertici)

PCR duplica le molecole che terminano con il corretto vertice finale (agisce sulla

o catena formata dagli archi)

6) Verifica che ogni percorso passi esattamente per n città (altrimenti si scarta il

percorso):

elettroforesi su gel  separazione ed eliminazione delle molecole di lunghezza errata

o

7) Verifica che ogni percorso passi per tutti le città (altrimenti si scarta il percorso): 13

Alice Giussani filtraggio a supporto solido (con microsfere di ferro attaccate a molecole

o complementari delle città)  conservazione di tutte e sole le molecole che

contengono la codifica DNA di ogni città del grafo

8) Se non tutti i percorsi sono stati scartati, allora esiste un percorso di Hamilton nel

grafo: duplicazione per PCR + sequenziamento delle molecole di DNA  decodifica del

o percorso trovato

Complessità computazionale dell’algoritmo «molecolare»:

– Numero di operazioni di laboratorio  O(n) (dove n è il numero dei vertici nel grafo)

…cioè Adleman ha «inventato» un modo per risolvere un problema NP-completo con un algoritmo

efficiente (di complessità lineare)!

Svantaggi del DNA Computing

Probabilità d’errore  le operazioni biologiche NON sono perfette

o Tempo  alcune operazioni di laboratorio richiedono un tempo dell’ordine dei minuti o delle

o ore

Quantità di DNA necessaria per una computazione:

o Scalabilità  limiti fisici

o HPP con 200 vertici richiede una quantità di DNA non trattabile

o

Banche dati biologiche ed elementi di basi di dati

Lo sviluppo delle biotecnologie molecolari ha consentito la produzione di enormi quantità di dati

biologici e questi dati vengono memorizzati nelle banche dati biologiche che contengono

informazioni derivanti da:

• Analisi di laboratorio (in vivo e in vitro)

• Analisi bioinformatiche (in silico)

• Letteratura scientifica

Le banche dati biologiche permettono di:

– Memorizzare e condividere le grandi quantità di dati che vengono continuamente generate

– Rendere disponibile l’informazione biologica in un formato leggibile dal computer, adatto per

analisi automatizzate

– Fornire un’infrastruttura ben organizzata e di facile utilizzo (user friendly) per la ricerca e il

reperimento dei dati

– Divulgare l’informazione biologica 14

Alice Giussani

Le banche dati contenenti sequenze di acidi nucleici (DNA, RNA) sono spesso definite primarie:

Contengono solo informazioni generiche sulla sequenza, per identificarla sulla base della

specie/funzione

L’informazione contenuta nelle banche dati primarie è spesso ridondante e «non curata» (non

annotata, o annotata in modo erroneo) esistono quindi banche dati secondarie che servono per

aggiornare, memorizzare e classificare i dati delle banche dati primarie, tramite correzione di

eventuali errori ed Inclusione di informazioni aggiuntive.

Le banche dati biologiche possono essere classificate a seconda del tipo di “struttura” usata per

gestire i dati:

– Banche dati basate su Database Management System (DBMS) standard, ad es. di tipo

relazionale o a oggetti

– Banche dati basate sul DBMS chiamato ACEDB Inizialmente sviluppato per la banca data «A

C. elegans Data Base” (ACeDB)

– Banche dati supportate da Object Protocol Model (OPM) insieme a un DBMS relazionale o a

oggetti OPM utilizza particolari costrutti per la gestione di esperimenti scientifici

– Banche dati implementate come collezione di “flat-file”.

Un flat-file è un file di testo non formattato (ASCII), contenente informazioni che non presentano

alcun tipo di relazione strutturata

Le basi di dati rappresentano degli strumenti molto potenti per la gestione e la ricerca automatica

di dati e informazioni:

– Gestiscono tipi diversi di informazione

– Visualizzano l’informazione in forma tabulare

Nonostante abbiano finalità e metodi di visualizzazione simili, i fogli di calcolo e le basi di dati

sono sostanzialmente differenti: Le basi di dati strutturano “maggiormente” l’informazione e sono

utilizzate principalmente per memorizzare grandi quantità di dati, più che per elaborare

automaticamente l’informazione

Strutturare l’informazione

In un database è possibile rappresentare qualunque entità che sia rappresentabile su un computer

e Per rappresentare un’entità, si identificano le sue caratteristiche, dette attributi e In particolare,

si identificano gli attributi dell’entità che sono necessari agli scopi di uno specifico contesto

applicativo.

Gli attributi hanno un nome e un dominio: Il nome caratterizza la natura dell’informazione, Il

dominio definisce il tipo di valori che possono essere assunti per quell’attributo.

Il dominio è un metadato: Informazione che descrive l’informazione, I metadati definiscono il tipo