DNA COMPUTING - profs.sci.univr.itprofs.sci.univr.it/~manca/mnc/dna-computing-08.pdf · 6 Teoria...

79
DNA COMPUTING Modelli di calcolo non convenzionali Prof. Vincenzo Manca Dispensa a cura di Marco Devincenzi 1

Transcript of DNA COMPUTING - profs.sci.univr.itprofs.sci.univr.it/~manca/mnc/dna-computing-08.pdf · 6 Teoria...

Page 1: DNA COMPUTING - profs.sci.univr.itprofs.sci.univr.it/~manca/mnc/dna-computing-08.pdf · 6 Teoria dei Linguaggi Formali ... Questa ridondanza di informazione µe di fondamentale ...

DNA COMPUTING

Modelli di calcolo non convenzionaliProf. Vincenzo Manca

Dispensa a cura di Marco Devincenzi

1

Page 2: DNA COMPUTING - profs.sci.univr.itprofs.sci.univr.it/~manca/mnc/dna-computing-08.pdf · 6 Teoria dei Linguaggi Formali ... Questa ridondanza di informazione µe di fondamentale ...

Indice

1 Introduzione 4

2 Fondamenti di DNA 52.1 La molecola DNA . . . . . . . . . . . . . . . . . . . . . . . . . 52.2 Il desossiribosio . . . . . . . . . . . . . . . . . . . . . . . . . . 72.3 Logica della concatenazione della molecola DNA . . . . . . . 82.4 Triangolo monomerico . . . . . . . . . . . . . . . . . . . . . . 132.5 Elica bilineare astratta . . . . . . . . . . . . . . . . . . . . . . 152.6 Forme bilineari . . . . . . . . . . . . . . . . . . . . . . . . . . 162.7 Notazione doppia stringa . . . . . . . . . . . . . . . . . . . . 17

3 Operazioni sul DNA 223.1 Operazioni di base: mix, split, length(elettroforesi), separate,

synthetize . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233.2 Denaturazione e Rinaturazione del DNA . . . . . . . . . . . . 263.3 Amplificazione con PCR . . . . . . . . . . . . . . . . . . . . . 27

3.3.1 Alberi PCR . . . . . . . . . . . . . . . . . . . . . . . . 303.4 Altre operazioni: Ligasi, Fish, Infix-Suffix . . . . . . . . . . . 343.5 Amplificazione con clonaggio molecolare . . . . . . . . . . . . 36

3.5.1 Vettori di clonaggio . . . . . . . . . . . . . . . . . . . 363.5.2 Enzimi di restrizione . . . . . . . . . . . . . . . . . . . 373.5.3 Plasmidi . . . . . . . . . . . . . . . . . . . . . . . . . . 393.5.4 Algoritmo di clonazione . . . . . . . . . . . . . . . . . 40

3.6 Sequenziamento . . . . . . . . . . . . . . . . . . . . . . . . . . 463.6.1 L’energia di attivazione delle reazioni chimiche . . . . 463.6.2 Gli enzimi catalizzatori . . . . . . . . . . . . . . . . . 473.6.3 ATP . . . . . . . . . . . . . . . . . . . . . . . . . . . . 473.6.4 Metodo chimico . . . . . . . . . . . . . . . . . . . . . . 483.6.5 Metodo enzimatico di Sanger . . . . . . . . . . . . . . 483.6.6 Pyrosequencing . . . . . . . . . . . . . . . . . . . . . . 50

4 Calcolare con il DNA 534.1 L’esperimento di Adleman (1994) . . . . . . . . . . . . . . . . 53

4.1.1 Extract Model . . . . . . . . . . . . . . . . . . . . . . 544.2 Algoritmi per 3-SAT . . . . . . . . . . . . . . . . . . . . . . . 56

4.2.1 Mix&Split Model . . . . . . . . . . . . . . . . . . . . . 564.2.2 Algoritmo di Lipton . . . . . . . . . . . . . . . . . . . 574.2.3 SAT come rete di contatto . . . . . . . . . . . . . . . . 584.2.4 Algoritmo di Jonoska . . . . . . . . . . . . . . . . . . 594.2.5 Algoritmo di Sakamoto . . . . . . . . . . . . . . . . . 604.2.6 Algoritmo di Manca . . . . . . . . . . . . . . . . . . . 61

4.3 Considerazioni . . . . . . . . . . . . . . . . . . . . . . . . . . 63

2

Page 3: DNA COMPUTING - profs.sci.univr.itprofs.sci.univr.it/~manca/mnc/dna-computing-08.pdf · 6 Teoria dei Linguaggi Formali ... Questa ridondanza di informazione µe di fondamentale ...

5 XPCR (Cross Pairing PCR) 645.1 Estrazione con XPCR . . . . . . . . . . . . . . . . . . . . . . 65

5.1.1 Considerazioni . . . . . . . . . . . . . . . . . . . . . . 665.2 Ricombinazione con XPCR . . . . . . . . . . . . . . . . . . . 67

6 Teoria dei Linguaggi Formali (FLT) 686.1 introduzione . . . . . . . . . . . . . . . . . . . . . . . . . . . . 686.2 Stringhe e linguaggi . . . . . . . . . . . . . . . . . . . . . . . 68

6.2.1 Gerarchia di Chomsky . . . . . . . . . . . . . . . . . . 696.2.2 Classi di Chomsky . . . . . . . . . . . . . . . . . . . . 706.2.3 Inclusioni . . . . . . . . . . . . . . . . . . . . . . . . . 71

6.3 Risultati fondamentali . . . . . . . . . . . . . . . . . . . . . . 726.3.1 Teorema di universalita di Chomsky . . . . . . . . . . 726.3.2 Teorema di Kleene . . . . . . . . . . . . . . . . . . . . 746.3.3 Teorema di Ginzburg . . . . . . . . . . . . . . . . . . . 766.3.4 Teorema di Savich . . . . . . . . . . . . . . . . . . . . 77

3

Page 4: DNA COMPUTING - profs.sci.univr.itprofs.sci.univr.it/~manca/mnc/dna-computing-08.pdf · 6 Teoria dei Linguaggi Formali ... Questa ridondanza di informazione µe di fondamentale ...

1 Introduzione

L’idea iniziale del DNA computing e molto semplice: calcolare, in terminiastratti, significa trasformare dati iniziali in risultati, ma dati e risultatisono sempre esprimibili tramite stringhe di un qualche linguaggio di rap-presentazione (teorema fondamentale della digitalizzazione). In particolareil DNA computing e un ottimo strumento per risolvere problemi intratta-bili. Un problema e intrattabile se non si conoscono algoritmi polinomialiin tempo che lo risolvono. Un problema viene classificato NP se puo essererisolto in tempo polinomiale da una macchina non deterministica, infine unproblema e NP-completo se ogni altro problema nella classe NP puo essereridotto ad esso in un tempo polinomiale (riduzione in tempo polinomiale). Iproblemi NP-completi sono considerati i piu difficili, cosı se si dimostra cheogni problema in NP e intrattabile allora tutti gli NP-completi lo sono, e seogni problema NP-completo puo essere risolto in tempo polinomiale alloratutti i problemi nella classe NP diventano trattabili.

Un computer non deterministico puo essere simulato tramite filamentidi DNA utilizzando tecniche di biologia molecolare per implementare le op-erazione su di esso. in teoria i problemi intrattabili possono essere risoltiin tempo polinomiale tramite un qualche tipo di DNA computer. Adleman,con il suo esperimento del 1994, risolse una istanza del problema del cammi-no Hamiltoniano (problema NP-completo) in tempo polinomiale utilizzandoil DNA come macchina di calcolo. Successivamente sono stati risolti altriproblemi NP-completi come SAT, indipendent Set e 3-colorabilita.

Come vedremo, per poter effetuare un tale tipo di elaborazione sono nec-essarie diverse operazioni biologiche tra cui: Separazione (melting), Accoppi-amento (annealing), Extract, Amplify, Merge, Elettroforesi su gel, Append,Split. Tuttavia gli algoritmi implementati con queste operazioni biologichenon sono esenti da errori. Cause di errori possono essere l’amplificazionePCR che non e al cento per cento efficiente, il graduale deterioramento delDNA e lo schema di codifica dell’istanza del problema: infatti se una codi-fica contiene sottostringhe, che anche in modo approssimato coincidono consottostringhe di un’altra codifica, allora l’input iniziale potrebbe essere com-promesso. Altra limitazione sono la lunghezza dei filamenti; grandi istanze diun problema richiedono spesso filamenti molto lunghi per una corretta cod-ifica e c’e un limite alla lunghezza che puo essere separata in modo efficientecon elettroforesi.

4

Page 5: DNA COMPUTING - profs.sci.univr.itprofs.sci.univr.it/~manca/mnc/dna-computing-08.pdf · 6 Teoria dei Linguaggi Formali ... Questa ridondanza di informazione µe di fondamentale ...

2 Fondamenti di DNA

Cio che contraddistingue in modo assoluto la materia vivente e che la suacomplessita risulta caratterizzata in modo preciso e si ripete in tutti gli in-dividui di una data specie. La complessita del mondo inorganico e invececasuale, per cui due sistemi inorganici non si ripetono mai in modo iden-tico, anzi, la probabilita che cio si verifichi diviene tanto piu remota tantopiu complesso e il sistema. L’esistenza di questa complessita comporta chenella materia vivente sia presente una enorme quantita di informazione,proprio per sapere come deve essere fatta e come deve essere duplicata.Tale informazione e registrata in un particolare composto, l’acido desos-siribonucleico (DNA). La capacita di duplicare l’informazione genetica euna caratteristica fondamentale per generare nuovi organismi, in modo cheogni nuovo individuo riceva la stessa informazione posseduta dai genitori.Come vedremo la struttura stessa delle molecole di DNA, costituite da duefilamenti che sono uno lo stampo dell’altro, offre il modello con cui tuttoquesto puo realizzarsi.

2.1 La molecola DNA

Il grosso del peso di una cellula e rappresentato da molecole di grandi di-mensioni, costituite quindi da migliaia di atomi dette macromolecole. Essesono rappresentate, essenzialmente, da acidi nucleici e proteine. Talimolecole ne assicurano la struttura e il funzionamento. in particolare gliacidi nucleici svolgono le funzioni di contenere e trasmettere l’informazionegenetica. Le varie proteine invece costituiscono la struttura stessa della cel-lula e svolgono tutte le funzioni fondamentali della materia vivente. In altritermini gli acidi nucleici, ed in particolare il DNA, costituiscono il supportomateriale nel quale e registrato il genotipo di un individuo (informazionegenetica), e le proteine sono la base del suo fenotipo cioe la concretizzazionedi tale informazione.

Una molecola di DNA e una sequenza di nucleotidi che, dal punto di vistadella loro struttura chimica, risultano costituiti da tre porzioni legate tra diloro da legami covalenti: zucchero, acido fosforico e base azotata. Le basisono le uniche che portano l’informazione e sono di quattro tipi (Adenina,Timina, Guanina, Citosina), mentre le altre due parti fungono da supporto:la base azotata legata allo zucchero costituisce un nucleoside, il nucleoside,legato al fosfato, costituisce un nucleotide. La molecola e composta da unacatena di zuccheri (Z) legati tramite il gruppo fosforico (P): ...Z P Z P ZP...; in particolare si hanno due file parallele (binario) e ogni fila possiede unorientamento intrinseco. Le due file sono legate da traversine che contengonol’informazione genetica. Tali traversine sono composte da basi azotate (B)che obbediscono al principio di Complementerieta (regola di Chargaff): A

5

Page 6: DNA COMPUTING - profs.sci.univr.itprofs.sci.univr.it/~manca/mnc/dna-computing-08.pdf · 6 Teoria dei Linguaggi Formali ... Questa ridondanza di informazione µe di fondamentale ...

(Adenina) lega con T (Timina) e C (Citosina) lega con G (Guanina). Sitratta di legami a idrogeno tra le coppie di basi che presentano una giustadisposizione dei gruppi donatori e accettori degli elettroni di valenza; questosi verifica solo se una adenina si trova di fronte ad una timina (due legami aidrogeno) e una guanina di fronte ad una citosina ( tre legami a idrogeno).Per tale motivo, le coppie adenina-timina (A-T) e guanina-citosina (G-C)vengono dette coppie di basi complementari. Inoltre come vedremo le duecatene hanno orientamenti opposti: si dice che hanno orientamento antipar-allelo.Si tratta ora di comprendere come questi vincoli strutturali imposti dalla

ZPZPZ

ZPZPZ

B

B

B

B’

B ’

B ’

Figura 1: Catena nucleotidi

doppia catena si concilino con la funzione di trasportare l’informazione delmateriale genetico. La sequenza nucleotidica, e quindi l’informazione di unadelle due catene, e assolutamente libera in quanto in ogni posizione puo es-sere presente uno qualsiasi dei quattro nucleotidi che costituiscono il DNA;tuttavia una volta definita la sequenza di una delle due catene, la sequenzadell’altra e completamente vincolata, poiche deve presentare le basi com-plementari a quelle sull’altra catena. Le due catena hanno quindi sequenzadiverse ma complementari: il DNA puo contenere qualsiasi informazione ela contiene due volte. Questa ridondanza di informazione e di fondamentaleimportanza biologica per due motivi:

• offre un modello molto efficiente per la replicazione dell’informazionegenetica: vedremo come le due catene si separino per costituire cias-cuna lo stampo per la polimerizzazione di una nuova catena, secondole regole della complementarieta delle basi;

• consente la conservazione dell’informazione nei casi in cui una delle duecatene venisse danneggiata: finche la catena complementare rimane in-tegra, la cellula puo sempre provvedere a riparare il danno utilizzandol’informazione conservata nella catena complementare.

Studiando matematicamente il DNA ci si rende conto che questi vincolistrutturali obbediscono a precisi criteri algoritmici; la molecola deve esserecosı fatta per avere algoritmi di duplicazione efficienti. La duplicazione, come

6

Page 7: DNA COMPUTING - profs.sci.univr.itprofs.sci.univr.it/~manca/mnc/dna-computing-08.pdf · 6 Teoria dei Linguaggi Formali ... Questa ridondanza di informazione µe di fondamentale ...

abbiamo accennato, e alla base della vita; la riproduzione si basa su mec-canismi di duplicazione e avere un meccanismo (algoritmo) efficiente e ve-loce e essenziale: la struttura del DNA e quindi legata all’efficienza delladuplicazione.

2.2 Il desossiribosio

Lo zucchero (Z) utilizzato nei nucleosidi e un desossiribosio a 5 atomi dicarbonio: Gli atomi di carbonio vengono denominati con gli indici da 1′ a

C H 2 O H

O H H

H

H

O H

H

O H

5 1 0 4C H O

Figura 2: struttura desossiribosio

5′. Il concatenamento dei nucleotidi per formare le catene avviene tramite illegame di un fosfato in posizione 5′ o 3′ a fronte di un fosfato gia presenterispettivamente in 3′ o in 5′. Il fosfato funge da ponte tra i due desossiribosi.Si vengono cosı a formare due catene lineari di lunghezza indefinita chepresentano una struttura costituita dalla alternanza di zucchero e fosfato,dalla quale sporgono le basi azotate. Le due estremita della catena nonsono equivalenti: quella che presenta un fosfato libero (non impegnato inun legame) e detta estremita 5′, quella che presenta un fosfato legato conuno zucchero e detta estremita 3′. Per convenzione, la sequenza dei nucleotidiviene descritta a partire dalla estremita 5′: si dice che viene letta in direzione5′ → 3′. Le Figure 3 e 4 mostrano rispettivamente la formazione di unnucleoside e di un nucleotide:

B

5’

4 ’

3 ’ 2 ’

1 ’

Figura 3: nucleoside

7

Page 8: DNA COMPUTING - profs.sci.univr.itprofs.sci.univr.it/~manca/mnc/dna-computing-08.pdf · 6 Teoria dei Linguaggi Formali ... Questa ridondanza di informazione µe di fondamentale ...

B

5’

4 ’

3 ’ 2 ’

1 ’

PH O

2

Figura 4: nucleotide

Nella Figura 5 vediamo la formazione di un nucleotide a partire da unnucleoside: al nucleoside formato dallo zucchero con base azotata viene ag-giunto in posizione 5′ il fosfato (PO4) e nella reazione vengono eliminati glielementi di una molecola d’acqua.

( 3 ’ ) O H _ Z ( B ) _ ( 5 ’ ) C H O H + P O = ( 3 ’ ) O H _ Z ( B ) _ ( 5 ’ ) C H P O2 4 42

Figura 5: formazione-nucleotide

Sono quindi emersi tre vincoli strutturali che possiamo enunciare come treprincipi costitutivi della molecola DNA:

1. BILINEARITA: il DNA e formato da due catene appaiate

2. COMPLEMENTARIETA: le catene sono appaiate rispettando la regola diChargaff

3. ANTIPARALLELISMO: la catena appaiata e posizionata nel verso oppos-to rispetto all’altra catena; Testa (Ch2PO4) Ã Coda(OH), Coda(OHTesta(CH2PO4) Ã).

Come vedremo, la bilinearita e la complementarieta sono strettamente legate aduna esigenza algoritmica piu che biochimica, volte ad una esecuzione efficiente del-la duplicazione. Ci si chiede invece come mai proprio l’antiparallelismo e non sem-plicemente il parallelismo? questa proprieta, come vedremo, e dovuta alla strutturastessa, e un obbligo strutturale.

2.3 Logica della concatenazione della molecola DNA

Si cerca di astrarre dalla formazione chimica delle molecole per concentrarsi prin-cipalmente sulla struttura necessaria per contenere l’informazione genetica.

I nucleotidi visti come singoli componenti vengono chiamati monomeri, per poiformare tramite concatenazione i polimeri detti anche polimeri informazionali. Imonomeri sono oggetti chirali1, ovvero oggetti rispetto a cui e possibile definire un

1Una molecola e detta chirale se la sua immagine speculare non e sovrapponibile a se.

8

Page 9: DNA COMPUTING - profs.sci.univr.itprofs.sci.univr.it/~manca/mnc/dna-computing-08.pdf · 6 Teoria dei Linguaggi Formali ... Questa ridondanza di informazione µe di fondamentale ...

sistema cartesiano di riferimento destrorso o sinistrorso con un certo orientamento.In particolare indichiamo la chiralita di un monomero, il piano cartesiano associatoai versi x,y,z con le seguenti direzioni: concatenazione per il verso x, appaiamentoper il verso y e posizione del lettore per l verso z (Figura 6).Inoltre i monomeri hanno un tipo denotato da un simbolo appartenente all’insieme{A, T, C,G} per cui se un monomero m ha un tipo X si scrive m : X

c o n c a t e n a z i o n e

p a i r i n g

le t t o re

Figura 6: mappatura

Si possono stabilire i seguenti principi sui quali si basera la notazione che verraintrodotta nel paragrafo 2.7

1. PRINCIPIO DI UNIFORMITA DELLA CONCATENAZIONE: stesso versodi concatenamento. Ogni monomero di una catena ha lo stesso verso che vadalla coda del monomero alla testa del monomero successivo. Il nucleotide Ne chimicamente una struttura orientata da 5′ a 3′. Dopo la concatenazione, lastruttura deve mantenere l’orientamento, quindi tale operazione puo avveniresolo se i due nucleotidi hanno lo stesso verso e di conseguenza il risultato avralo stesso verso: −N → ; −N → ⇒ −N → −N →.

2. PRINCIPIO DI COMPLEMENTARIETA: Due monomeri si possono appa-iare solo se i loro tipi rispondono alla regola di Chargaf (A-T; G-C)

3. MIRROR PAIRING. I versi dell’appaiamento sulle due catene sono opposti :La direzione dell’appaiamento va dalla testa del monomero alla testa delmonomero appaiato: un monomero puo essere appaiato con al piu un altromonomero e due monomeri concatenati con altri due monomeri concatenati.Questo implica che i monomeri di una singola catena hanno lo stesso orienta-mento nella direzione del pairing (appaiamento). La Figura 7 a) mostra unacatena concorde con tale principio mentre la b) va contro il principio.

a )b )

Figura 7: a) stesso verso y. b) verso y opposto

9

Page 10: DNA COMPUTING - profs.sci.univr.itprofs.sci.univr.it/~manca/mnc/dna-computing-08.pdf · 6 Teoria dei Linguaggi Formali ... Questa ridondanza di informazione µe di fondamentale ...

4. FREE BILINEAR LOCATION. Le molecole sono libere di posizionarsi inqualsiasi punto della catena, l’importante e che siano rispettati gli altri prin-cipi.

Le catene bilineari possono essere denaturate in due singoli filamenti separati;questo significa che la forza di appaiamento e debole rispetto alla forza di concate-nazione. La forza debole di appaiamento e legata alla complementarieta. Infatti sei monomeri appaiati avessero lo steso tipo, allora i legami sarebbero legami chimicicovalenti, ovvero molto forti e quindi molto difficili da rompere in fase di denatu-razione e tale operazione e fondamentale per la duplicazione del DNA.Come e intuibile, tale struttura bilineare e complementare e l’unica che permetteuna duplicazione in tempo polinomiale oltre a facilitare un controllo di possibilierrori. Vedremo che grazie a questa caratteristica si avra un numero esponenzialedi coppie in un tempo lineare; se si lavorasse su una sola stringa, infatti, ogni algo-ritmo di duplicazione avrebbe complessita quadratica rispetto alla dimensione dellastringa stessa.

La struttura bilineare puo essere rappresentata come in Figura 8, oppure comein Figura 9 e in entrambi i casi sono rispettati i principi strutturali sopra men-zionati, tuttavia vedremo che l’unica disposizione possibile e quella antiparallela;inoltre l’appaiamento tra due filamenti puo essere parziale dando origine a moltecombinazioni come mostrato in Figura 10.

x

y

y

x

Figura 8: pairing paralleli

x

y

y

x

Figura 9: pairing antiparalleli

10

Page 11: DNA COMPUTING - profs.sci.univr.itprofs.sci.univr.it/~manca/mnc/dna-computing-08.pdf · 6 Teoria dei Linguaggi Formali ... Questa ridondanza di informazione µe di fondamentale ...

Figura 10: possibili appaiamenti

Riassumendo la struttura bilineare dei monomeri e cosi definita:

• Il verso di concatenazione corrispondente all’asse x. La coda-testa del monomerocorrisponde al verso 5′ − 3′.

• Il verso y corrisponde alla direzione lungo la quale i monomeri si appaiano.

• La direzione z perpendicolare al piano xy, identifica il punto in cui si posizionaun ipotetico lettore. Infatti i nucleotidi contengono informazione e per talemotivo necessitano di essere letti.

In accordo con il principio 1 e 3, i monomeri sono asimmetrici rispetto sia all’asse xche all’asse y. La seguente proposizione afferma che sono asimmetrici anche rispettoall’asse z :

Proposizione 1. I monomeri devono essere asimmetrici rispetto all’asse z.

Dimostrazione. Se per assurdo un monomero fosse simmetrico all’asse z, al-lora dopo una rotazione attorno all’asse y o x, il monomero si posizionerebbe converso opposto rispetto all’asse x o y e quindi sarebbe simmetrico rispetto a x o y ;ma non puo essere perche violerebbe il mirror pairing e l’uniformita della concate-nazione.

Corollario. I monomeri sono oggetti chirali: sono asimmetrici rispetto a tuttele direzioni. Ad un oggetto chirale si associa un sistema cartesiano.

La asimmetria rispetto all’asse z suggerisce un naturale verso di lettura pref-erenziale e questa intuizione ci porta ad enunciare il Principio del verso di let-tura uniforme: un lettore (ad esempio l’enzima polimerasi) puo leggere tutti imonomeri di una catena stando sempre nello stesso lato rispetto al piano xy, ovverotutti i monomeri della stessa catena devono avere lo stesso verso z (Figura 11).

Lemma. Se due oggetti chirali con sistemi di riferimento F1 e F2 differisconoper due versi, e possibile tramite un movimento rigido, sovrapporre i due oggetti inmodo che abbiano lo stesso sistema cartesiano (oggetti omochirali). Se differisconoper un solo verso, non e possibile sovrapporli e tali oggetti si chiamano eterochirali.

Proposizione 2. Il principio dell’universalita del verso di lettura implica chetutti i monomeri della stessa catena devono avere la stessa chiralita.

Dimostrazione. Se per assurdo esistessero due monomeri con chiralita diversanello stesso filamento, allora per l’uniformita di concatenamento avrebbero lo stessoasse x, e per il mirror pairing avrebbero lo stesso asse y, quindi per il lemma devonodifferire per l’asse z (essendo per assurdo eterochirali), ma questo contraddice il

11

Page 12: DNA COMPUTING - profs.sci.univr.itprofs.sci.univr.it/~manca/mnc/dna-computing-08.pdf · 6 Teoria dei Linguaggi Formali ... Questa ridondanza di informazione µe di fondamentale ...

x

y

z

Le t t o re d i e t r o a l p i a n o x y

L e t t o r e d a v a n t i a l p i a n o x y

Figura 11: Lettore

principio dell’uniformita di lettura. Segue che i monomeri sono omochirali

Proposizione 3. Il verso di lettura dei due filamenti appaiati coincide se e solose i due orientamenti sono antiparalleli.

Dimostrazione. Si e visto che i monomeri hanno chiralita e sono omochirali,quindi devono essere messi per forza in modo antiparallelo, altrimenti si infrange ilmirror pairing o l’uniformita o la free location. Quindi essendo omochirali il versoz coincide solo se sono disposti in modo antiparallelo.(⇐): se sono antiparalleli i monomeri dei due filamenti differiscono per due versi xe y, ma essendo omochirali ed avendo versi opposti per x e y, il verso z deve perforza coincidere e quindi hanno lo stesso verso di lettura.(⇒):Dimostro il contronominale. Se sono paralleli allora i monomeri differisconosolo per il verso y, ma essendo omochirali allora devono differire per un’altro verso,ed essendo paralleli questa direzione e l’asse z, quindi hanno una diversa direzionedi lettura.

Questa proposizione mostra il grande vantaggio dell’antiparallelismo rispetto alparallelismo: con il primo abbiamo un unico verso di lettura.Proveremo che la disposizione antiparallela delle due stringhe e l’unica possibile elo proveremo utilizzando solo argomenti geometrici.

12

Page 13: DNA COMPUTING - profs.sci.univr.itprofs.sci.univr.it/~manca/mnc/dna-computing-08.pdf · 6 Teoria dei Linguaggi Formali ... Questa ridondanza di informazione µe di fondamentale ...

2.4 Triangolo monomerico

Il monomero e completamente individuato da un triangolo composto da i due puntidi concatenazione ovvero i due fosfati, e il punto di appaiamento (Figura 12)

T

H H ’

t e s t a ( h e d ) t e s t a a p p a i a t a

coda ( t a i l )

a n g o l o a c u t o

Figura 12: triangolo-monomerico

L’angolo del triangolo e acuto; se fosse stato ottuso avrebbe occupato piu spazio ela catena avrebbe assunto dimensioni spropositate per una cellula. L’angolo acutoci permette di dare una ulteriore conferma che la disposizione antiparallela e l’unicapossibile. Se solo lo ipotizziamo notiamo che l’unico modo per mettere due triangoliappaiati consiste nel disporli in modo antiparallelo (Figura 13)

TH

H ’

HT

Figura 13: angolo acuto e triangoli antiparalleli

I tre punti che individuano il triangolo sono essenziali per determinare la funzion-alita monomerica:

• Il punto H di testa e i primo punto del monomero lungo il verso di concate-nazione.

• La coda T e la testa del successivo monomero lungo il verso di concatena-mento.

• H’ e la testa del monomero appaiato.

Questi punti specificano il triangolo HTH’ chiamato appunto triangolo monomreri-co. In termini di nucleotidi, H corrisponde al fosfato in 5′ e T al fosfato in 3′ (Figura14). In base al tipo di informazione trasportata, esistono quattro tipi di triangoli:A, T, C, G. Quindi dal punto di vista astratto un monomero e un triangolo aventeun tipo che appartiene all’alfabeto delle basi azotate.

Proposizione. Se l’angolo THH’ del triangolo e acuto allora la disposizioneparallela bilineare non e possibile e quella antiparallela e l’unica possibile.

13

Page 14: DNA COMPUTING - profs.sci.univr.itprofs.sci.univr.it/~manca/mnc/dna-computing-08.pdf · 6 Teoria dei Linguaggi Formali ... Questa ridondanza di informazione µe di fondamentale ...

P

T

TH

H’b a s e a z o t a t a

g r u p p o f o s f o r i c o

Figura 14: punti del triangolo monomerico

Dimostrazione. Se i due monomeri sono sullo stesso piano, sono appaiati lungoil loro asse di pairing (y) e l’angolo e acuto, l’unico modo per ottenere la bilinearitae una disposizione antiparallela. Un’altra disposizione e mostrata in Figura 15, main questo caso si perde la bilinearita.

x

y

y

x

Figura 15: disposizione non lineare

Tuttavia nella struttura bilineare antiparallela, i monomeri non sono sullo stessopiano perche si trovano in un ambiente fluido. In questo caso avviene una rotazionedi un certo angolo da parte dei lati esterni del triangolo e questo e possibile secontemporaneamente ciascun triangolo e libero di ruotare lungo l’asse x nei punti dicontatto della concatenazione. Questa rotazione provoca la classica forma a doppiaelica del DNA.

14

Page 15: DNA COMPUTING - profs.sci.univr.itprofs.sci.univr.it/~manca/mnc/dna-computing-08.pdf · 6 Teoria dei Linguaggi Formali ... Questa ridondanza di informazione µe di fondamentale ...

2.5 Elica bilineare astratta

I legami del doppio filamento sono liberi di muoversi in un ambiente fluido, ma talemovimento rimane confinato all’interno di un cilindro chiamato cilindro astratto(Figura 16). Il triangolo ruota attorno all’asse del cilindro il quale e determinato

H

T H ’

T

Figura 16: cilindro monomerico

dai seguenti punti:

• Angolo ρ: rotazione rispetto all’asse del cilindro del segmento di concate-nazione; dice di quanto ruota per concatenarsi.

• Angolo τ : torsione; dice di quanto il monomero si piega rispetto alla verticale

• Angolo θ: fase; dice di quanto ruota l’accoppiamento nel cilindro (angoloformato tra H e la perpendicolare di H’).

• Raggio cilindro.

La forma dell’elica del DNA e quindi completamente determinata da tre angoli, unraggio e la non complanarita (ovvero i monomeri sono situati su piani differenti).

15

Page 16: DNA COMPUTING - profs.sci.univr.itprofs.sci.univr.it/~manca/mnc/dna-computing-08.pdf · 6 Teoria dei Linguaggi Formali ... Questa ridondanza di informazione µe di fondamentale ...

2.6 Forme bilineari

Avendo come riferimento i seguenti principi:

• bilinearita: doppia catena,

• antiparrallelismo: direzione delle due catene opposte 5′ − 3′ e 3′ − 5′,

• complementerieta: regola di Chargaff.

la struttura nucleotidica viene rappresentata tramite due frecce parallele aventi ver-so opposto: ¿Se consideriamo le forme bilineari strette si hanno le forme chiamate STICKYENDS (ovvero delle incollature, appiccicature) dovute proprio alla complementa-rieta la quale si puo vedere come una forma di adesione tra cose complementari. GliSticky ends si differenziano in base ai terminali, ovvero alle sporgenze di ossidrile ofosfato in 3’ o 5’ dei filamenti come mostrato in Figura 17.

3’3 ’ s t i cky end 3 ’ -3 ’

3 ’s t i c ky end 3 ’

3 ’5 ’s t i cky end 5 ’ -3 ’

3 ’b l u n t - y

y

3’s t i c k y e n d 3 ’ - y

y

3’y - y

y

5’s t i c k y e n d y - 5 ’

5 ’5 ’ s t i cky end 5 ’ -5 ’

5 ’ s t i c ky end 5 ’

m o l e c o l a b l u n t : s e n z a s p i g o l i

1 )

2 )

6 )

7 )

2 )

3 )

4 )

5 )

8 )

9 )

1 0 )

Figura 17: sticky-end

16

Page 17: DNA COMPUTING - profs.sci.univr.itprofs.sci.univr.it/~manca/mnc/dna-computing-08.pdf · 6 Teoria dei Linguaggi Formali ... Questa ridondanza di informazione µe di fondamentale ...

Nota: la parte y indica la porzione di filamento non complementare.

Alle forme bilineari strette si aggiungono la monostruttura: −→, gli eteroduplex,strutture con un singolo filamento: hairpin (punta di capello) e le varie combinazionicircolari e doppio circolari (Figura 18)

e t e r o d u p l e x

h a r p i n

c i r co la r i

Figura 18: forme non lineari

2.7 Notazione doppia stringa

A questo punto occorre fornire le molecole di una opportuna notazione per poterdescrivere matematicamente le operazioni sulla struttura monomerica.Dato un alfabeto finito A, definiamo A∗ come tutte le possibili sequenze di stringhesu A. Nel nostro caso A = {A, T, C,G} e corrisponde all’alfabeto nucleotidico. Chi-amiamo α, β, γ . . . le sequenze sull’alfabeto. Avendo a disposizione l’operazione diconcatenazione, le sequenze sono a tutti gli effetti delle stringhe; preso α e β, laconcatenazione produce la sequenza α seguita da β: αβ. Per rappresentare l’orienta-mento dei nucleotidi faremo seguire la stringa da una freccia α →: la parte sinistraindica la presenza del gruppo fosforico e la pate destra l’ossidrile. L’orientamentoopposto lo otteniamo con l’ndicazione ← α.Indichiamo con λ la sequenza vuota formata cioe da nessun nucleotide. Un’altraoperazione su A? e il rev, ad esempio rev(cane) = enac.

Definizione di rev :rev(x) = xrev(αβ) = rev(β)rev(α)rev(λ) = λ

Esempio:rev(cane) = rev(ane)rev(c) = rev(ne)rev(a)rev(c) = rev(e)rev(n)rev(a)rev(c) =enac.

17

Page 18: DNA COMPUTING - profs.sci.univr.itprofs.sci.univr.it/~manca/mnc/dna-computing-08.pdf · 6 Teoria dei Linguaggi Formali ... Questa ridondanza di informazione µe di fondamentale ...

Assioma:αλ = αλα = α

Sulle stringe definiamo inoltre la lunghezza |α|:|λ| = 0|αβ| = |α|+ |β||x| = 1

Abbiamo cosı definito tre operazioni di base sulle stringhe:

• concatenazione

• reverse

• lunghezza

Per rappresentare l’appaiamento di due filamenti utilizziamo la notazionefrazionaria in cui il filamento superiore ha verso 5′ − 3′ e quello inferiore e ilreverse ovvero 3′ − 5′.Ad esempio, se N e un generico nucleotide una possibile notazione frazionaria e laseguente: NNNCACGNNN

GCAC

Operazioni sulle doppie stringhe

• sottostringa α[i, j]: porzione di stringa tra le posizioni i e j

• concatenazione αβ

• complemento (αc): ad ogni base si prende la lettera complementare

• reversing rev(α): stringa girata in senso opposto

• mirroring rev((αc)): composizione tra rev e complemento, ovvero la stringae girata dall’altra parte ed e complementata

• Hibridazione α][β: indica che le stringhe si possono ibridizzare

• pairing αβ : e sottointeso che hanno verso opposto

• overlapping α ./ β

• overlap concatenation α|β• blunt pairing < α >

Le operazioni non vengono svolte su singole stringhe, ma su popolazioni di stringhe;si tratta dunque di capire come agire sulla popolazione per avere i comportamentivoluti sulle singole stringhe.

18

Page 19: DNA COMPUTING - profs.sci.univr.itprofs.sci.univr.it/~manca/mnc/dna-computing-08.pdf · 6 Teoria dei Linguaggi Formali ... Questa ridondanza di informazione µe di fondamentale ...

Definizioni.

• (α)c ,

(λ)c = λ(T )c = A(A)c = T(C)c = G(G)c = C(αβ)c = (α)c(β)c

• mirr(α) = rev((α)c) = α si usa questo simbolo come abbreviazione

• orientamento:αλ = α → notazione superiore

λα =← rev(α) notazione inferiore

• αrev(α) =< α > ovvero:

αrev(rev(α)c) = α

αc

Nota: rev e mirr sono involutive, ovvero: rev(rev(α)) = α e (αc)c = α

Esempio:

Sia α → la seguente stringa: 5’ATTCCG→ 3′ se ora si esegue il mirror siottiene: CGGAAT→, ma vediamo nel dettaglio come operare.Per effettuare il mirror, prima si complementa e poi si fa il reversing:(α)c = TAAGGC = α′

rev(α′) = CGGAAT →• pairing: α ‖ β sse β = mirr(α), ricordando che mirr = rev(αc)

ovvero si ha il pairing se e solo se β e il mirror(α) e in questo caso e definital’operazione di pairing: α

rev(β)

Esempio.

ATTCCG →‖ CGGAAT →La seconda stringa e il mirr della prima e quindi e possibile effettuare il pair-ing: ATTCCG→

←TAAGGC

La difficolta rispetto alle stringhe normali consiste nel fatto che si deve oper-are in primo luogo con doppie stringhe e poi occorre considerare due elementiaggiuntivi come la coplementarieta e l’orientamento.

Nota:Se α||α allora α

rev(α) = αrev(rev(αc)) = α

αc

19

Page 20: DNA COMPUTING - profs.sci.univr.itprofs.sci.univr.it/~manca/mnc/dna-computing-08.pdf · 6 Teoria dei Linguaggi Formali ... Questa ridondanza di informazione µe di fondamentale ...

Sopra si legge da 5′ a 3′ e sotto da 3′ a 5′ anche se e la stessa stringa (lastringa e la stessa, ma il verso e opposto).La molecola in forma doppia la si indica con < α >. Quando la molecola eperfettamente doppia si ha l’uguaglianza < α >=< α > ovvero e uguale alsuo mirror, infatti:< α >= α

rev( ¯α)) = αrev(α) = α

rev(α) = αrev(rev(αc)) = α

αc che e proprio < α >

• α][β indica il pairing generale, cioe α si accoppia con β se esiste γ tale cheα ⊃ β,β ⊃ γ e |γ| > h, ovvero la lunghezza di γ e maggiore di un certovalore chiamato costante di ibridizzazione che dipende dalla temperatura edalla composizione della molecola.Se sussistono tali condizioni allora puo esistere la struttura doppia α

rev(β) .L’insieme di tutte le strutture doppie le indichiamo con B∗|B∗.

Assioma di rotazione:

αrev(β) = β

rev(α)

Le molecole doppie sono rotazionali perche si trovano in un ambiente fluidoe pertanto un enzima le puo leggere indifferentemente da sopra o da sotto.

• Overlapping α ./ β = max{g|α = fg ∧ β = gp}L’operazione max si riferisce alla massima lunghezza.L’idea e la seguente(Figura 19): Due filamenti appaiati hanno una parte

f g

g p

Figura 19: overlapping

perfettamente appaiata, quindi l’overlapping e quella parte appaiata.

• overlap concatenation< α|β >=< fgp > questa e una operazione che viene effettuata dall’enzimapolimerasi (Figura 20).

• Extend (ext)

ext(αγ, δγβ) = ext(αγ, λδcγcβc ) = αγβ

Questa operazione corrisponde all’estensione di un filamento prendendo cometemplate, come stampo, il filamento inferiore. Se la seconda molecola si ap-paia per un pezzo con la prima, allora come risultato si ha l’estensione dellaprima copiando quello che trova sotto. Ovvero si mette la seconda stringain notazione frazionaria, si vede se c’e una parte in comune (γ) e copio la

20

Page 21: DNA COMPUTING - profs.sci.univr.itprofs.sci.univr.it/~manca/mnc/dna-computing-08.pdf · 6 Teoria dei Linguaggi Formali ... Questa ridondanza di informazione µe di fondamentale ...

f g

g p

Figura 20: overlap concatenation

sottostringa rimanente β nella stringa superiore (indipendentemente da α eδ).Inoltre si ha:

ext(αγ, η) = αγ se η 6= βγδ ∀βγ

ovvero se η non si puo fattorizzare con il template βγδ, allora l’estensionenon fa nulla e ritorna il primo filamento come risultato

Nella notazione a doppia stringa, l’ext() utilizza come template il filamemtoappaiato.

Abbreviazioni

ext(α,β)rev(β) ≡ ext(α)

rev(β)

αrev(ext(β,α)) ≡ α

rev(ext(β))

ext(α,β)rev(ext(β,α)) ≡ ext(α)

rev(ext(β)) : Overlap Concatenation su doppia stringa

21

Page 22: DNA COMPUTING - profs.sci.univr.itprofs.sci.univr.it/~manca/mnc/dna-computing-08.pdf · 6 Teoria dei Linguaggi Formali ... Questa ridondanza di informazione µe di fondamentale ...

3 Operazioni sul DNA

Consideriamo come oggetto delle operazioni un pool di DNA; un pool e un mul-tiinsieme di elementi appartenente a B∗|B∗ ovvero l’insieme di tutte le stringhedoppie. Il pool di DNA e contenuto in una provetta che indichiamo con P. P indicasia il contenuto che il contenitore: ad esempio R = R + 1 e l’operazione di incre-mento in cui R indica a sinistra il registro e a destra il contenuto del registro; oancora P = ext(p) dove a sinistra P indica la provetta e a destra il contenuto.

Chiamiamo filamento un oggetto s sul quale e definita l’operazione type cheassegna ad s una stringa di B∗|B∗. in particolare, se type(s) e una singola stringaallora s e un singolo filamento, mentre se type(s) e una doppia stringa, allora s eun doppio filamento.Consideriamo un pool P di DNA come un insieme di filamenti o come un multiin-sieme di singole o doppie stringhe di B∗|B∗.Possiamo scrivere:

P = {n1 : α1, n2 : α2, . . . , nk : αk} dove:α1 . . . αk ∈ B∗|B∗, n e il numero della molecola di uno specifico tipo e α e il tipodella molecola

Oppure possiamo indicare P come segue:

P = {S1, S2, . . . , Si} ∀ i si ha che S : α, α ∈ {α1 . . . αk}Ovvero un multiinsieme di stringhe di B∗|B∗ e specificato dalla funzione molteplic-ita multp da B∗|B∗ ai numeri naturali, che indica il numero di copie per ognifilamento di tipo η ∈ B∗|B∗:

multp : B∗|B∗ → N

Esempio:multp(α1) = n1

multp(αk) = nk

multp(β) = 0

Si puo dunque scrivere che:y ∈ P sse multp(y) 6= 0: la stringa y appartiene al pool sse nel pool c’e qualcheoggetto di quel tipo.S ∈ P sse type(S) 6= λ: Ogni filamento in provetta ha come tipo una stringa, ifilamenti che non sono in provetta hanno come tipo una stringa vuota.

Si ha che:Type(P ) = {y ∈ B∗|B∗|y ∈ P} = {type(S)|S ∈ P}Type e un insieme di stringhe ovvero e un linguaggio.

L’operatore type assegna ad un filamento una stringa e l’operatore Type asseg-na ad un pool di filamenti l’insieme dei tipi dei suoi filamenti. Stringhe e filamentisono concetti differenti anche se spesso i due termini vengono usati come sinonimi.Infatti una stringa e fisicamente implementata dal filamento che ha come tipo la

22

Page 23: DNA COMPUTING - profs.sci.univr.itprofs.sci.univr.it/~manca/mnc/dna-computing-08.pdf · 6 Teoria dei Linguaggi Formali ... Questa ridondanza di informazione µe di fondamentale ...

stringa stessa.

Le operazioni sul DNA viste con la nostra notazione sono sostanzialmente op-erazioni su linguaggi. Vedremo le operazioni biologiche mix, split, length, separate,sintesi, amplificazione, naturazione, denaturazione e sequenziamento.

Note sul calcolo

Dato un singolo filamento S, con la notazione introdotta esso viene rappresen-tato come stringa α e un doppio filamento come una doppia stringa. Si dice che Sha un tipo: rispettivamente S : α t.c type(S) = α e S : α

β t.c. type(S) = αβ .

Anche una popolazione P ha un tipo, che e l’insieme di tutti i tipi che si hannonella popolazione:Type(P ) = {type(S) ∈ B?B?|S ∈ P} dove P = {S1, S2, . . . , Sn} e un multiinsieme.

Le operazioni viste e che vedremo operano su popolazioni di oggetti per cui sipassa da P a P’ senza avere la piena conoscenza di come e fatto P; si conosce sola-mente il suo tipo, ovvero il tipo degli oggetti in P. Quello che interessa e passare aP’ contenente altri oggetti di un certo tipo; si ha quindi il passagio di tipi: Type(P)→ Type(P’).

3.1 Operazioni di base: mix, split, length(elettroforesi), sep-arate, synthetize

1. mix o merge (unione).mix(P1, P2) = P1 + P2: e la somma delle molteplicita come multiinsieme;il contenuto di due provette separate viene mescolato in una unica provetta.

2. split (divisione).split(P ) = (P1, P2) tale che P1 + P2 = P e Type(P1) = Type(P2 =Type(P )): il tipo di entrambi gli elementi prodotti deve uguagliare il tipodi partenza.Dopo lo split il linguaggio di P si trova sia in P1 che in P2, quindi se in P sihanno le stringhe α1 e α2, allora un certo numero di esse si sono distribuitesia in P1 che in P2 (Figura 21)

P

P 1

P 2

Figura 21: split

3. length.length(P ) = {n1, n2, . . . , nn}e un insieme finito di numeri che rappresentano le lunghezze presenti in

23

Page 24: DNA COMPUTING - profs.sci.univr.itprofs.sci.univr.it/~manca/mnc/dna-computing-08.pdf · 6 Teoria dei Linguaggi Formali ... Questa ridondanza di informazione µe di fondamentale ...

provetta.Questa operazione viene effettuata tramite uno strumento di analisi chiamatoelettroforesi su gel e consente di separare le molecole in base alle loro dimen-sioni. Un gel costituito da agarosio puo essere considerato come una rete tridi-mensionale in cui vengono fatte migrare le molecole sotto l’azione di un campoelettrico. Le molecole di DNA, essendo cariche negativamente per la presen-za del gruppo fosfato, migrano verso il polo positivo con una velocita che efunzione del loro peso molecolare. Molecole di dimensioni minori si muovonopiu velocemente attraverso le maglie del gel e quindi si separano da quelle didimensioni maggiori. Dopo un certo tempo l’insieme delle molecole che han-no la stessa lunghezza appaiono come bande a diversa distanza dal pozzettodi ingresso, Figura 22. Si possono vedere utilizzando particolari reagenti eilluminando il gel con luce ultravioletta.

0

1 0

2 0

3 0

4 0

+ + + + + + + + + + + + + + + + + + + + + + + + + + + + +

- - - - - - - - - - - - - - - - - - - - - - - - - - - -

i n g r e s s i p e r v a r i p o o l d i D N A

0

1 0

2 0

3 0

4 0

+ + + + + + + + + + + + + + + + + + + + + + + + + + + + +

- - - - - - - - - - - - - - - - - - - - - - - - - - - -

T

Figura 22: elettroforesi

4. separate.separate(P, n) = {s ∈ P | type(s) = η, |η| = n} prende la banda delle molecolelunghe n; questa operazione si basa sull’elettroforesi.

5. synthetize.E la procedura per creare ovvero scrivere una stringa di DNA. I nucleotidipossono essere creati con metodi di sintesi chimica e quello che si desidera emettere questi nucleotidi in una specifica posizione nella sequenza; ad esempiopotremmo essere interessati a produrre la sequenza ATCG→.La scrittura avviene da destra a sinistra, contrariamente alla lettura cheavviene da sinistra a destra. Il procedimento si basa su una sequenza di treoperazioni: ancoraggio, blocco e sblocco come descritto di seguito.

(a) Si prende una certa quantita di molecole di un certo tipo a esempioG. Non essendo possibile operare su singole molecole (data la loro pic-colissima dimensione) se ne prende un quantitativo pari ad esempio a1014 e si effettua la procedura di ancoraggio, ovvero si rende solidale lamolecola con un supporto solido.

(b) Si riempiono quattro vaschette con i nucleotidi A,T,C,G (una per vaschet-ta) e si bloccano in 5′ tramite la defosforilazione (eliminazione del fos-foro); in questo modo si impedisce la possibile formazione di un legamecon 3′ dalla parte di 5′.

24

Page 25: DNA COMPUTING - profs.sci.univr.itprofs.sci.univr.it/~manca/mnc/dna-computing-08.pdf · 6 Teoria dei Linguaggi Formali ... Questa ridondanza di informazione µe di fondamentale ...

(c) Si intinge il supporto solido nella vaschetta C e poiche, tali nucleotidinon hanno il fosforo, l’unico legame che si puo creare e dalla partedell’ossidrile (3′), cosı la C si attacca con la G dalla parte voluta: si ecreato un legame 3′ − 5′ tra C e G.

(d) Si toglie il supporto dalla vaschetta e quindi tramite opportune oper-azioni chimiche si sblocca C. A questo punto si ha 5′3′5′ su CG. Quindisi intinge il supporto cosı formato in T e dopo averlo estratto si ha5′3′5′3′5′ su TCG; si ripete per A e si ottiene la sequenza voluta ATCG.

La lettura della stringa e invece piu complicata perche necessita di una fase di am-plificazione del materiale genetico. Solitamente l’ordine di grandezza del materialeamplificato e di 1020. A livello simbolico un pool di molecole avente un certo tipo,occorre trasformarlo in un pool contenete tanti insiemi di molecole, dove ogni in-sieme contiene cloni di molecole dello stesso tipo:Type(P ) = {α1, α2 . . . αk} 7→ ({α1}, {α2} . . . {αk})

Nei prossimi capitoli vedremo le tecniche di amplificazione e di lettura.

25

Page 26: DNA COMPUTING - profs.sci.univr.itprofs.sci.univr.it/~manca/mnc/dna-computing-08.pdf · 6 Teoria dei Linguaggi Formali ... Questa ridondanza di informazione µe di fondamentale ...

3.2 Denaturazione e Rinaturazione del DNA

Il DNA, per effetto di agenti denaturanti fisici (calore) e chimici (condizioni estremedi pH e forza ionica) puo subire il fenomeno della denaturazione. Esso consiste nelladistruzione della struttura a doppia elica con separazione delle due catene nucleo-tidiche cha la costituiscono, senza pero che vengano scissi i legami del gruppo fos-forico che assicurano la continuita della catena con il desossiribosio (Figura 23). IlDNA in questo stato denaturato non puo essere utilizzato dalle cellule come fontedi informazione genetica.

Se il DNA, denaturato al calore, viene raffreddato lentamente lasciandolo aduna temperatura vicina a quella di denaturazione per un tempo abbastanza lungo, siconsente alle eliche di provare ad accoppiarsi formando alcuni legami ad idrogeno:se l’appaiamento e coretto, la formazione dei primi legami porta vicine fra loroaltre basi complementari che possono formare cosı altri legami, per cui le catenesi chiudono rapidamente come se fossero una cerniera lampo dando luogo ad unadoppia elica stabile, identica a quella di partenza: si e verificata la rinaturazione(Figura 24).La sola cosa che conta ai fini della formazione della doppia elica, e la presenzadi sequenze complementari, per cui la rinaturazione avviene anche se le cateneprovengono da DNA diversi: tale fenomeno prende il nome di ibridazione

AT G CG A GC G TA T GA T CT G

TA C GC T CG C AT A CT A GA C

3’ 5 ’

3 ’5 ’

AT G

C

G

A GC G TA T

G

A

T CT G

TA C

G

C

T CG C AT A

C

T

A GA C

3’

3 ’5 ’

5 ’

AT G CG A GC G TA T GA T CT G

3’ 5 ’

TA C GC T CG C AT A CT A GA C

3’5 ’

S i n g o l e c a t e n ed i nuc leo t i d i

D N A a d o p p i o f i l a m e n t o

I n i z i o d e l p r o c e s s od i d e n a t u r a z i o n e

Figura 23: denaturazione

26

Page 27: DNA COMPUTING - profs.sci.univr.itprofs.sci.univr.it/~manca/mnc/dna-computing-08.pdf · 6 Teoria dei Linguaggi Formali ... Questa ridondanza di informazione µe di fondamentale ...

AT G CG A GC G TA T GA T CT G

TA C GC T CG C AT A CT A GA C

3’ 5 ’

3 ’5 ’

AT G CG A GC G TA T GA T CT G

3’ 5 ’

TA C GC T CG C AT A CT A GA C

3’5 ’

AT G CG A GC G TA T GA T CT G

3’ 5 ’

TA C GC T CG C AT A CT A GA C

3’5 ’

D u e f i l a m e n t i s e p a r a t i

A p p a i a m e n t o c o r r e t t o

T e n t a t i v o d i a p p a i a m e n t o

Figura 24: rinaturazione

3.3 Amplificazione con PCR

La reazione a catena della DNA polimerasi detta PCR (Polymerase Chain Reac-tion) e una tecnica introdotta nel 1985 da Kary Millis che consente di amplificarein modo specifico e selettivo una stringha di DNA.Per amplificare una striga di DNA e indispensabile disporre di un nucleotide com-plementare alla estremita della sequenza di partenza (primer). La sintesi richiedepertanto che sia nota almeno la sequenza nucleotidica di brevi zone adiacenti allasequenza da amplificare.La PCR consiste di vari cicli di amplificazione e ogni ciclo e costituito da tre fasi:denaturazione, appaiamento (annealing) e sintesi.In breve la duplicazione e completamente svolta dall’enzima Polimerasi (ad esempiol’enzima TAQIII, Termo Acquaticus III), il quale una volta identificato un innesco(Primer), inizia a duplicare la parte complementare del filamento mancante leggen-do l’altro filamento (Figura 25).Gli ingredienti principali per la PCR sono il DNA campione, i primer, i nucleotidi

5’

5 ’

3 ’

3 ’

m o l e c o l a d a d u p l i c a r e

p r i m e r

p a r t e a g g i u n t a d a l T A G I I I

Figura 25: polimerasi

trifosfati (A,T,C,G) e il TaQIII. La reazione di amplificazione avviene tramite cicli

27

Page 28: DNA COMPUTING - profs.sci.univr.itprofs.sci.univr.it/~manca/mnc/dna-computing-08.pdf · 6 Teoria dei Linguaggi Formali ... Questa ridondanza di informazione µe di fondamentale ...

sequenziali ed e una reazione a catena in cui i filamenti neosintetizzati agiscono dastampo per l’ulteriore sintesi di DNA nel ciclo successivo.La procedura e la seguente:

• Si parte da una molecola bersaglio < α . . . β >, ma come si e gia detto nonsi lavora mai con singole molecole, ma con pool di DNA.

• Denaturazione: si innalza la temperatura a 90◦C per facilitare la denatu-razione (Figura 26)

a b

ba

a b

ba

Figura 26: denaturazione di < α . . . β >

• Annealing: si disegnano i primer α e β e si abbassa la temperatura attornoai 30◦C per facilitare l’appaiamento per complementarieta con i filamentitemplate (Figura 27)

a b

ba

b a

Figura 27: Annealing con i primers

• Sintesi: si porta la temperatura attorno ai 70◦C per un certo tempo per fa-cilitare il lavoro della polimerasi (Figura 28): il TaqIII, partendo dal primer,aggiunge i singoli nucleotidi (sparsi nella soluzione del pool) che sono com-plementari al filamento template.

a b

ba

b ataq I I I

taq I I I

A GCT

A GCT

Figura 28: Estensione

Iterando il processo per n volte si ottengono 2n copie.

Nota:La PCR copia un filamento template, aggiungendo nucleotidi, sempre nella direzione

28

Page 29: DNA COMPUTING - profs.sci.univr.itprofs.sci.univr.it/~manca/mnc/dna-computing-08.pdf · 6 Teoria dei Linguaggi Formali ... Questa ridondanza di informazione µe di fondamentale ...

5′−3′ e mai nella direzione 3′−5′ (Figura 29); piu precisamente il filamento, lungoil quale le basi sono scansite, e percorso dall’enzima nella direzione 3′ − 5′, ma lascrittura avviene nel neofilamento in direzione 5′ − 3′.

G G A G A T C C G AC C T C T A G G C T A A G C T A G G A C C A T T A C G

T T C G A T C C T G G5’3 ’

A G C C T A G A G GG G T C C T A G C T TG C A T T A C C A G G A T C G A A T C G G A T C T C C

o p p u r e

3’

5 ’

A g g i u n t a d i n u c l e o t i d i :

N e s s u n a a g g i u n t a d i n u c l e o t i d i :

G A G G A C A T C C G A T T C A G G A G T A C C5’C T C C T G T A G G3’

o p p u r e

G G A T G T C C T CC C A T G A G G A C T T A G C C T A C A G G A G

3’5 ’

Figura 29: Direzione di sintesi

Algoritmo per PCR:

PCR(P,n){let Type(P) = {<a...b>,c,d} //<a..b>: tipo del template; c,d: primersinput Pfor i = 1,n do

{P:= denature(P)P:= hybridize(P)P:= extend(P)

}output P

}

29

Page 30: DNA COMPUTING - profs.sci.univr.itprofs.sci.univr.it/~manca/mnc/dna-computing-08.pdf · 6 Teoria dei Linguaggi Formali ... Questa ridondanza di informazione µe di fondamentale ...

3.3.1 Alberi PCR

La visualizzazione della PCR tramite alberi e particolarmente utile per osservarecosa accade quando la forma e la posizione delle molecole risulta essere complessa.Si dimostra che tra le molecole che vengono duplicate esponenzialmente, c’e ne sarasicuramente una di tipo blunt; si avranno tante forme diverse, ma una o piu sarannoblunt. La forma della molecola blunt sara delimitata dai primers considerando iltemplate superiore (Figura 30)

ay b 2

b 1 b 2y

Figura 30: Regola molecola blunt

Esempio.Con riferimento alla Figura 31a, nel primo ciclo della PCR, la molecola templatesi divide e i filamenti 1 e 2 si attaccano ai relativi primer, e dopo il lavoro dellapolimerasi si ottengono le molecole descritte nella Figura 31b.Al secondo ciclo le molecole cosı ottenute si separano e i filamenti 1 e 2 si riattaccanocon i primer (infatti sono i template di partenza) e si ottengono le stesse molecoleottenute al passo precedente. I filamenti 3 e 4 non si attaccano ai primers perche nonsono complementari (rispetto ai primers), pero si appaiano nella loro parte comunee la polimerasi completa i filamenti ottenendo cosı una molecola blunt (Figura 31c).

30

Page 31: DNA COMPUTING - profs.sci.univr.itprofs.sci.univr.it/~manca/mnc/dna-computing-08.pdf · 6 Teoria dei Linguaggi Formali ... Questa ridondanza di informazione µe di fondamentale ...

1

2

a )

1

2

3

4

b )

3

4

c )

p r i m e r

p r i m e r

M o l e c o l e o t t e n u t e a l p r imo c i c l o

M o l e c o l e o t t e n u t e a l s e c o n d o c i c l o

1

2

Figura 31: esempio blunt

Nota:Quando si scrive α significa che si sta leggendo un filamento singolo da 5′ a 3′; seinvece si vuole leggere in notazione doppia si deve scrivere α

rev(α)

Alcuni alberi PCR:

Esempio 1 , Figura 32

Figura 32: Albero pcr esempio 1

31

Page 32: DNA COMPUTING - profs.sci.univr.itprofs.sci.univr.it/~manca/mnc/dna-computing-08.pdf · 6 Teoria dei Linguaggi Formali ... Questa ridondanza di informazione µe di fondamentale ...

Esempio 2 , Figura 33

2

2

1

1

D a q u e s t o l a t o ,da qu i i n po i , s i o t t e n g o n o s e q u e n z e tu t t e ugua l i .

Figura 33: Albero pcr esempio 2

Esempio 3 , Figura 34

2

1

1

2

3

4

3

45

5

2

A l t e r z o p a s s o s i è o t t e n u t al a m o l e c o l a b l u n t l a c u i l u n g h e z z a è q u e l l a d e l i m i t a t a d a i d u e p r i m e r s u l l a m o l e c o l a i n i z i a l e

Figura 34: Albero pcr esempio 3

32

Page 33: DNA COMPUTING - profs.sci.univr.itprofs.sci.univr.it/~manca/mnc/dna-computing-08.pdf · 6 Teoria dei Linguaggi Formali ... Questa ridondanza di informazione µe di fondamentale ...

Altri esempi di forme di PCR:

Sticky end 3’-3’ La polimerasi lavora nel verso 5’-3’ e con molecole con Stickyends 3’-3’, la PCR non fa nulla (Figura 35)

3’

3 ’

5 ’

5 ’

Figura 35: Albero pcr Sticky end 3’-3’

Sticky end 5’-5’ Con Sticky ends 5’-5’ la polimerasi completa i filamenti (Figura36)

3’

3 ’

5 ’

5 ’

Figura 36: Albero pcr Sticky end 5’-5’

Blunt Ad ogni passo la polimerasi lavora solo sul filamento inferiore e scarta quellosuperiore. In questo caso si ha una amplificazione lineare (Figura 37)

3’

3 ’

5 ’

5 ’

3 ’ 5 ’

3 ’ 5 ’

Figura 37: Albero pcr blunt

Forma a Y Anche in questo caso si ha una amplificazione lineare in quanto leparti nuove non possono essere appaiate dai primers, mentre quelle vecchiesi (Figura 38)

Forma a Y Altro esempio di molecola a forma di Y (Figura 39)

33

Page 34: DNA COMPUTING - profs.sci.univr.itprofs.sci.univr.it/~manca/mnc/dna-computing-08.pdf · 6 Teoria dei Linguaggi Formali ... Questa ridondanza di informazione µe di fondamentale ...

1

1

n e w

o l d

2

2

n e w

o l d

Figura 38: Albero pcr y-y

Figura 39: Albero pcr y

3.4 Altre operazioni: Ligasi, Fish, Infix-Suffix

ligasi. Concatena le stringhe aggiungendo un legame fosforico.La ligazione e unprocesso di saldatura di frammenti di DNA e avviene grazie ad un enzimadenominato DNA Ligasi. La ligazione tra molecole di DNA, e indispensabileper effettuare il clonaggio molecolare (vedi Paragrafo 3.5).

Esempio.In riferimento alla Figura 40 la polimerasi allunga il primer complementareal template, poi l’enzima ligasi concatena il neofilamento con il filamentoaccanto. Si puo dire che la polimerasi chiude i “buchi“ grandi e la ligasii “buchi“ piccoli. Con la notazione introdotta possiamo esprimere la ligasicome segue:α→β→

γ ⇒ αβ→γ . La ligasi toglie l’ossidrile in posizione 3′ e forma un’unica

catena.

P o l i m e r a s iC o l l e g a m e n t o p e rL i g a s i

A l l u n g a m e n t o p e r

Figura 40: Ligasi

34

Page 35: DNA COMPUTING - profs.sci.univr.itprofs.sci.univr.it/~manca/mnc/dna-computing-08.pdf · 6 Teoria dei Linguaggi Formali ... Questa ridondanza di informazione µe di fondamentale ...

fish. Si tratta di un pescaggio dei filamenti desiderati, ovvero identifica una specifi-ca sequenza di DNA. Si effettua l’ancoraggio del complementare della parolache si vuole pescare, la si immerge nella popolazione e i filamenti che cor-rispondono al template si attaccheranno. Questa operazione si basa sullaibridazione molecolare.

ibridazione molecolare. Permette di evidenziare la presenza di una specifica se-quenza di DNA all’interno di un pool. Si basa sulla proprieta della molecoladi DNA di poter subire i processi di denaturazione e rinaturazione. In con-dizioni opportune di temperatura i singoli filamenti che presentano sequenzedi basi complementari possono appaiarsi e dare origine a molecole a doppiofilamento, ovvero possono ibridare tra di loro2.

Per poter individuare un dato filamento di DNA occorre disporre di unamolecola detta sonda, che contiene la sequenza complementare a quella chesi e interessati. La sonda viene denaturata a singolo filamento e immersain un pool anch’esso denaturato. A questo punto la sonda potra appaiarsial filamento complementare presente tra le migliaia di filamenti non com-plementari. Si forma cosı un ibrido molecolare a l’avvenuta ibridazione puoessere evidenziata mediante un opportuno sistema di rilevazione ad esempiotramite radiografia se le sonde sono state marcate con elementi radioattivi.

infix-suffix. Se si vuole duplicare una molecola blunt, si deve conoscere la porzionedi DNA corrispondente alla testa e alla coda per poi utilizzare i loro comple-mentari come primers. Non sempre e possibile avere questa conoscenza, cosısi aggiunge al filamento un prefisso e un suffisso per poi usare i loro comple-mentari come primers (Figura 41).

a b

a b

a b

b

a b

a

Figura 41: infix-suffix

Questa operazione utilizza la ligasi. Se non si conosce la sequenza dellamolecola N, grazie all’infix, la posso prefissare e sufissare riprendendo il con-trollo della molecola: αNβ.Innanzitutto si prendono due molecole note α e β e gli si leva il fosforo nellaestremita 5’ per ridurre la possibilita di aggancio, quindi la ligasi puo operaresolamente tra la punta e la coda (Figura 42). Una volta avvenuta la ligasi, lapolimerasi produrra una molecola doppia allungando i singoli filamenti.A questo punto si ha il completo controllo della molecola poiche si ha laconoscenza delle parti terminali ed e possibile progettare i primers in mo-do opportuno per applicare la PCR e amplificare la molecola: PCR(α, β)(Figura 43).

2L’appaiamento avviene per formazione di legami di idrogeno tra le basi complementariappaiate

35

Page 36: DNA COMPUTING - profs.sci.univr.itprofs.sci.univr.it/~manca/mnc/dna-computing-08.pdf · 6 Teoria dei Linguaggi Formali ... Questa ridondanza di informazione µe di fondamentale ...

a

b

M o l e c o l a N

+

b o r a

a o r b

Figura 42: Possibili agganci di infix-suffix

ba

a

b

a

b

A l l u n g a m e n t o p e r P C R

Figura 43: progettazione primer

3.5 Amplificazione con clonaggio molecolare

Tramite clonaggio molecolare e possibile isolare un singolo gene o in generale unframmento di DNA e produrne molte copie identiche. Per clonare un filamento diDNA occorre inserirlo in un vettore di clonaggio tramite il processo di ligazione. Ivettori ricombinati vengono successivamente introdotti in idonee cellule ospiti (cel-lule batteriche o di lievito), ottenendo una grande collezione di cloni ricombinati cheviene detta libreria di DNA. Dopo aver costruito una libreria, occorre identificarela sequenza di DNA che contiene il gene.

L’amplificazione, effettuata tramite clonaggio o PCR, permette di ottenere inentrambi i casi molte copie di una sequenza di DNA; tuttavia dono diversi i prin-cipi e i metodi: con la clonazione si usa la macchina genetica della natura, ovvero ibatteri; la PCR invece permette di fotocopiare in modo sintetico (con un processosemplice, poco costoso e soprattutto programmabile) attraverso il meccanismo deiprimers che sono i segnali che dirigono il fenomeno amplificativo.

3.5.1 Vettori di clonaggio

Sono molecole di DNA in grado di replicarsi autonomamente in una cellula ospite.In tali molecole e possibile inserire, in una posizione nota, i frammenti di DNA daclonare. I singoli vettori ricombinati possono essere introdotti in una cellula ospite(cellula batterica o di lievito) nella quale veicolano il frammento di DNA preceden-temente inserito. In tali cellule i singoli vettori replicano il proprio DNA e quellodel frammento in esso integrato. Metaforicamente il vettore e come se fosse un buscontenente un passeggero; il bus entra in un box specializzato (cellula) che in pochiistanti replica il bus stesso compreso il passeggero. In questo modo quando la cellulabatterica si divide, porta con se i plasmidi compreso il DNA target.

Esistono quattro tipi di vettori di clonaggio: i plasmisi, i batteriofagi, i cosmidie i cromosomi artificiali di lievito. I primi tre usano come cellula ospite il batte-

36

Page 37: DNA COMPUTING - profs.sci.univr.itprofs.sci.univr.it/~manca/mnc/dna-computing-08.pdf · 6 Teoria dei Linguaggi Formali ... Questa ridondanza di informazione µe di fondamentale ...

rio Escherichia Coli (comunemente chiamato E.Coli), mentre il quarto il communelievito di birra. Tali vettori sono in grado di effettuare una replicazione autono-ma nelle cellule ospiti, presentano piu siti di taglio per enzimi di restrizione incorrispondenza dei quali inserire i frammenti di DNA da clonare (la regione dellacellula che contiene i siti si chiama polylinker), inoltre contengono uno o piu mar-catori selettivi per distinguere le cellule ospiti che contengono il vettore da quelleche non lo contengono; un marcatore selettivo potrebbe essere un gene resistentead un antibiotico.La scelta dei vettori dipende dalle dimensioni dei filamenti di DNA che si e inter-essati a clonare.

3.5.2 Enzimi di restrizione

La scoperta degli enzimi di restrizione ha reso possibile la tecnologia del DNA ri-combinante. Sono enzimi di origine batterica in grado di tagliare una molecola diDNA a doppia elica in corrispondenza di specifiche sequenze di basi. Questi enzimiservono ai batteri per difendersi dall’invasione di virus, in quanto riconoscono edegradano ogni DNA estraneo che penetra nella cellula.

La sequenza di coppie di basi riconosciuta da un enzima di restrizione prende ilnome di sito di restrizione. Ogni enzima riconosce uno specifico sito che in generee un palindromo3

I siti di restrizione possono essere costituite da 4 o 6 o piu coppie di nucleotidie le modalita di taglio possono essere le seguenti:

• esattamente al centro, generando estremita piatte

• in modo asimmetrico, generando estremita a singolo filamento (estremitacoesive o appiccicose) sporgenti verso il 5’

• in modo asimmetrico, generando estremita a singolo filamento, sporgentiverso il 3’

Esempi di enzimi di restrizione:

Enzima Sequenza di riconoscimentoHaeIII 5′GG•CC3′

3′CC•GG5′

HbaI GC•GCC•GCG

HpaII C•CGGGGC•C

ecoRI G•AATTCCTTAA•G

3In linguistica il palindromo e una parola che rimane identica sia se letta da sinistraverso destra che viceversa. Nel caso di DNA, palindromo e una sequenza di nucleotidi asimmetria binaria che presenta la stessa sequenza di basi se letta in direzione 5’-3’ sia suun’elica sia sull’altra; esempio 5′GGTACC3′

3′CCATGG5′

37

Page 38: DNA COMPUTING - profs.sci.univr.itprofs.sci.univr.it/~manca/mnc/dna-computing-08.pdf · 6 Teoria dei Linguaggi Formali ... Questa ridondanza di informazione µe di fondamentale ...

In Figura 44 vediamo alcuni esempi di taglio con altri enzimi di restrizione.

5 ’ C C C G G G 3 ’

3 ’ G G G C C C 5 ’

5 ’ C C C

3 ’ G G G C C C 5 ’G G G 3 ’

5 ’ G G A T C C 3 ’

3 ’ C C T A G G 5 ’

5 ’ G

3 ’ C C T A G 5 ’

5 ’ G A T C C 3 ’G 5 ’

5 ’ C T G C A G 3 ’3 ’ G A T G T C 5 ’

5 ’ C T G C A 3 ’3 ’ G

G 3 ’

3 ’ A C G T C 5 ’S t i k y e n d 3 ’

S t i k y e n d 5 ’

Es t r em i t a ’ p i a t t eT a g l i o c o nS m a I

T a g l i o c o nB a m H I

T a g l i o c o nPs t I

Figura 44: Esempi di taglio con enzimi di restrizione

38

Page 39: DNA COMPUTING - profs.sci.univr.itprofs.sci.univr.it/~manca/mnc/dna-computing-08.pdf · 6 Teoria dei Linguaggi Formali ... Questa ridondanza di informazione µe di fondamentale ...

3.5.3 Plasmidi

I plasmidi sono molecole circolari di DNA presenti nei batteri. Queste molecolenon sono strettamente necessarie alla vita del batterio, ma possiedono dei geni chepossono fornire caratteristiche aggiuntive al batterio che ne possiede; tipicamentequesti geni codificano la resistenza ad un antibiotico. Inoltre i plasmidi, essendodotati di un’origine per la replicazione, hanno la capacita di replicarsi autonoma-mente all’interno di una cellula, e i loro geni vengono espressi indipendentementedal cromosoma principale. I geni vengono cosı trasmessi alle cellule figlie nella di-visione cellulare, conferendogli lo steso vantaggio.I plasmidi possono essere riprodotti in laboratorio e progettati in modo da averecaratteristiche aggiuntive rispetto a quelli naturali. In Figura 45 vediamo un gener-ico plasmide in cui sono evidenziate le caratteristiche principali dove AR e BR sonoi geni capaci di conferire resistenza a un antibiotico.I plasmidi si replicano in modo autonomo rispetto al cromosoma che contiene l’in-

O r i g i n e r e p l i c a z i o n e ( o r i )

A

B

R

R

P s t I

E c o R IB a m H I

S i t i d i t ag l i o pe r enz im i d i r es t r i z i one

Figura 45: Caratteristiche principali di un vettore plasmidico

formazione genetica principale, ma il principio e lo stesso, ovvero tramite l’enzimaDNA polimerasi, quindi durante la divisione cellulare i plasmidi vengono trasferitida una cellula all’altra come mostrato in Figura 46.Grazie agli enzimi di restrizione in grado di tagliare il DNA in corrispondenza di

sequenze specifiche, e possibile utilizzare i plasmidi per introdurre nei batteri delDNA esogeno al fine di produrre proteine o per amplificare tratti di DNA. La Figura47 rappresenta il taglio di un plasmide e di un DNA esogeno tramite un enzima direstrizione. La successiva ligazione tramite l’enzima ligasi tra il plasmide e il DNAestraneo, forma una molecola chiamata plasmide ricombinato.

39

Page 40: DNA COMPUTING - profs.sci.univr.itprofs.sci.univr.it/~manca/mnc/dna-computing-08.pdf · 6 Teoria dei Linguaggi Formali ... Questa ridondanza di informazione µe di fondamentale ...

C r o m o s o m a

P l a s m i d e

Figura 46: Trasferimento del DNA plasmidico

AR

3’

5 ’ 3 ’

5 ’

3 ’5 ’

F r a m m e n t i d i D N A e s o g e n o

V e t t o r e d i c l o n a g g i oT a g l i o i n c o r r i s p o n d e n z a d i u ns i t o d i r es t r i z i one

Figura 47: Ligazione tra molecole di DNA

3.5.4 Algoritmo di clonazione

Le tecniche di clonaggio consistono di inserire un frammento di DNA in un vettore,introdurre la nuova molecola in una cellula ospite e successivamente isolare il cloneche contiene la molecola di DNA ricombinante.L’algoritmo dettagliato e il seguente:

1. Si sceglie un vettore circolare (plasmide) che include un gene che codifica laresistenza ad un antibiotico A ed un gene per la resistenza ad un antibioticoB.

2. Si linearizza il vettore tagliandolo con un enzima di restrizione in un sito checompare una volta sola e che interrompe la sequenza del gene che codifical’antibiotico B. Ad esempio supponiamo che tale gene sia codificato dalla se-quenza

5′TTTCCCGAATTCAAA3′3′AAAGGGCTTAAGTTT5′

si applica un enzima di restrizione che spezza tale sequenza eliminando lapossibilita di produrre la proteina che produce la resistenza e di conseguenzail plasmide diviene vulnerabile a tale antibiotico (Figura 48)

40

Page 41: DNA COMPUTING - profs.sci.univr.itprofs.sci.univr.it/~manca/mnc/dna-computing-08.pdf · 6 Teoria dei Linguaggi Formali ... Questa ridondanza di informazione µe di fondamentale ...

Figura 48: Taglio del plasmide

3. Si adatta il frammento da amplificare con infix-suffix, in modo da avereestremita complementari a quelle del plasmide linearizzato (Figura 49)

A A T T C

G C T T A AG

Figura 49: Adattamento DNA esogeno

4. Si collegano vettore e frammento per opera della ligasi ottenendo plasmidiricombinati (Figura 50) L’enzima DNA ligasi salda le estremita compatibili

A A T T C

G C T T A AG

Figura 50: Collegamento per ligasi

41

Page 42: DNA COMPUTING - profs.sci.univr.itprofs.sci.univr.it/~manca/mnc/dna-computing-08.pdf · 6 Teoria dei Linguaggi Formali ... Questa ridondanza di informazione µe di fondamentale ...

di DNA, senza selezionare le molecole a cui le estremita appartengono. Infattisi possono creare due tipi diversi di molecole in grado di replicarsi una voltainseriti nella cellula:

(a) DNA ricombinante ovvero plasmide con inserto DNA esogeno

(b) Plasmide circolare puro ovvero il taglio dell’enzima di restrizione si erisaldato, per ligasi infatti puo avvenire la reazione del plasmide con sestesso (Figura 51).

5 ’ T T T C C C G A A T T C A A A 3 ’3 ’ A A A G G G C T T A A G T T T 5 ’

5 ’ A A T T C X X X X X G 3 ’ 3 ’ G X X X X X C T T A A 5 ’

5 ’ T T T C C C G 3 ’3 ’ A A A G G G C T T A A 5 ’

5 ’ A A T T C A A A 3 ’ 3 ’GTTT5 ’

T a g l i o c o n e n z i m a d i r e s t r i z i o n e

P L A S M I D E

I N S E R T O

5 ’ T T T C C C G A A T T C A A A 3 ’3 ’ A A A G G G C T T A A G T T T 5 ’

A p p a i a m e n t o e L i g a s id e l p l a s m i d e c o n s e s t e s s o

A p p a i a m e n t o e L i g a s id e l p l a s m i d e c o n l ’ i n s e r t o

5 ’ T T T C C C G A A T T C X X X X X G A A T T C A A A 3 ’3 ’ A A A G G G C T T A A G X X X X X C T T A A G T T T 5 ’

Figura 51: Due tipi di appaiamento per ligasi

5. Si infetta un batterio non resistente all’antibiotico A con il plasmide ricom-binato, sfruttando il fenomeno della infezione univoca (al piu un plasmideentra nella menbrana batterica). Attenzione, in questa fase possono entrarenei batteri anche i plasmidi puri come descritto al passo precedente. E danotare che solo una minoranza di batteri assume DNA esogeno (circa 1 su10.000), per cui i batteri che ospitano il plasmide ricombinato devono essereindividuate tra le numerose cellule non trasformate.

6. I batteri vengono posti in pozzetti di crescita separati (un batterio per pozzet-to) il cui nutrimento contiene l’antibiotico A; l’antibiotico uccide tutti i bat-teri privi di plasmide. Dopo ripetute divisioni cellulari si ha la formazionedi una colonia di tali batteri. Derivando da una singola cellula originaria,tutte le cellule hanno il medesimo patrimonio genetico, per cui si parla dicloni cellulari (i batteri hanno dimensioni che permettono l’individuazione disingole unita ). Vedi Figura 52

7. Si selezionano nella colonia i batteri resistenti all’antibiotico A, che costitu-iscono una colonia M

42

Page 43: DNA COMPUTING - profs.sci.univr.itprofs.sci.univr.it/~manca/mnc/dna-computing-08.pdf · 6 Teoria dei Linguaggi Formali ... Questa ridondanza di informazione µe di fondamentale ...

D N A c r o m o s o m i c oP l a s m i d er i c o m b i n a t o

B a t t e r i o I b a t t e r i c h e n o n c o n t e n g o n oi p a s m i d i m u o i o n o a c o n t a t t o c o nl ’an t ib io t i co A

C O L T U R A C O N A N T I B I O T I C O T I P O A

M o l t i p l i c a z i o n e c e l l u l a r e

Figura 52: Coltura con antibiotico A

8. Dei batteri sopravvissuti si preleva un batterio da ciascun clone in modo dacostruire, dopo crescita in coltura, una colonia mirror M’ della colonia M(Figura 53)

1

2 3

4

56

7

8

C o l o n i a M d i c l o n i s o p r a v v i s s u t ia l l ’ an t ib io t i co A

1

2 3

4

5

7

8

C o l o n i a M ’ .E ’ u n a c o p i a c o n f o r m ea l l a c o l o n i a M

6

P o z z e t t i con tene t i i c l on i

Figura 53: Colonia mirror M’ di M

9. Si espone M’ all’antibiotico B per discriminare i bateri resistenti a tale antibi-otico da quelli non resistenti (Figura 54). Applicando l’antibiotico al mirror sivede chi muore in seguito alla sua azione. Se nel mirror muoiono le cellule neipozzetti 2, 5, 8 allora nella colonia originale, negli stessi pozzetti, deve essercil’inserto (che ha interrotto il gene che sviluppa la resistenza a B)

10. A questo punto dalla mappa della sopravvivenza in M’ si puo capire quali

43

Page 44: DNA COMPUTING - profs.sci.univr.itprofs.sci.univr.it/~manca/mnc/dna-computing-08.pdf · 6 Teoria dei Linguaggi Formali ... Questa ridondanza di informazione µe di fondamentale ...

1

3

4

7

D o p o l ’ e s p o s i z i o n ea l l ’ an t ib io t i co B s o p r a v v i v o n o s o l o l e c o l o n i eres i s ten t i a t a l e an t i b i o t i co , ovve roq u e i b a t t e r i n o n r i c o m b i n a t i

6

Figura 54: Esposizione all’antibiotico B

sono i batteri di M che sono resistenti a B. Si prelevano da M tali batterie si pongono in una coltura C; tutti questi batteri contengono il plasmidericombinato. (Figura 55)

1

3

4

7

6

2 3

4

56

7

8

1

D a l l a m a p p a t u r a d i M ’ s i d e d u c e c h e i n Mi p o z z e t t i 2 , 5 , 8 c o n t e n g o n o c l o n i c o n p l a s m i d i r i c o m b i n a t i

C o l o n i a M ’ C o l o n i a M

Figura 55: Individuazione dei cloni con inserto

11. Per lisi si elimina la membrana dei batteri di C e si filtra il contenutotrattenendo i plasmidi ricombinati.

12. Nel pool dei plasmidi ricombinati si agisce con l’enzima di restrizione in mododa separare il frammento inserito dal vettore originale. Quindi per elettro-foresi si selezionano i filamenti di lunghezza uguale a quella del frammentoiniziale da amplificare.

Considerazioni.

La chiave dell’algoritmo sta nel fatto che il sito dell’enzima di restrizione e al-l’interno del gene dell’antibiotico B, cosı quando un frammento di DNA esogenoviene inserito in quel punto, la funzionalita del gene viene eliminata. Poi tutte lecellule del batterio con plasmide trasformato o no, possono svilupparsi in presenzadell’antibiotico A. Ma le cellule del batterio che contiene il plasmide ricombinatocon DNA esogeno non sara mai in grado di svilupparsi in presenza dell’antibiotico B.

Tuttavia, in modo meno preciso si puo recuperare il frammento di DNA esogenosenza operare la seconda selezione con l’antibiotico B. In questo caso l’algotimodiventa il seguente; brevemente:

44

Page 45: DNA COMPUTING - profs.sci.univr.itprofs.sci.univr.it/~manca/mnc/dna-computing-08.pdf · 6 Teoria dei Linguaggi Formali ... Questa ridondanza di informazione µe di fondamentale ...

1. Linearizzazione

2. Inserimento del passeggero

3. Infezione dei batteri non resistenti all’antibiotico A con plasmidi ricombinati

4. Produzione della colonia di batteri in presenza dell’antibiotico A

5. Selezione dei batteri ricombinati, ovvero la colonia sviluppata al passo 4

6. Recupero dei plasmidi per lisi della cellula

7. Rimozione inserto con enzima di restrizione ed elettroforesi

45

Page 46: DNA COMPUTING - profs.sci.univr.itprofs.sci.univr.it/~manca/mnc/dna-computing-08.pdf · 6 Teoria dei Linguaggi Formali ... Questa ridondanza di informazione µe di fondamentale ...

3.6 Sequenziamento

Sequenziare un frammento di DNA significa leggere la successione di basi che essocontiene individuando l’ordine con cui A,C,G,T si alternano. Negli anni settan-ta sono state sviluppate due tecniche. Un metodo, messo a punto da Maxam eGilbert utilizza un processo di degradazione chimica del DNA; l’altro e stato messoa punto da Sanger e utilizza un approccio di tipo enzimatico. Per tale contributoquesti ricercatori condivisero il premio Nobel.Il metodo di Sanger ha subito nel tempo molti miglioramenti rendendolo robusto,affidabile e automatizzabile. Tuttavia questa tecnica ha delle limitazioni per tuttequelle operazione che necessitano di un elevato flusso di informazioni. Nel frattem-po sono stati studiati metodi alternativi come il sequenziamento per ibridizzazione,sequenziamento per firma parallela basato sulla ligazione e il pyrosequencing. Ilpyrosequencing sta avendo una notevole diffusione in quanto risulta essere estrema-mente rapido, totalmente automatizzabile e soprattutto a basso costo.

Nei prossimi paragrafi verranno analizzate in dettaglio le tecniche piu utilizzate,ovvero il metodo di Sanger e il pirosequenziamento, ma per capire meglio il lorofunzionamento risulta utile un breve ripasso di alcuni concetti riguardo le reazionichimiche e del ruolo importantissimo degli enzimi catalizzatori.

3.6.1 L’energia di attivazione delle reazioni chimiche

Tutte le reazioni per avvenire spontaneamente, devono svolgersi con liberazionedi energia (devono cioe possedere un ∆E negativo): in altre parole, il contenutoenergetico dei prodotti deve essere inferiore a quello dei reagenti. Ma il fatto cheun processo possibile (spontaneo) dal punto di vista termodinamico non implicanecessariamente che esso si verifichi con velocita apprezzabile in ogni condizione.Supponiamo di prendere in esame una reazione spontanea tra i composti A-B eC-D, che dia come prodotti i composti A-D e B-C.E chiaro che per formare il composto A-D e necessario rompere gli altri legami. Larottura di un legame chimico tra due atomi richiede energia almeno per destabiliz-zare i legami esistenti che devono dare origine ai nuovi composti. Questo si verificanel momento in cui le molecole dei reagenti collidono tra di loro per dare luogo allareazione: se l’energia e sufficiente si forma il cosiddetto complesso di attivazione, nelquale i vecchi legami sono resi instabili, mentre i nuovi cominciano a formarsi; e unasorta di stato intermedio tra quello iniziale e quello finale. L’energia necessaria allaformazione del complesso e detta energia di attivazione. Il complesso di attivazionesi trova cosı ad un livello energia superiore quello dei reagenti. Una volta formato,il complesso puo sia tornare indietro, riformando i reagenti, sia andare avanti, for-mando i prodotti della reazione.L’energia di attivazione rappresenta un ostacolo allo svolgimento della reazione: sele molecole dei reagenti non posseggono energia sufficiente a superare tale ostacolo,la reazione, pur essendo possibile non puo avvenire.Ora, l’energia che consente alle molecole di superare la barriera deriva dall’energiacon cui esse si muovono e collidono (energia cinetica), che a sua volta dipende dallatemperatura del sistema (tanto piu alta e la temperatura, tanto maggiore e l’ener-gia cinetica delle molecole). Alla temperatura ambiente, che caratterizza la materiavivente, l’energia delle molecole e mediamente insufficiente a consentire loro di su-perare la barriera di attivazione per la stragrande maggioranza delle reazioni, e

46

Page 47: DNA COMPUTING - profs.sci.univr.itprofs.sci.univr.it/~manca/mnc/dna-computing-08.pdf · 6 Teoria dei Linguaggi Formali ... Questa ridondanza di informazione µe di fondamentale ...

quindi queste, anche se teoricamente possibili, di fatto non avvengono, se non inmisura infinitamente piccola.Inoltre occorre che la collisione tra gli stomi avvenga in modo giusto. Se cio non ac-cade, puo avvenire una reazione diversa, che porta alla formazione di sottoprodotti,oppure ad un aborto della reazione stessa.

3.6.2 Gli enzimi catalizzatori

In un sistema che debba rimanere a temperatura costante e relativamente bassa,come la materia vivente, il solo modo di aggirare questi problemi e quello di ricorrereai catalizzatori, cioe sostanze che si ritrovano inalterate al termine della reazionee che sono capaci di accelerarne lo svolgimento abbassando l’energia di attivazione,cosı che le molecole deo reagenti, pur avendo una energia cinetica bassa, sono ingrado ugualmente di effettuare la reazione. Questi catalizzatori sono gli enzimi.Glienzimi sono estremamente specializzati, in quanto ciascuno di essi catalizza un solotipo di reazione utilizzando un ristretto numero di composti simili tra loro, dettisubstrati; in molti casi il substrato e rappresentato da un singolo composto.

Alla base del meccanismo degli enzimi sta il fatto che il substrato si combi-na temporaneamente con l’enzima per formare un complesso enzima-substrato. Lacombinazione non avviene a caso, ma in corrispondenza di una specifica zona dellasuperficie dell’enzima, detta sito attivo o sito catalitico. Esso e costruito in mododa riconoscere proprio i substrati ad esso dedicati.Grazie alla formazione del complesso enzima-substrato, le molecole dei substrativengono orientate nello spazio nel modo corretto per lo svolgimento della reazione,esoprattutto, sempre nelle molecole dei substrati, avviene una serie di modificazioniche favoriscono il complesso di attivazione. In questo modo si abbassa l’energia diattivazione. una volta avvenuta la reazione, il complesso enzima-substrato divienecomplesso enzima-prodotti della reazione. Questi si distaccano dall’enzima, che ri-torna nella situazione iniziale e puo tornare a combinarsi con nuove molecole disubstrato, iniziando un nuovo ciclo detto di catalisi (Figura 56)

EE n z i m a

SS u b s t r a t o

E-S C o m p l e s s oe n z i m a - s u b s t r a t o

E-P C o m p l e s s oe n z i m a - p r o d o t t i

EE n z i m a

PP r o d o t t i

+

Figura 56: catalisi

3.6.3 ATP

Il composto adenosintrifosfato (ATP4), o altri nucleotidi equivalenti, costituisce laforma di energia immediata per tutte le forme di lavoro svolte dalla materia vivente.

4Si ricorda che alcuni nucleotidi, oltre ad essere i monomeri che compongono gli aci-di nucleici, svolgono un ruolo essenziale negli scambi di energia all’interno delle cellule,fungono cie da carburante per le reazioni chimiche; l’ATP e il piu importante

47

Page 48: DNA COMPUTING - profs.sci.univr.itprofs.sci.univr.it/~manca/mnc/dna-computing-08.pdf · 6 Teoria dei Linguaggi Formali ... Questa ridondanza di informazione µe di fondamentale ...

L’energia utilizzabile e quella che puo essere liberata dall’idrolisi dei due legamianidridici che uniscono tra di loro i fosfati: in caso di rottura del primo legame,viene prodotto adenosindifosfato (ADP) e fosfato inorganico; in caso di rotturadel secondo, viene prodotto adenosinmonofosfato (AMP) e pirofosfato inorganico(Figura 57)

P P Z + H 2 O P P Z +

ATPa d e n o s i n t r i f o s f a t o

A c q u a ADPa d e n o s i n d i f o s f a t o F o s f a t o i n o r g n i c o

P P

+ H 2 O P P Z +

ATPa d e n o s i n t r i f o s f a t o

A c q u a AMPa d e n o s i n m o n o f o s f a t o

P i r i f os fa to i no rgn i co (ppi )

P P ZP P P

A

A d e n i n ab a s e a z o t a t a

A

A d e n i n ab a s e a z o t a t a

A

A d e n i n ab a s e a z o t a t a

A

A d e n i n ab a s e a z o t a t a

a ) r o t t u ra d i un f os fo ro

b ) ro t t u ra d i due f os fo r i

Figura 57: idrolisi ATP

3.6.4 Metodo chimico

Il metodo di Maxam e Gilbert, oggi praticamente abbandonato, impiega fosfororadioattivo 32P per marcare le molecole ad una estemita. In seguito, il DNA daanalizzare viene ripartito in quattro provette, una per nucleotide (A,T,C,G), e sot-toposto ad un trattamento chimico che modifica un tipo solo di base per provetta.Si aggiunge poi una sostanza chiamata piperidina che taglia la catena a livello del-la base modificata, e quindi si procede all’analisi dei frammenti generati medianteelettroforesi su gel.

3.6.5 Metodo enzimatico di Sanger

Il sequenziamento viene effettuato su un frammento di DNA clonato in un vettoredi clonaggio (vedi Paragrafo 3.5) oppure amplificato mediante PCR. Il DNA vienedapprima denaturato a singolo filamento, poi si fa avvenire l’appaiamento con unprimer in una zona adiacente a quella che si vuole sequenzaire.Vengono quindi allestite quattro diverse reazioni contenenti i seguenti materiali:

• DNA denaturato con primer appaiato

48

Page 49: DNA COMPUTING - profs.sci.univr.itprofs.sci.univr.it/~manca/mnc/dna-computing-08.pdf · 6 Teoria dei Linguaggi Formali ... Questa ridondanza di informazione µe di fondamentale ...

• enzima polimerasi

• desossinocleotidi trifosfati (dATP, dCTP,dGTP, dTTP), indicati come dNTP

• uno dei quattro didesossinucleotidi trifosfati (ddATP o ddCTP o ddGTP oDDTTP), uno diverso per ogni reazione

Un didesossinucleotide (ddNTP) e un nucleotide privato di un gruppo OH in po-sizione 3′ (Figura 58) La mancanza del gruppo OH in 3′ determina la terminazione

P

P

O H

5’

3 ’

P

B

Figura 58: ddNTP

della sintesi della catena di DNA. Il legame OH e infatti indispensabile per il legamecon il nucleotide successivo.Per questo il metodo di Sanger prende anche il nome di sequenziamento tramiteterminazione della catena o tramite didesossinucleotidi.

I desossi e i didesossinucleotidi sono presenti in ognuna delle quattro reazioniin un rapporto di concatenazione tale che statisticamente possa essere incorporatoo il nucleotide normale o il corrispondente didesossinucleotide. Ad esempio se sulfilamento template e presente una base T, allora sul filamento di nuova sintesi deveessere incorporato una base A. Ora, nella reazione in cui e presente il ddATP , l’enz-ima puo incorporare il dATP o il ddATP. Se avviene l’incorporazione con il ddATPla sintesi termina, se viene incorporato il dATP, la sintesi continua e l’enzima puonuovamente scegliere tra il dATP o il ddATP: si generano quindi frammenti di DNAdi lunghezza diversa, ciascuno dei quali termina nell’estremo 3′ con un ddNTP.Analogamente, in ciascuna delle reazioni in cui sono presenti il ddTP, il ddCTPoppure il ddGTP, si ottengono frammenti di lunghezza diversa ciascuno dei qualitermina in 3′, rispettivamente con un ddT, un ddC e un ddG.

In ciascuna provetta si utilizza un qualche meccanismo che ha l’effetto di tagliarele sequenza in un solo punto. Se indichiamo le provette come PT , PA, PC , PG, allorain PT i nuovi filamenti di sintesi saranno sempre tagliati dopo una base T, in PA

sempre dopo una base A, ecc. . .I frammenti cosı ottenuti in ogni reazione, possono essere separati mediante elet-troforesi; in ogni corsia vengono fatti correre i frammenti ottenuti in ciascuna dellequattro provette. La sequenza nucleotidica puo quindi essere dedotta dalla posizionedelle bande nelle corsie: se il frammento piu piccolo e localizzato nella corsia delddA allora il neofilamento inizia con A, il successivi piu corto si trova nella corsia G

49

Page 50: DNA COMPUTING - profs.sci.univr.itprofs.sci.univr.it/~manca/mnc/dna-computing-08.pdf · 6 Teoria dei Linguaggi Formali ... Questa ridondanza di informazione µe di fondamentale ...

e dunque la seconda base e una G e cosi via . . . In tal modo, risalendo lungo la las-tra attraverso le varie corsie, si puo determinare la sequenza del filamento di nuovasintesi e la lettura del filamento template originale si ottiene complementando lasequenza precedentemente ottenuta. (Figura 59)

5’

3 ’

T

C

GG

ATC

TGA

S e q u e n z ad a l e g g e r e

P r i m e r

C

G

G

A

T

C

G

A

A A

C

G

T

C

A

A

1 6 8

d d A T P +d N T P

d d G T P +d N T P

d d C T P +d N T P

d d T T P +d N T P

C

G

G

A

T

C

A

A

2 7

C

G

G

A

C

A A

C

G

T

C

A

A

3 4 9

G

A A

C

G

T

C

A

A

5 1 0

G

C

C

T

C

C

G

T

C

N u m e r o d in u c l e o t i d i

P r o d o t t o

R e a z i o n e

d d A d d G d d C d d T

1 0987654321

E le t t r o f o res i

A G C C T A G A C T

S e q u e n z a d e d o t t a d a l l a d i s t r u b u z i o n e d e l l e b a n d e

T C G G A T C T G A

S e q u e n z a f i l a m e n t o t e m p l a t e

Figura 59: Sequenziamento di Sanger

3.6.6 Pyrosequencing

E un metodo di sequenziamento basato sul principio di sequenziamento mediantesintesi. Il metodo si basa sulla possibilita di osservare l’attivita della polimeraseattraverso l’enzima della chemiluminescenza (quello delle lucciole). Si sintetizza ilcomplementare del template da leggere aggiungendo sequenzialmente un tipo dibase per volta, quando una base si ibridizza con il template viene emesso un seg-nale luminoso; sapendo per ogni passo quale base e stata aggiunta e tenendo tracciadei segnali si risale alla sequenza del template.

La base del principio risiede nel fatto che viene rilasciato del pirofosfato (ppi)

50

Page 51: DNA COMPUTING - profs.sci.univr.itprofs.sci.univr.it/~manca/mnc/dna-computing-08.pdf · 6 Teoria dei Linguaggi Formali ... Questa ridondanza di informazione µe di fondamentale ...

ogni volta che una base e aggiunta alla sintesi. Questo fenomeno e stato descrittogia negli anni ottanta, e successivamente si e cercato di mettere a punto un sequen-ziamento mediante sintesi utilizzando nucleotidi marcati, ma senza grandi successi.In seguito venne utilizzato l’enzima luciferasi, ma venivano continuamente osser-vati falsi segnali quando veniva aggiunta alla sintesi un dATP. Nel 1996 MustafaRonaghi ebbe l’intuizione di sostituire il dATP con l’adenosina alfa-trio-trifosfato(dATPαS) nella reazione della polimerasi. Un secondo miglioramento e stato quellodi inserire nella reazione l’enzima apirasi formando cosı un sistema a quattro enzimi;l’aggiunta di questo enzima permette di aggiungere nucleotidi in modo sequenzialeevitando lavaggi intermedi dopo ogni passo.

La procedura e costituita dai seguenti cinque passi.

1. Il DNA da analizzare viene amplificato tramite PCR, quindi viene denaturatoa singolo filamento, appaiato con un primer e incubato assieme agli enzimiDNA polimerase, ATP solforilasi, luciferasi e apirasi, e ai substrati adenosina5′ solfofosfato (APS) e luciferina (substrati rispettivamente per gli enzimiATP e luciferasi) vedi Figura 60.

S e q u e n z a d a a n a l i z z a r e

P r i m e r

E n z i m aD N A p o l i m e r a s i

E n z i m aA T P s o l f o r i l a s i

E n z i m aluc i f e ras i

E n z i m aa p i r a s i s u b s t r a t o

luc i f e r i na

s u b s t r a t oA P S

Figura 60: pyrosequencing step1

2. Il primo dei quattro deossinucleotidi trifosfato (dNTP) viene aggiunto allareazione. L’enzima DNA polimerasi catalizza il dNTP nel neofilamento diDNA se esso e complementare alla base presente nel filamento template.Ogni reazione e accompagnata dal rilascio di pirofosfato (ppi) in una quantitaproporzionale al numero di nucleotidi di quel tipo appaiati (Figura 61).

3. L’enzima ATP solforilasi, con l’aiuto del substrato APS, converte tutto ilppi prodotto al passo 1 in ATP. Questo ATP fornisce l’energia all’enzimaluciferasi che trasforma il substrato luciferina in ossidoluciferina liberandoluce visibile in quantita proporzionale all’ATP. La luce prodotta viene rilevata

51

Page 52: DNA COMPUTING - profs.sci.univr.itprofs.sci.univr.it/~manca/mnc/dna-computing-08.pdf · 6 Teoria dei Linguaggi Formali ... Questa ridondanza di informazione µe di fondamentale ...

( D N A ) n + d N T Pp o l i m e r a s i

( D N A ) n + 1 + p p i

Figura 61: pyrosequencing step2

da un dispositivo CCD ed analizzata da un programma che fornisce comeoutput un picco di segnale. Ogni segnale luminoso e proporzionale al numerodi nucleotidi appaiati (Figura 62)

A P S + p p iA T P s o l f o r i l a s i

A T P

luc i f e r i naL u c i f e r a s i

L u c e

t e m p o

s e g n a l e

Figura 62: pyrosequencing step3

4. L’enzima apirasi continuamente degrada i dNTP che non vengono appaiatie l’ATP rimanente. Quando la degradazione e completata viene aggiuntoun’altro dNTP (Figura 63)

d N T P d N D P + d N M P + f o s f a t o

A T P A D P + A M P + f o s f a t o

A p i r a s i

A p i r a s i

Figura 63: pyrosequencing step4

5. Si aggiungono gli altri dNTP ciclicamente fino alla deduzione completa dellasequenza. E da notare che al posto del dATP viene usato il dATPαS il qualeviene riconosciuto senza problemi dalla polimerasi come se fosse ATP, ma nondalla luciferasi; questo per evitare falsi segnali dovuti all’attivita dell’ATP conla luciferasi.

In Figura 64 viene mostrato un ciclo del procedimento; al ciclo successivo la polimerasiappaia tre dCTP liberando ppi in quantita tripla rispetto al ciclo precedente, quindiviene emesso un segnale luminoso che il ccd rileva con intensita tripla. La apirasi in-fine elimina l’unico dCTP non appaiato e il ciclo si ripete aggiungendo altri dNTP.Se vengono aggiunti dNTP non complementari al template non viene emesso alcunsegnale luminoso.

52

Page 53: DNA COMPUTING - profs.sci.univr.itprofs.sci.univr.it/~manca/mnc/dna-computing-08.pdf · 6 Teoria dei Linguaggi Formali ... Questa ridondanza di informazione µe di fondamentale ...

A C T T G G G

T G A1 2

A C T T G G G

T G Ap p i

3 A C T T G G G

T G A A

A T P so l fo r i l as i

p p i

A P S

A T P

4

L u c i f e r i n a

A T P L u c i f e r a s i

L U C E

t e m p o

s e g n a l e

A

A p i r a s i

5

d C T P

d C T Pd C T P

d C T P

d A T PaS d A T PaS

d A T PaSd A T PaS

d A T PaS

d A T PaS

d A T PaS

d A T PaS

d A T PaS

d A T PaSd A T PaS

Figura 64: pyrosequencing-esempio

4 Calcolare con il DNA

4.1 L’esperimento di Adleman (1994)

L’esperimento di Adleman risolve il problema del cammino Hamiltoniano: dato ungrafo totalmente connesso stabilire se esiste un cammino che, partendo da un ver-tice iniziale e arrivando ad un vertice finale, visiti tutti i nodi una e una sola volta.Tale problema si risolve in tempo polinomiale con una macchina non deterministicae pertanto appartiene alla classe dei problemi NP. E possibile risolverlo in mododeterministico utilizzando un algoritmo di forza bruta che genera tutti i possibilicicli Hamiltoniani e questo richiede un tempo esponenziale rispetto alla dimensionedell’input (con n nodi, i possibili cicli hamiltoniani sono n− 1! e per la formula diStirling n! ≈ O(nn)); in particolare si dimostra che il problema NP-completo.

L’idea di Adleman e quella di utilizzare un modello di calcolo in grado di gener-are facilmente lo spazio delle soluzioni del problema. Sfrutta quindi la naturalecapacita di calcolo parallelo e di codifica delle molecole di DNA.Adleman codifica i vertici del grafo con piccole sequenza di nucleotidi lunghe 20.Un arco aij che collega due vertici viene rappresentato considerando il reversing delcomplementare degli ultimi dieci nucleotidi del primo con i primi dieci del secondo.

53

Page 54: DNA COMPUTING - profs.sci.univr.itprofs.sci.univr.it/~manca/mnc/dna-computing-08.pdf · 6 Teoria dei Linguaggi Formali ... Questa ridondanza di informazione µe di fondamentale ...

In questo modo e possibile sfruttare il fenomeno dell’ibridizzazione e della ligasi performare un doppio filamento che rappresenta un cammino.Infatti mettendo in un unico pool ad esempio 1014 coppie delle codifiche dei verticie degli archi si formano tutti i possibili cammini per ibridizzazione (Figura 65). In

A 1 B 1 A 2 B 2 A 3 B 3

B 1 A 2 B 2 A 3 B 3

Figura 65: Ibridizzazione tra vertici e archi

questo modo lo spazio delle possibili soluzioni viene praticamente generato in untempo polinomiale a differenza della computazione convenzionale.I passi da seguire sono quindi i seguenti:

• Codifica dei nodi e degli archi

• Ibridizzazione

• Ligasi che concatena due nodi consecutivi

• Se tra i nodi c’e un cammino allora si forma la catena, ma ovviamente si sonoformati tutti i possibili cammini e non necessariamente solo quelli voluti (adesempio tra il nodo n1 e il nodo n7); quindi si isola il cammino desideratoamplificando con PCR(n1, n7)

• Il cammino ha una lunghezza di nucleotidi predefinita, ad esempio se il cam-mino comprende 7 nodi allora esso sara lungo 140 nucleotidi (20 × 7). Ifilamenti con questa lunghezza si trovano con l’elettroforesi.

• Per essere sicuri che ogni nodo e visitato una sola volta si esegue una selezioneper affinita dei filamenti in cui occorrono le codifiche di tutti i vertici:

For i = 1 to 7Fish(Ci)

end For

Per non perdere il segnale si deve ulteriormente amplificare

• Se nel pool finale e rimasto del materiale allora quello e il cammino cercato

4.1.1 Extract Model

L’Extract Model e il tipico modello computazionale del DNA Computing secondoAdleman. Questo modello si basa su due passi fondamentali; a) un pool di fila-menti di DNA codifica un insieme di soluzioni candidate del problema tipicamenteottenute per annealing e ligazione da un pool iniziale che codifica i dati; b) unaprocedura che estrae le soluzioni vere separandole da quelle false.L’operazione di ‘extract’ puo essere migliorata utilizzando altre operazioni comeseparate, merge, detect. L’operazione ‘separate’ prende in input un pool T e un

54

Page 55: DNA COMPUTING - profs.sci.univr.itprofs.sci.univr.it/~manca/mnc/dna-computing-08.pdf · 6 Teoria dei Linguaggi Formali ... Questa ridondanza di informazione µe di fondamentale ...

filamento S, e fornisce un pool T’ contenente filamenti in cui S compare come sot-tostringa e un T” contenente gli altri filamenti. Il ‘merge’ produce un unico poolcontenente i filamenti di due pool separati. L’operazione di ‘detect’ conferma lapresenza o l’assenza di DNA in un pool.In seguito alla realizzazione di queste operazioni biologiche, il costo computazionaledegli algoritmi di DNA computing puo essere identificato nel numero di ‘extract’effettuati.Quindi per valutare gli algoritmi secondo questo modello sono necessari solo dueparametri:

• la dimensione dello spazio delle soluzioni, che corrisponde alla quantita diDNA necessaria per codificare l’insieme delle soluzioni candidate

• il numero di operazioni di ‘extract’ necessarie per ottenere il pool finale deirisultati.

Questo significa che per migliorare tali algoritmi occorre concentrarsi su tre aspetti:la diminuzione della dimensione dello spazio delle soluzioni, migliorare l’implemen-tazione dell’ ‘extract’ o diminuire il numero di passi di ‘extract’ nella fase finale.

55

Page 56: DNA COMPUTING - profs.sci.univr.itprofs.sci.univr.it/~manca/mnc/dna-computing-08.pdf · 6 Teoria dei Linguaggi Formali ... Questa ridondanza di informazione µe di fondamentale ...

4.2 Algoritmi per 3-SAT

L’interesse per il problema SAT e dovuto al fatto che viene utilizzato come toolper risolvere numerosi problemi pratici. In particolare SAT puo essere ridotto intempo polinomiale al problema 3-SAT che e un prolema NP-completo in cui datauna espressione booleana in forma normale congiunta dove tutte le clausole hannotre letterali, chiede di stabilire se l’espressione e soddisfacibile.Una formulazione equivalente puo essere espressa in termini di risolvibilita di unsistema di equazioni booleane. Indichiamo con il termine letterali una variabilebooleana o la sua negazione e consideriamo un sistema di equazione basato sul-l’algebra booleana assumendo che in ogni equazione i membri di sinistra siano ladisgiunzione di tre letterali e il numero di destra sia 1. Una istanza appartiene a3-SAT se esiste un assegnamento che soddisfa tutte le equazioni del sistema.

4.2.1 Mix&Split Model

E un metodo piu efficiente per generare lo spazio delle soluzioni.Si mettono in un pool le tessere che codificano X1 e ¬X1, poi con la tecnica displit si divide il pool iniziale in due pool conservando i tipi, ovvero entrambi i nuovipool mantengono le informazioni di X1 e ¬X1. Poi si esegue un estensione dei duepool con la codifica di X2 da una patre e ¬X2 dall’altra, quindi si effettua un mixottenendo tutte e quattro lepossibilta di accoppiamento per la coppia X1 e X2. Siitera il procedimento n volte.

Sp l i t

M i x

E s t e n s i o n eE s t e n s i o n e

X 1X 1

X 1X 1

X 1

X 1

X 1X 1

X 2 X 2

X 2X 2

Figura 66: Mix & Split

In generale questa tecnica permette di generare per concatenazione tutte lepossibili combinazioni di stringhe A∗ a partire da un insieme finito di stringhe.In tempo lineare dunque si genera lo spazio di soluzioni 2n. Il problema e il costoin termini di denaro e tecnologia, e attualmente viene fatto solo in poche aziendeal mondo.

56

Page 57: DNA COMPUTING - profs.sci.univr.itprofs.sci.univr.it/~manca/mnc/dna-computing-08.pdf · 6 Teoria dei Linguaggi Formali ... Questa ridondanza di informazione µe di fondamentale ...

4.2.2 Algoritmo di Lipton

Un primo approccio e il metodo di Adleman, avvero quello di generare le possibilisoluzioni e quindi estrarre solo quello che interessa. Per tale scopo si prendono 2ntessere che codificano le variabili e le loro negate, e 4(n − 1) tessere per formare iconnettori tra le variabili (quattro per ciascuna coppia). Questi connettori rappre-sentano le possibili scelte; ad esempio per la coppia di variabili X1 e X2 posso averei connettori (scelte) mostrate in Figura 67. Quindi si mettono nel pool le tessere e

1 ) 2 )

3 ) 4 )

X 1 X 2 X 1 X 2

X 1 X 2X 2X 1

Figura 67: connettori

per ibridizzazione si formeranno tutti i possibili cammini, poi con varie operazionidi extract si separano le soluzioni vere da quelle false.Lo svantaggio e che al crescere del numero di variabili serve un numero spropositatodi materiale di DNA e diventa poco conveniente.

L’algoritmo di Lipton prevede di generare lo spazio delle soluzioni tramiteMix&Split e verificare l’esistenza di un cammino che rappresenta la soluzione,tramite la ripetizione dell’operazione biologica ‘extract’. L’extract puo essere real-izzata tramite il fish, che per essere efficiente e sicuro diviene un’operazione moltocostosa. Il fish viene realizzato con una sorta di tubo a strati dove ogni sezionecorrisponde ad un filtro che fa passare solo determinate molecole (nel nostro caso,solo le molecole che soddisfano la clausola).

Lipton risolve m equazioni booleane (m clausole) con 3m operazione di extract:tre operazioni per ogni clausola. Dopo aver generato lo spazio delle soluzioni, laselezione avviene iterando le operazioni di extract per ogni clausola, lavorando ognivolta sul risultato precedente. Ad ogni ciclo si selezionano i letterali che soddisfanol’equazione. Algoritmo:

Genera lo spazio delle soluzioni com mix&split e metti in Tfor j = 1 to m do

beginT1 := extract(T,L(1,j))T := T-T1T2 := extract(T,L(2,j))T := T-T2T3 := extract(T,L(3,j))T := merge(T1,T2)T := merge(T,T3)

endif T not null then prendi un clone e sequenzialoelse problema insolubile

57

Page 58: DNA COMPUTING - profs.sci.univr.itprofs.sci.univr.it/~manca/mnc/dna-computing-08.pdf · 6 Teoria dei Linguaggi Formali ... Questa ridondanza di informazione µe di fondamentale ...

Dove Ti sono i pool, L(1, j), L(2, j), L(2, j) sono i termini booleani dell’equazionej-esima e m e il numero di clausole.Ad esempio se la prima equazione e X1∨¬X2∨X3, i letterali corrispondenti saran-no L(1, 1), L(2, 1), , L(3, 1); alla prima iterazione del ciclo for verranno estratte lestringhe che codificano l’1 di X1, lo 0 di X2 r l’1 di X3

Note:Si puo notare che mentre la costruzione dello spazio delle soluzioni e la stessa pertutte le formule aventi lo stesso numero di variabili, l’algoritmo di selezione dellasoluzione cambia al variare della formula. I procedimenti biologici, inoltre, sonosolamente due; l’accoppiamento nella fase iniziale e l’estrazione per affinia nell’ese-cuzione dell’extract. L’operazione piu complicata e l’extract che viene eseguita 3mvolte (dove m e il numero di clausole), il tempo di computazione e quindi poli-nomiale in m. Un algoritmo deterministico con MdT per risolvere 3-SAT richiedeun tempo esponenziale nel numero delle variabili per generare lo spazio (2n) e untempo polinomiale nel numero delle clausole (m) per verificare se la soluzione eammissibile.

4.2.3 SAT come rete di contatto

SAT puo essere formulato come il problema della rete di contatto. Si associa adogni clausola C un grafo con due nodi, il nodo sorgente S(C) e il noto target T(C)e, per ogni letterale nella clausola, un arco che collega questi nodi. In Figura 68 emostrata una istanza di una rete di contatto

X

Y

Z

Y

Z

X

Y

X

Z

X

Y

Z

S ( C 1 )

S ( C 2 )

T ( C 1 ) T ( C 2 )

S ( C 3 )

T ( C 3 )

S ( C 4 )

T ( C 4 )

Figura 68: Istanza rete contatto

I successivi algoritmi risolvono SAT come istanza del problema della rete dicontatto.

58

Page 59: DNA COMPUTING - profs.sci.univr.itprofs.sci.univr.it/~manca/mnc/dna-computing-08.pdf · 6 Teoria dei Linguaggi Formali ... Questa ridondanza di informazione µe di fondamentale ...

4.2.4 Algoritmo di Jonoska

Si costruisce un pool contenente molte copie del grafo che rappresenta la rete dicontatto. Si esegue uno split separado il pool iniziale A in dure pool equivalenti Ae B. Si rimuovono in tutti i grafi di A gli archi etichettati con X1 e nei grafi diB gli archi etichettati con ¬X1. Quindi si effettua un merge tra il risultato di A eB, e si ripete la procedura (separazione, taglio degli archi, unificazione) per ognivariabile. La formula originale e soddisfatta se alla fine della procedura rimangonouno o piu grafi che connettono il nodo sorgente della prima clausola con il nodotarget dell’ultima clausola. E da notare che non si trova un’unica soluzione valida,ma bensi tutte, e nel pool finale saranno presenti anche tutti i grafi disconnessi.

P 0

E 1 N o t E 1

T a g l i o X 1 T a g l i o N o t X 1

M e r g e ( E 1 , N o t E 1 )

P 1

E 2 N o t E 2

T a g l i o X 2 T a g l i o N o t X 2

M e r g e ( E 2 , N o t E 2 )

P 2

Figura 69: Janoska

59

Page 60: DNA COMPUTING - profs.sci.univr.itprofs.sci.univr.it/~manca/mnc/dna-computing-08.pdf · 6 Teoria dei Linguaggi Formali ... Questa ridondanza di informazione µe di fondamentale ...

4.2.5 Algoritmo di Sakamoto

Si realizza un nuovo spazio di soluzioni composto da tessere di DNA che rappre-sentano i tre letterali di ciascuna clausola, codificando Xi e ¬Xi con nucleotidicomplementari (¬Xi = mirr(Xiovvero Xi

¬Xi)), in modo tale che se l’annealing pro-

duce un cammino non valido, si formi un hairpin per complementarieta (Figura 70).

X i

X i

Figura 70: hairpin

Si consideri un nodo sorgente S(C) e target T(C) per ogni clausola Ci e sicostruisce il grafo collegando un arco tra i due nodi per ogni letterale Lj che appar-tiene alla clausola Ci, si completa poi la rete di contatto aggiungendo un arco trail nodo target di una clausola e il sorgente del nodo successivo. Quindi si esegue untest per verificare l’esistenza di un percorso incoerente cioe se occorre un letteralesia nella sua forma positiva che negativa. Ogni letterale che risulta incoerente vienerimosso. Il problema originale e soddisfacibile se rimane qualche percorso coerentenella rete di contatto. In Figura 71 e raffigurata una rete di contatto relativa aduna istanza di SAT (3, 4)

S ( C 1 )

S ( C 2 )

T ( C 1 ) T ( C 2 )

S ( C 3 )

T ( C 3 )

S ( C 4 )

T ( C 4 )

L i t ( C 1 ) L i t ( C 2 ) L i t ( C 3 ) L i t ( C 4 )

Figura 71: istanza-sakamoto

Le tessere cosı composte vengono messe in provetta e per ibridizzazione si creatutto lo spazio delle soluzioni. Se in un cammino si ha la presenza di una variabilee la sua negata si ha la formazione di un hairpin tra le due tessere. Quindi tramiteselezione, in un unico passaggio, si possono eliminare tutte le soluzioni non valide.

Lo spazio delle soluzioni e 3m dove m e il numero delle clausole. Il tempo pereseguire l’extract non e piu una funzione di m o n, ma bensi risulta essere costante equesto porta ad un miglioramento dell’extract model, ma a discapito di un aumentodello spazio delle soluzioni.

60

Page 61: DNA COMPUTING - profs.sci.univr.itprofs.sci.univr.it/~manca/mnc/dna-computing-08.pdf · 6 Teoria dei Linguaggi Formali ... Questa ridondanza di informazione µe di fondamentale ...

4.2.6 Algoritmo di Manca

Si converte il problema 3-SAT in un BCP (Bipartite Covering Problem): dato uninsieme finito C (clausole) e n coppie di sotto insiemei di C: A1/B1 . . . An/Bn taliche Ai ∩Bi = ∅ per i = 1 . . . n, trovare n insiemi Y1 . . . Yn tali che Y1 ∪ . . .∪Yn = Ce Yi = Ai oppure Yi = Bi.

In sostana l’algoritmo codifia strinhe di clausole in un BCP. Ragionando in ter-mini di grafo di contatto, l’algoritmo costruisce stringhe di clausole cosi fatte:per ogni variabile si considerano due nodi S(X) e T(X) (sorgente e target) da con-nettere con archi etichettati con Cla(X) e Cla(¬X) corrispondenti all’insieme delleclausole in cui occorre il letterale X e a quello in cui occorre ¬X. Quindi si completail grafo collegando i target di una variabile con i sorgenti della variabile sccessiva. Lestringhe di clausole coincidono con tutti i possibili percorsi dal primo nodo all’ul-timo. Un stringa di clausole si dice completa se ogni clausola appartiene a qualcheinsieme che occorre come arco, qundi si eliminano tutti i percorsi incompleti e quelloche rimane e la soluzione dell’istanza del problema (Figura 72) Quindi gli insiemi

S ( X 1 ) S ( X 2 )T ( X 1 ) T ( X 2 ) S ( X 3 ) T ( X 3 )C l a ( X 1 )

S ( X 1 ) T ( X 1 )

C l a ( X 1 )

S ( X 2 ) T ( X 2 ) S ( X 3 ) T ( X 3 )

C l a ( X 2 ) C l a ( X 3 )

C l a ( X 2 ) C l a ( X 3 )

Figura 72: stringhe di clausole

Ai e Bi non sono alro che Cla(Xi) e Cla(¬Xi).

Di seguito viene mostrato un esempio su quattro equazioni. Si costruiscono cop-pie di insiemi Ai/Bi mettendo in Ai i pedici delle clausole in cui compare il letteralepositivo Xi e in Bi i pedici delle clausole in cui compare il letterale negativo ¬Xi.X1 + ¬X2 + X3 = C1X1 + X3 + X4 = C2X2 + ¬X4 + X3 = C3¬X1 + X2 + ¬X3 = C3

Xi = Ai se Xi oppure Bi se ¬Xi

A1|B1 = 1, 2|4A2|B2 = 3, 4|1A3|B3 = 1, 2, 3|4A4|B4 = 2|3

La soluzione e composta dagli insiemi che determinano una copertura completadelle clausole. Ad esempio la soluzione A1B2B3A4 che coprono rispettivamente leclausole 1 e 2 , 1, 4, 2 non e corretta poiche non copre la clausola 3. una soluzionecorretta potrebbe essere B1, B2, A3, B4.

Gli insiemi si codificano tramite due filamenti di DNA aventi due differenti parti

61

Page 62: DNA COMPUTING - profs.sci.univr.itprofs.sci.univr.it/~manca/mnc/dna-computing-08.pdf · 6 Teoria dei Linguaggi Formali ... Questa ridondanza di informazione µe di fondamentale ...

centrali che corrispondono ad Ai e Bi, ma aventi lo stesso sticky end sinistro Xi elo stesso sticky end destro ¬Xi+1. Quindi per ogni variabile Xi si hanno due dominicon stessi sticky end ma con differenti parti centrali che codificano rispettivamentele clausole che contengono Xi e le clausole che contengono ¬Xi. Per esempio idomini per A1 e B1 hanno la forma della Figura73

5’ 3 ’

3 ’ 5 ’

X 1

X 2C 1 C 2

5’ 3 ’

3 ’ 5 ’

X 1

X 2C 4

Figura 73: Codifica insiemi A1 e B1

Si mettono poi molte copie di Ai e Bi in un pool e dopo annealing e ligazione percomplementarieta degli sticky end, si ottengono stringhe di clausole (vedi Figura74)e le stringhe di DNA che codificano tutte le clausole rappresentano la soluzione.

X 1

X 2A 1 | B 1

X 2

X 3A 2 | B 2

Figura 74: Stringa di DNA

62

Page 63: DNA COMPUTING - profs.sci.univr.itprofs.sci.univr.it/~manca/mnc/dna-computing-08.pdf · 6 Teoria dei Linguaggi Formali ... Questa ridondanza di informazione µe di fondamentale ...

4.3 Considerazioni

Il DNA computing inizia nel 1994 con Leonard Adleman mostrando che le molecolebiologiche possono essere usate per scopi decisamente non biologici. Adleman hadimostrato come l’enorme parallelismo di miliardi di filamenti di DNA possono ri-solvere problemi considerati dificili (NP). Ricordiamo che utilizzando l’approcciodel DNA e stato decrittato il codice DES.

E interessante sottolineare alcuni aspetti che renderebbero i DNA computerpiu convenienti rispetto ai calclatori elettronici. A favore dei primi ci sarebbero ilnotevole calcolo parallelo, il basso consumo energetico e l’elevata densita di memo-rizzazione. Relativamente al primo aspetto, sebbene l’elevato parallelismo permetteteoricamente di eseguire tutti gli algoritmi in tempo polinomiale, sfortunatamentela loro applicabilita e per ora limitata a piccole istanze, infatti mentre gli algoritmihanno tempo di esecuzione lineare nelle dimensioni degli input, la massa di DNAnecessario per la codifica dei dati cresce esponenzialmente. Per esempio il DNA nec-essario per codificare tutti i cammini di un grafo con 200 vertici avrebbe una massapari a quella della terra. L’algoritmo di Adleman per il problema del commessoviaggiatore puo essere realizzato per un grafo avente al massimo 70 vertici, ma intal caso puo essere risolto in modo piu conveniente dai calcolatori al silicio.Attualmente altri argomenti a sfavore dei DNA computer sono la possibilita di er-rori dovuti sia alla esecuzione pratica delle operazioni biologiche che alla fase dicodifica, le quali se non sono sufficientemente accurate potrebbero permettere laformazione di filamenti iniziali non previsti, tuttavia le tecniche di biologia moleco-lare si evolvono rapidamente e tali errori possono essere notevolmente ridotti.

63

Page 64: DNA COMPUTING - profs.sci.univr.itprofs.sci.univr.it/~manca/mnc/dna-computing-08.pdf · 6 Teoria dei Linguaggi Formali ... Questa ridondanza di informazione µe di fondamentale ...

5 XPCR (Cross Pairing PCR)

Il modello fondamentale degli algoritmi di DNA e l’extract model di Adleman-Lipton e consiste di due passi fondamentali: la generazione dello spazio delle soluzioni,e l’estrazione dei filamenti che codificano le istanze positive del problema. Grazieall’estremo parallelismo del DNA, la complessita di questi due passi e polinomialerispetto alla dimensione dell’istanza. Tuttavia, mentre il primo passo puo essereulteriormente migliorato utilizzando la procedura di Mix-and-Split, l’estrazione ri-mane il punto critico del paradigma, ma grazie ad una specializzazione della PCRe possibile renderla piu efficiente.

La XPCR e una variante della PCR dove due molecole e due primers vengonoutilizzati in modo tale che un primer ibridizzi con un singolo filamento di una mleco-la e l’altro primer con un singolo filamento dell’altra molecola. Rispetto alla PCRinvece di avere un’unica doppia sringa target per l’amplificazione, se ne hanno duecon type < αργ > e type < γψβ >

La XPCR puo essere utilizzata principalmente in due tipi di applicazioni: l’es-trazione e la ricombinazione di DNA:

• Estrazione. Extraction(P, γ) = {ξ ∈ P | ∃δ, η t.c.ξ = δγη, δη ∈ A?}γ viene estratto da P. Il nuovo insieme, chiamiamolo Pγ , e una copia dellestringhe in P e non sono le stringhe di P estratte: Pγ * P ma Type(P ) =⊆Type(P )

• Ricombinazione.P = {α1, α2 . . . αn}, Q = {β1, β1 . . . βn} → L = {γ1 . . . γn t.c. γi ∈ {αi, βi}}

Passo principale della XPCR:E il passo chiave dell’algoritmo di estazione.Si mettono in un pool copie di molecole α . . . γ e γ . . . β, cioe che finiscono e inizianorispettivamente con la stessa sottostringa γ, e i due primers α e β. La PCR generala superstringa5 α . . . γ . . . β, e poi si amplifica.L’evento avviene nel seguente modo: i primers ibridizzano con i singoli filamen-ti delle due molecole liberando le rispettive molecole appaiate. A questo punto isingoli filamenti possono ibridizzare tramite le loro parti complementari γ e γ ela polimerasi utilizza come template proprio questi singoli filamenti e completa ladoppia stringa (Figura 75).Formalmente lo schema di esecuzione e il seguente:

< αϕγ >, < γψβ >, α, β ⇒αϕγ

λ , λ(αϕγ)c , γψβ

λ , λ(γψβ)c , α, β ⇒

αϕγ(γψβ)c , α

(αϕγ)c , γψββc ⇒

< αϕγψβ > ovvero il risultato dell’overlap concatenation tra αϕγ e γψβ

5γ superstringa := qualsiasi stringa che include la stringa γ

64

Page 65: DNA COMPUTING - profs.sci.univr.itprofs.sci.univr.it/~manca/mnc/dna-computing-08.pdf · 6 Teoria dei Linguaggi Formali ... Questa ridondanza di informazione µe di fondamentale ...

a g g b

g g ba

b

a

a g

gag b

g b

a

a

a

g b

g b

b

S e p a r a z i o n e

I b r i d i z z a z i o n e p e r P C R

Figura 75: XPCR

5.1 Estrazione con XPCR

Il problema dell’estrazione e il seguente: data una specifica sequenza γ e un pool dimolecole lunghe n aventi in comune lo stesso prefisso e suffisso, si vuole produrreun pool P ′ contenente solo filamenti che includono la sequenza γ.Si assume che le molecole abbiano la stessa lunghezza n, lo stesso prefix e suffix αe β e l’invarianza di γ ovvero:

α1δ1γδ2β,αδ3γδ4β →αδ1γδ4β,αδ3γδ2β,αδ1γδ2β,αδ3γδ4β

Passi:

• Split(P ) = P1, P2

• P1 := PCR(P1, α, γ)

• P2 := PCR(P2, γ, β)

• P = P1 ∪ P2; con gel elettroforesi si selezionano le sequenze corte. In questopasso rimangono solo stringhe del tipo α . . . γ e γ . . . β

• P := PCR(P, α, β)

• elettroforesi per selezionare la molecola piu lunga: P := separate(P, n+ |α|+|β|)

Esempio in Figura 76

65

Page 66: DNA COMPUTING - profs.sci.univr.itprofs.sci.univr.it/~manca/mnc/dna-computing-08.pdf · 6 Teoria dei Linguaggi Formali ... Questa ridondanza di informazione µe di fondamentale ...

a b

b

a

1 )

2 )

3 )

4 )

5 )

6 )

P

P 1

P 2

g

g

g

a bg

g

g

a

g

a

a g

g

a

g

a

A m p l i f i c a z i o n e e s p o n e n z i a l ed e l l a m o l e c o l a < a . . g >

A m p l i f i c a z i o n e e s p o n e n z i a l ed e l l a m o l e c o l a < g . . b >

a b

b

g

g

g

b

a

a bg

b

g

g

b

g

g b

b

b

S e l e z i o n e d i < a . . g > e < g . . b > c o n e l e t t r o f o r e s i

S e l e z i o n e d e l l e s t r i n g h e p i u ’ l u n g h e c o n e l e t t r o f o r e s i

a g

a g

g b

g b

a g

a

b

a g b

b

a g

g b

S u p e r s t r i n g a c h e c o n t i e n e g e c h e v e r r a ’a m p l i f i c a t a d a l l a p o l i m e r a s i

Figura 76: Extract con XPCR

5.1.1 Considerazioni

• Se ξ = αδ1γδ2β ∈ P ⇒ ξ ∈ XPCR(P, γ) = {ξ ∈ P t.c. ξ = αδγηβ, δη ∈ A?}ovvero le sequenze originali vengono mantenute nel pool finale

• Se ξ ∈ P, ξ 6= δγη∀δη ∈ A? ⇒ ξ /∈ XPCR(P, γ) ovvero le sequenze che noncontengono γ vengono eliminate dall’elettroforesi

• Se αδ1γδ2β ∈ P, αδ3γδ4β ∈ P, αδ1γδ4β /∈ P ⇒ αδ1γδ4β ∈ XPCR(P, γ)? →Si, infatti la XPCR prende cose di partenza e cose miste:XPCR(P, γ) ! extr(p, γ)

66

Page 67: DNA COMPUTING - profs.sci.univr.itprofs.sci.univr.it/~manca/mnc/dna-computing-08.pdf · 6 Teoria dei Linguaggi Formali ... Questa ridondanza di informazione µe di fondamentale ...

5.2 Ricombinazione con XPCR

• XPCR come generatore dello spazio delle soluzioni:Partendo da Ii(i = 1 . . . n), facendo 2(n − 1) cicli di XPCR si ottiene tuttolo spazio.Esempio.I1 = X1X2X3X4X5X6

I2 = Y1Y2Y3Y4Y5Y6

I3 = X1Y2X3Y4X5Y6

I4 = Y 1X2Y3X4Y5X6

sia P = {αIiβ, i = 1, 2, 3, 4} ovvero estendo con αprefix e βsuffix

For i=2 to n-1begin

XPCR(P,xi)XPCR(P,yi)

end

L’algoritmo prende P ′ =∏n

i=i(xi + yi) = {xi, yi}n e in tempo lineare si hauno spazio esponenziale

• XPCR per ricombinare strinhe:

Esempio.

In riferimento all’insieme I1 . . . I4 del punto precedente

– Vorrei ottenere: Y1Y2X3Y4Y5X6

XPCRy2(I2, I3) 7→ Y1Y2X3Y4X5Y6 = I5 ma e sottointeso anche X1Y2Y3Y4Y5Y6

XPCRy4(I5, I2) 7→ Y1Y2X3Y4Y5Y6 = I6

XPCRy5(I6, I4) 7→ Y1Y2X3Y4X5X6

– Vorrei ottenere: X1Y2X3X4X5X6

XPCRX3(I1, I3) 7→ X1Y2X3X4Y5X6

In sostanza per una qualsiasi sequenza presa a caso, esiste sempre una se-quenza di operazioni XPCR t.c. determina la sequenza voluta.

67

Page 68: DNA COMPUTING - profs.sci.univr.itprofs.sci.univr.it/~manca/mnc/dna-computing-08.pdf · 6 Teoria dei Linguaggi Formali ... Questa ridondanza di informazione µe di fondamentale ...

6 Teoria dei Linguaggi Formali (FLT)

6.1 introduzione

La teoria dei linguaggi formali ha un ruolo fondamentale nella teoria della com-putazione. Inoltre molti meccanismi biologici (DNA, sintesi proteica, metabolismi)e fisici hanno una natura discreta dell’informazione e la teoria dei linguaggi formalipermette di formulare modelli adeguati per modellare un gran numero di fenomeniin quanto una struttura discreta la si puo sempre rappresentare tramite un linguag-gio formale.La nozione stessa di problema, una volta codificato, ha uno stretto legame con ilinguaggi e tra tutti i problemi, quelli di decisione (la cui risposta e si o no), sonoquelli di maggior interesse. Fissato un modello di calcolo e possibile rappresentarei parametri del problema mediante stringhe di simboli propri del modello (codificadell’istanza). Dato quindi uno schema di codifica per un problema π e sia

∑l’al-

fabeto usato dallo schema, l’insieme∑? conterra le codifiche di tutte le istanze del

problema e non solo. Il sottoinsieme delle codifiche delle istanze positive caratter-izza in modo unico il problema:Lπ = {ω ∈ ∑? t.c.ω e codifica di una istanza positiva }Segue che il problema π puo essere visto come il problema di riconoscere il linguag-gio corrispondente Lπ

Riconoscere un linguaggio e uno dei quattro metodi per definire i linguaggi for-mali; due di tipo matematico e due di tipo algoritmico:

1. Metodi logici: descrizione tramite proprieta L = {α ∈ A? t.c. P (α)}2. Metodi algebrici: costruzione del linguaggio tramite operazioni insiemistiche

3. Metodi generativi:grammatiche che consistono in algoritmi che produconotutte e solo le parole del linguaggio

4. Metodi reconoscitivi: automi che per ogni α ∈ A? dicono se α appartiene omeno al linguaggio

Nota:Dato un algoritmo riconoscitivo se ne ottiene uno generativo (l’algoritmo che prendetutte le parole di A?) e genera tutte e sole quelle che riconosce appartenenti ad L.Il viceversa non e vero.

6.2 Stringhe e linguaggi

• un alfabeto e un insieme finito e non vuoto di oggetti detti simboli

• una stringa, detta parola, e una sequenza finita di simboli di A. L’insiemedelle possibili sequenze su A si indica con A?

• un linguaggio su A e un elemento di ℘(A?). Si indica con L un genericolinguaggio e con L la classe dei linguaggi

• operazioni:

– unione ∪

68

Page 69: DNA COMPUTING - profs.sci.univr.itprofs.sci.univr.it/~manca/mnc/dna-computing-08.pdf · 6 Teoria dei Linguaggi Formali ... Questa ridondanza di informazione µe di fondamentale ...

– intersezione ∩– differenza \– concatenazione •– iterazione ∗ ( o stella di kleene)

Descrivere un linguaggio attraverso la forma delle sue stringhe oppure tramite unagrammatico o un automa e un qualcosa di simile. Infatti una grammatica o unautoma si limitano a stabilire le regole che possono essere applicate a certe stringheiniziali per generare o riconoscere una stringa del linguaggio.

6.2.1 Gerarchia di Chomsky

• Il concetto di grammatica di Chomsky si basa su un sistema di riscrittura distringa: meccanismo di rimpiazzamento

• Si chiama grammatica di Chomsky una quaterna G = (A, T, S, R) t.c.

– A e l’alfabeto

– T ⊂ A e un insieme di simboli detti terminali

– S ∈ A\T e un simbolo di Start del linguaggio

– R ⊂ A? ×A? e l’insieme delle produzioni, delle regole

• Quando si scrive α →G β (riscrivi α con β) si indica (α, β ∈ R), R ⊂ A?×A?

• A partire dalla grammatica G si definisce una regola di riscrittura ad unpasso ⇒G:ω ⇒G ω

′sse ∃α, β, γ, δ ∈ A? t.c. (α →G β) ∧ (ω = γαγ) ∧ (ω

′= γβδ)

• A partire da una relazione ⇒G si definisce una riscrittura in piu passi ⇒G:ω ⇒?

G ω′sse ∃α1 . . . αn t.c. α1 = ω ∧ αn = ω

′ ∧ αi ⇒G αi+1∀i• Il linguaggio generato da una frammatica G e L(G):

L(G) = {α ∈ T ?|S ⇒?G α}

• A? si chiama universo linguistico dell’alfabeto A. A? e un monoide rispettoalla concatenazione che e associativa ed ha λ come elemento neutro (λ =stringa vuota)

• Per generare un linguaggio di una grammatica G, si parte dal simbolo S e sifa una riscrittura a piu passi rimpiazzando sottostringhe secondo le regole diR. Possono esserci piu regoole applicabili per uno steso passo; in questo casosi procede in modo non deterministico, scegliendo tra le regole applicabili etra i vari modi di applicarle. Ci si ferma quando non ci sono piu regole daapplicare. La parola ottenuta appartiene al linguaggio solo se appartiene aT ?.Esempio.L(G) = {anbncn}|n ∈ N linguaggio trisomatico di nteresse biologico poichemodella lo sviluppo di un embrione nelle sue tre parti (mesoderma,endoderma,ectoderma).E generato dalla seguente grammatica G.A = {a, b, c, B, S}; T = {a, b, c}; R = {S → abc, S → aSBc, cB → Bc, bB →bb}

69

Page 70: DNA COMPUTING - profs.sci.univr.itprofs.sci.univr.it/~manca/mnc/dna-computing-08.pdf · 6 Teoria dei Linguaggi Formali ... Questa ridondanza di informazione µe di fondamentale ...

6.2.2 Classi di Chomsky

Nel definire una grammatica ci sono quattro tipi di regole e una grammatica si dicedi tipo i(i = 0, 1, 2, 3) se tutte le sue produzioni sono di tipo i. Ogni regola di tipoi e necessariamente di tipo i− 1. Le classi di Chomsky corrispondono alle classi deilinguaggi L0, L1, L2, L3 generati dalle grammatiche di tipo 0, 1, 2, 3.

Tipi di regole:

• indichiamo con N i non terminali: A\T• indichiamo con le lettere minuscole i simboli terminali

• le regole hanno la forma α → β con α e β stringhe ∈ A?

Tipo 0.

α ∈ A?NA?

Cioe in α ci deve essere almeno un simbolo non terminale (non puo essereab → bb). Questa condizione impedisce a stringhe terminalizzate di contin-uare la derivazione.

Avere due tipi di simboli, terminali (T) e non teminali (N) e fondamentale.Sistemi grammaticali composti solo da simboi terminali sono sistemi poveri.Quando si genera qualcosa e ci sono simboli N, allora quella generazione con-tiene forme immature che possono ancora essere sviluppate. L’introduzione disimbili non terminali e la scelta di accettare solo simboli terminali, definisceimplicitamente una strategia. In generale infatti, il modello di Chomsky ebasato su una generazione non deterministica, si deriva a caso applicandoogni produzione possibile e se si prendono strade non finalizzate al risultatofinale non si terminalizza. La distinzione tra T e N serve quindi a selezionaretra cammini inutili (stringhe parassite) da cammini buoni.

Vedremo che {L(G)|G : 0} = RE

Tipo 1.

(0) ∧ (|α| 6 |β|)Le grammatiche con queste regole sono equivalenti alle grammatiche CS,sensibili al contesto, aventi le produzioni del tipo:αXβ → αγβ con X ∈ N e αγβ ∈ A? e γ 6= λ. La riscrittura aviene in modocontestuale solo se e presente il contesto α e β le quali fungono da stringhedi controllo.

70

Page 71: DNA COMPUTING - profs.sci.univr.itprofs.sci.univr.it/~manca/mnc/dna-computing-08.pdf · 6 Teoria dei Linguaggi Formali ... Questa ridondanza di informazione µe di fondamentale ...

Tipo 2.

(1) ∧ |α| = 1

Queste grammatice coincidono con le grammatiche CF libere dal contestole cui produzioni sono del tipo:X → γ dove X ∈ N, γ ∈ A?, γ 6= λSi vede subito che CF ⊆ CS poiche la grammatica CF e una grammaticaCD particolare in cui α e β sono vuote. Inoltre si dimostra che L2 (CF) puoesprimere simmetrie binarie e L1 (CS) puo esprimere simmetrie ternarie; percui il linguaggio trisomatico e discriminante tra L1 e L2: e generato da unaG : 1 e quindi ∈ L1 ma /∈ L2 perche quest’ultima ha simmetria binaria, qundiCF CS.

Tipo 3.

(2) ∧ (β ∈ T ∪ T ·N) e α ∈ N

Questa regola dice che a destra, ovvero in β c’e un sombolo N oppure unacoppia TN, ad esempio x → aY, x → b.

Esempio.

Riprendiamo la G per il linguaggio trisomatico e identifichiamo il tipo di grammaticaS → abc à Tipo 2S → aSBc à Tipo 2cB → Bc à Tipo 1bB → bb à Tipo 1

La G e di tipo 1¥

6.2.3 Inclusioni

Valgono le seguenti inclusioni strette:

L3 ⊂ L2 ⊂ L1 ⊂ L0↓ ↓ ↓ ↓

ASF PDA LBA MdT

La classificazione e importante perche indica i quattro livelli di difficolta nelgenerare i linguaggi e quindi nel calcolare. Gli strumenti di calcolo che generano ilinguaggi sono sempre piu complicati e vanno dagli ASF per L3 ai PDA (nastro apila) per L2, alle MdT con nastro limitato per L1 e alle MdT per L0

Le forme di interesse naturale si possono modellare con linguaggi compresi tratipo 1 e tipo 2, devono cioe avere una qualche forma di contestualita , ovvero quelloche avviene in una stringa dipende da quello che avviene in un’altro punto dellastringa stessa (si dice che ci sono dei collegamenti a distanza).

71

Page 72: DNA COMPUTING - profs.sci.univr.itprofs.sci.univr.it/~manca/mnc/dna-computing-08.pdf · 6 Teoria dei Linguaggi Formali ... Questa ridondanza di informazione µe di fondamentale ...

6.3 Risultati fondamentali

6.3.1 Teorema di universalita di Chomsky

{L(G)|G : 0} = RE ovvero L0 = RE

Ricordiamo che:

• Sia f una funzione da A? in A? (A alfabeto finito), si dice che f e calcolabilese esiste un sistema fisico che assunto uno stato che codifica un ingressodi f si evolve nel tempo raggiungendo uno stato finale solo se f e definitasull’ingresso; lo stato finale codifica il risultato di f.

• Un linguaggio L su un alfabeto A si dice ricorsivamente enumerabile o semide-cidibile o effettivamente generabile se L e il codominio di una funzione calco-labile. La classe di questi linguaggi si indica con RE.

• In genere si dice computazionalmente universale un qualsiasi formalismo chefornisca un metodo di costruzione per ogni linguaggio in RE.

Questo teorema e importante perche generare = calcolare e dicendo che G:0 = REdiciamo che con tale grammatica possiamo generare tutto cio che e possibile gener-are con le MdT, cioe che G:0 ha la stessa potenza delle MdT.Ad esempio posso calcolare una funzione f se riesco a costruire una macchina chegenera il suo grafico6. Quindi so calcolare f se so generare il suo grafico e viceversa.

La calcolabilita , previa opportuna codifica, e espressa in termini di linguaggiformali e invece di studiare la calcolabilita si studia la generabilita del linguaggio.Quindo le G:0 calcolano tutto cio che possono calcolare le MdT e le MdT calcolanoil calcolabile per la tesi di Church, e in conclusione, con le grammatiche e possibilesviluppare tutta la calcolabilita .

Dimostrazione di RE= L0

⊆) Sia L(M) ∈ RE con M = MdT si vuole costruire una grammatica GM di tipo0 che genera lo stesso linguaggio di M.Suddividiamo le regole di GM in regole di ingresso, di programma, di uscitae di allungamento.

• Regole di ingresso

S0 → $S1

S1 → S#S → Sx∀x ∈ AS → q0

6grafico(f) = {X, f(X)|X ∈ T ?} dove T = alfabeto di f

72

Page 73: DNA COMPUTING - profs.sci.univr.itprofs.sci.univr.it/~manca/mnc/dna-computing-08.pdf · 6 Teoria dei Linguaggi Formali ... Questa ridondanza di informazione µe di fondamentale ...

S0 e il simbolo iniziale e q0 un simbilo che rappresenta lo stato iniziale.I simboli $ e # indicano l’inizio e la fine del nastro. La terza pro-duzione simula la trascrizione di simboli dell’alfabeto sul nastro e pro-duce la stringa $q0α#; le produzioni applicate nell’ordine di esposizionecorrispondono a caricare la macchina M con ingresso α.

• Regole di programma

∀ regola qixyqjL (Spostamento a sinistra)qix → qjyzqj → qjz∀ regola qixyqjR (Spostamento a destra)qix → yqj

• Regole di allungamento

# → b#$ → $b

Questa regola ci permette di poter simulare un nastro illimitato, adesempio:$bbb . . . b# → $bbb . . . bb# e stata aggiunta una casella vuota

• Regole di uscita

qfx → xqf

qf# → q##′

Bq# → q##′

xq# → qf ′x

Idem per $ #′ → λ

$′ → λ

Queste regole spostano qf fino alla fine e simulano la sostituzione di Bcon #

′da destra a sinistra

Le regole cosı ottenute simulano la MdT e formano un sistema di rimpiazza-mento binario in cui tutte le stringhe non hanno piu di due simboli, chiamatoanche Forma Normale di Kuroda.Si ha dunque L(GM ) = {α|S0 →? α} e per costruzione si ha che L(Gm) =Output(M). Quindi per ∀M ∈ MdT esiste una grammatica GM tale cheL(M) = L(GM ) e tale che G e di tipo 0. ¥

⊇) Data una G:0 e possibile costruire un M ∈ MdT tale che L(G) = L(GM ). Siimplementano tante procedure quante sono le regole di G. Si inizia con S sulnastro e in modo non deterministico M si portera in uno stato qi e cercherasul nastro la codifica di αi →G βi e rimpiazzera αi con βi. ¥

73

Page 74: DNA COMPUTING - profs.sci.univr.itprofs.sci.univr.it/~manca/mnc/dna-computing-08.pdf · 6 Teoria dei Linguaggi Formali ... Questa ridondanza di informazione µe di fondamentale ...

Considerazioni.Le regole di uscita che cancellano i blank sono importanti, infatti l’uscita della MdTe composta dal contenuto del nastro senza i blank estremi. Senza questa conven-zione, la potenza della MdT si ridurrebbe notevolmente: la motivazione sara resanota con il teorema di Savich (vedi Paragrafo 6.3.4)

La MdT e cosı potente perche cancella; se non cancellasse sarebbe equivalentead un G:1. Il meccanismo di cancellare aumenta la potenza computazionale e deter-mina la differenza tra i linguaggi RE e CS. Dal punto di vista filosofico corrispondeal tornare indietro, al calcolo reversibile e il non cancellare rende il calcolo unidi-rezionale indebolendolo in potenza computazionale.

Nota:Come si riconosce se un formalismo e piu deole di un’altro?F1 < F2 Ã Formalismo F1 piu debole di F2.I due formalismi generano due linguaggi L(F1) e L(F2) e le rispettive classi dilinguaggi, ovvero tutti i linguaggi generati:L1 = {L|L = L(F1), F1 ∈ F1}L2 = {L|L = L(F2), F2 ∈ F2}Un formalismo e piu piccolo di un’altro se la classe dei linguaggi associati e stret-tamente inclusa nell’altro:L1 ( L2

6.3.2 Teorema di Kleene

Partendo da linguaggi finiti ed utilizzando le operazioni di concatenazione, unionee stella di Kleene si generano linguaggi regolari. Tali linguaggi vengono riconosciutidagli automi a stati finiti (ASF). Gli ASF partendo da uno stato iniziale q0, scan-discono la stringa in input secondo le regole di transizione e se alla fine si trovanoin uno stato finale allora l’automa accetta la stringa.ASF = (A,Q, q0, F, R)Il linguaggio generato e L(M) = {α|q0α →? q ∈ F}La differenza tra grammatica e automa sta rispettivamente nel generare e riconoscereuna parola α:g : S →? α : genera αASF : q0α →? q ∈ F : riconosce α

Il teorema dice che:

{L(M)|M ∈ ASF} = L3 = REG dove REG = CLOS(FIN,·, ?, +) Dove CLOSindica la chiusura algebrica rispetto alle operazioni indicate.

74

Page 75: DNA COMPUTING - profs.sci.univr.itprofs.sci.univr.it/~manca/mnc/dna-computing-08.pdf · 6 Teoria dei Linguaggi Formali ... Questa ridondanza di informazione µe di fondamentale ...

Dimostraione:

• {L(M)|M ∈ ASF} = L3:

Data una G:3 avente produzioni del tipo α →G β con α = x∧β = T ∪T ·N ,si puo costruire una M ∈ ASF che genera lo stesso linguaggio e viceversa:

S → aS1 q0a → q1

S1 → bS2 ⇔ q1b → q2

......

Si → b qib → qf

• L3 = REG:Dimostriamo che ogni L(M) con M ∈ ASF e ottenibile con unioni, concate-nazioni e stella di Kleene di linguaggi finiti su un alfabeto A. Il viceversa eovvio.Sia Q = {q1 . . . qn} gli stati di M con q1 stato iniziale e F = {qm . . . qn} glistati finali.Cosideriamo il linguaggio:Ln

i,j = {α ∈ A?|qiα → qi+1β → . . . qj ∈ F}ovvero il linguaggio fatto dalle parole α che vengono lette passando dagli statiqi . . . qj compresi n stati intermedi ∈ QPer esempio L3

i,j e il linguaggio formato da tutti i simboli che legge la macchi-na per passare dallo stato i allo stato j passando per tre stati intermedi.

Per induzione si osserva che:

base:L0

i,j ⊆ A, tale linguaggio e finito e quindi ∈ REG

infatti:L0

i,j = {α|qiα →? qj , Q = 0} = {a|qiα → qj , a ∈ A} = {a} ⊆ A, quindiessendo A finito, lo e anche L0

i,j e L0i,j e regolare.

induzione:Lk+1

i,j = Lki,k+1 · (Lk

k+1,k+1)? · Lk

k+1,j + Lki,j ∀i, j ∈ N

Infatti per andare da qi a qj avendo k+1 stati si puo passare o meno da qk+1

e i due tipi percorso sono compresi rispettivamente in:Lk

i,k+1 · (Lkk+1,k+1)

? · Lkk+1,j e in Lk

i,j

Per ipotesi induttiva Lki,j e regolare ed essendo Lk+1

i,j composto da unione econcatenazione e esso stesso regolare. Quindi:

L(M) =⋃

qk∈F Ln1,k = REG ⇒ L3 = REG

dove Q = {q1 . . . qn} con q1 iniziale e qk sono stati finali eL(M) = {Ln

1,m ∪ Ln1,m+1 ∪ . . . ∪ Ln

1,n} ¥

75

Page 76: DNA COMPUTING - profs.sci.univr.itprofs.sci.univr.it/~manca/mnc/dna-computing-08.pdf · 6 Teoria dei Linguaggi Formali ... Questa ridondanza di informazione µe di fondamentale ...

6.3.3 Teorema di Ginzburg

E un teorema di chiusura. Sia C una classe di Chomsky allora:

L ∈ C ⇒ L ∩R ∈ C ∀R ∈ REG

Ovvero i linguaggi regolari hanno la proprieta di conservare la gerarchia diChomsky, o meglio l’intersezione con i regolari non fa cambiare la classe di comp-lessita .

Dimostrazione.

Si dimostra per casi, L ∈ Li con i = 0, 1, 2, 3

• Se L ∈ RE banale RE ∩REG = RE poiche REG ⊂ RE

• Se L ∈ REG, basta considerare che REG e chiusa rispetto unione e comple-mento, quindi rispetto l’intersezione:L ∩R = L ∪R

• L ∈ CS (G:1)se L ∈ CS,R ∈ REG ⇒ L ∩R ∈ CS

∃M ∈ ASF tale che R = L(M) si vuole costruire una nuova grammaticacorrispondente al linguaggio intersezione.

Apicizzo le reogole di G: ax → yz ≡ a′x′ → y′z′ ottenendo G′

Aggiungo le seguenti regoleottenedo G′′:x′q0α → y′q0β ∀x′α′ → y′β′ ∈ G′

a′qib′ → ab

′qj ∀qia → qj ∈ M

bqi → b ∀qib → qf ∈ M, qf ∈ F

Questa grammatica G′′ partendo da Sq0 genera stringhe uguali a quelle cheavrebbe generato la G, con la differenza di avere stringhe apicizzate e indiciqi. Gli indici e gli apici spariscono solo se la stringa e riconosciuta anchedall’automa M (per costruzione). Tale G′′ e di tipo 1.Esempio:S′q0

→? a′1q0a′2 . . . a′n → a1a

′2qi

. . . a′n →? a1a2 . . . an Gli ultimi due passaggiavvengono sse la stringa e riconosciuta da M. ¥

• L ∈ CF (G:2)se L ∈ CF,R ∈ REG ⇒ L ∩R ∈ CF

Apicizzo G ottenendo G′,aggiungo le seguenti regole di tipo 2 ottenendo G′′:S → S′q0qf

∀qf ∈ F

x → yz ≡ xq1q2 → yq1q3zq3q2 ∀q1, q2, q3 ∈ Q

76

Page 77: DNA COMPUTING - profs.sci.univr.itprofs.sci.univr.it/~manca/mnc/dna-computing-08.pdf · 6 Teoria dei Linguaggi Formali ... Questa ridondanza di informazione µe di fondamentale ...

x → y ≡ xq1q2 → yq1q3 ∀q1, q2 ∈ Maq,q′ → a ∀a ∈ T, ∀q1, q

′ ∈ M

La seconda e la terza regolea mettono coppie di stati, la quarta dice che: aq,q′

diventa a se nell’automa nello stato q, leggendo a passa in q′.

Se la grammatica originale generava: S → x1, x2 . . . x11 e poi terminalizzain a1, a2 . . . a11, ora la nuova G′′, partenso da Sq0qf

genera stringhe del tipoaq0q1 bq1q2 . . . e tale stringha terminalizza solo se l’automa riconosce la parolasecondo la sequenza: aq0 → q1, bq1 → . . . qk.Esempio:S →? x1q1q3, x2q3q7, x3q7q9, . . . x11q15q17 con q17 ∈ F .Nella stringa ci sono tutti ipossibili stati da q0 a qf e i pedici sparisconoquando la stringa e riconosciuta da M.Quindi se l’automa riconosce la stringa, tale stringa viene riconosciuta anchedalla G′′ che e di tipo 2 per costruzione, quindi L(G′′) ∈ L2

6.3.4 Teorema di Savich

Questo teorema determina il passaggio dalla contestualita alla universalita .

∀L ∈ RE = L0, ∃L′ ∈ CS = L1 t.c L = {α|∃n : α e di tipo α#n ∈ L′} con #terminale.

La potenza di calcolo degli RE deriva dalla possibilita di cancellare, avere cioeun calcolo bidirezionale (avanti e indietro). Esempio.L = {α1, α2, . . .} ∈ RE → L′ = {α1##, α2###, . . .}ovvero allungando opportunamente le parole di L, tutto quello che si otteneva conuna MdT ora lo si puo fare con un LBA. Questo significa che se si ha la possi-bilita di cancellare caratteti, la complessita dell’automa che generara il linguaggioe maggiore. l’operazione di cancellare e un operazione difficile proprio perche fa au-mentere al complessita dell’automa. Capire bene cosa eliminare o dimenticare peruna gestione informativa efficiente e una operazione tutt’altro che banale.

Ricordiamo che:L1 = CS ( REC ( RE = L0

• REC ( RECostruisco un Lk che e RE ma non ricorsivo. Si numerino le grammatiche Gi

e le parole αi di A?, ora ∀i, j ∈ N × N si controlli se Gi nei primi j passi hatrovato αi; in caso positivo si aggiunga αi in Lk, altrimenti no.Questo e un metodo generativo per costruire Lk, quindi Lk ∈ RE, ma non siconosce un modo finito per stabilire se data una stringa ∈ Lk o /∈ Lk

• L1 ⊂ RECLa condizione |α| 6 |β| su α → β fa scendere nei decidibili ovvero che presaα ∈ L1 si puo stabilire se α ∈ L1 o se α /∈ L1.Preso G:1 e una stringa α tale che |α| = n, la generazione di α tramitele regole (che sono finite) contiene stringhe al piu lunghe n (S → α1 →

77

Page 78: DNA COMPUTING - profs.sci.univr.itprofs.sci.univr.it/~manca/mnc/dna-computing-08.pdf · 6 Teoria dei Linguaggi Formali ... Questa ridondanza di informazione µe di fondamentale ...

α2 . . . → α) e quindi controllando tutte le possibili generazioni posso dire seα puo essere generata.

• L1 ( RECSi numerino tutte le grammatiche Gi di L1 e le stringhe αi di A?.Sia LR = {αi|αi /∈ L(Gi)}, LR e ricorsivo poiche le grammatiche sono de-cidibili; ora se LR fosse generato da G:1 ovvero da CS avremmo due casi:

1. γ ∈ LR → γ ∈ {αi|alphai /∈ L(Gi)} → γ /∈ L(Gi) ovvero /∈ L(Gcs) ⇒γ /∈ LR Assurdo.

2. γ /∈ LR → γ /∈ {αi|alphai /∈ L(Gi)} → γ ∈ L(Gi) ovvero ∈ L(Gcs) ⇒γ ∈ LR Assurdo. ¥

Dimostrazione del teorema di Savich:

• Apicizzo le regole d G per trattare tutti i simboli come non terminali (G’)Nella forma contestuale si ha αXβ → αγβ, ma in G:0 la X si puo cancellare,mentre in G:1 (contestuale) non si puo perche deve essere |α| 6 |β| quindinella trasformazione da α a β al piu si aggiunge materiale e non si puo toglirenulla.In G:0 sarebbe dunque αXβ → αβ, cosı inserisco in G’ un simbolo ⊥ comesimbolo fittizio da mettere al posto della cancellazione.α′X ′β′ → α′⊥β′: significa che quando in G:0 cancello, in G:1 metto ⊥ alpostodel carattere nullo.

• S → $S′ :il $ funge da marcatore per l’inizio della stringa

• ⊥X ′ → X ′⊥ : sposta il ⊥ a destra

• $X ′ → X$ : sposta i simboli diversi da ⊥ a sinistra

• $⊥ → #⊥• #⊥ → ## : i ⊥ alla destra del $ diventano # che e simbolo terminale

Alla fine avro tutti i simboli diversi da ⊥ a sinistra de $ e il ⊥ alla destra del$. L’idea e spostare il ⊥ in fondo a destra e farlo diventare # e il teorema e cosıdimostrato, perche ho messo in fondo tutti i cancelletti che sono simboli terminali,e il tutto e stato fatto con regole di tipo 1

Esempio.$X ′Y ′⊥Z ′⊥$X ′X ′Z ′⊥⊥ regola 3XXZ$⊥⊥ regola 4XXZ#⊥⊥ regola 5XXZ### regola 6

Non permettendo l’operazione di cancellazione, l’automa genera la stringa volutacon l’aggiunta di altro materiale prodotto durante il calcolo. Ecco perche con leMdT e importante cancellare i blank generati in fase di elaborazione, altrimenti siprodurrebbero linguaggi CS declassificando la potenza di calcolo.

78

Page 79: DNA COMPUTING - profs.sci.univr.itprofs.sci.univr.it/~manca/mnc/dna-computing-08.pdf · 6 Teoria dei Linguaggi Formali ... Questa ridondanza di informazione µe di fondamentale ...

References

1 Chieffi, Dolfini, Malcovati, Pierantoni, Tenchini. Biologia e Genetica. EdiSESedizioni.

2 Vincenzo Manca. Frontiere della ricerca, DNA Computing il calcolatore in provet-ta. Mondo digitale n.4, p.19-32, Dicembre 2006.

3 Giuditta Franco, Cinzia Giagulli, Carlo Laudanna, Vincenzo Manca. DNA Ex-traction by Cross Pairing PCR. LNCS 3384, p.106-114, Springer-Verlag,2005.

4 Vincenzo Manca. On the logical and geometry of bilinear forms. FundamentaInformaticae, volume 64 p.261-273, IOS Press, 2005.

5 Vincenzo Manca, Giuditta Franco. Computing by polymerase chain reaction.Mathematical Biosciences n.211, p.282-298, 2008

6 Vincenzo Manca, Claudio Zandron. A clause string DNA algorithm for SAT.Lecture Notes in Computer Science, vol 2340, p.172-181, Springer-Verlag,2001.

7 Vincenzo Manca. Linguaggi, Grammatiche e Automi. Dipartimento di Informat-ica, Universita di Verona.

8 Appunti del corso di Modelli di calcolo non convenzionali. Dipartimento di In-formatica, Universita di Verona.

9 H.Papadimitriou. Computational Complexity. Addison Wesley Longman.

79