fundamentos de bioquímica experimentos con adn · fundamentos de bioquímica experimentos con adn...

1

Computación Computación bioinspiradabioinspiradaFundamentos de bioquímicaFundamentos de bioquímica

Experimentos con ADNExperimentos con ADN

José M. José M. SempereSempereDepartamento de Sistemas Informáticos y ComputaciónDepartamento de Sistemas Informáticos y Computación

Universidad Politécnica de ValenciaUniversidad Politécnica de Valencia

Fundamentos de bioquímicaFundamentos de bioquímica1.1. Estructura del ADN: los nucleótidosEstructura del ADN: los nucleótidos2.2. El ARN y las El ARN y las proteinasproteinas3.3. Del ADN a las Del ADN a las proteinasproteinas: enzimas, : enzimas, transcripcióntranscripción y traduccióny traducción4.4. Medidas sobre el ADN (los periféricos de lectura)Medidas sobre el ADN (los periféricos de lectura)5.5. Operaciones sobre el ADNOperaciones sobre el ADN

Bibliografía del temaBibliografía del tema

• DNA Computing. G. Păun, G. Rozenberg, A. Salomaa. Springer. 1998

• Computational Molecular Biology. An Introduction. P. Clote, R. Backofen.John Wiley & Sons, Ltd. 2000.

• Molecular Biology of the Cell. B. Alberts et al. Garland, NY. 1994.

2

Estructura del ADNEstructura del ADN

ADNADN : polímero formado por ácidos nucleicos llamados (desoxirribo)nucleótidos

Grupo fosfato + Azúcar(desoxirribosa)

+ Base nitrogenada

O P O

O

O

CH2

H

H

OH

O

C

C C

C

H

CH3

NH

N

CH

O

C

C

C O

1’1’2’2’3’3’4’4’

5’5’

grupo hidroxil

Bases nitrogenadas de los nucleótidosBases nitrogenadas de los nucleótidos

PurinasPurinas

PirimidinasPirimidinas

Adenina (A)Adenina (A)Guanina (G)Guanina (G)

Timina (T)Timina (T)

HC

NH

NH

H3C

C

C

C O

O

TT

Citosina (C)Citosina (C)

HC

N

NH

C

HC

C O

NH2

CC

C

N

N

C

C

CH

NH2

AA

N

HC

NH

HC

C

NH

N

C

C

C NH2

GG

N

NH

O

3

Enlaces en los nucleótidos Enlaces en los nucleótidos (I)(I)

Enlace Enlace fosfodiésterfosfodiéster (covalentes): (covalentes): formación de hebras

El grupo fosfato 5’ de un nucleótido se enlaza con el grupohidroxil 3’ del otro nucleótido. Forman un enlace fuerte

Direccionalidad

PPPP PP

AA CC GG

5’-3’

PPPP PP

AA CC GG

5’5’--ACGACG 3’3’--ACGACG

3’-5’

Enlaces no covalentes débilesEnlaces no covalentes débiles

• Enlaces de hidrógeno:formación de hebras dobles enlazando las bases.

• Estructura doble helicoidal

• Regla de Watson-Crick(hebras complementarias)

A A –– TTG G -- CC

hebra 1 hebra 2

dirección 5’-3’ dirección 3’-5’

ATTCGCGAT...

TAAGCGCTA...

Enlaces en los nucleótidos Enlaces en los nucleótidos (II)(II)

4

Estructura del ARNEstructura del ARN

ARNARN : polímero formado por ácidos nucleicos llamados (ribo)nucleótidos

Diferencias entre el ADN y el ARN

• Se sustituye el azúcar desoxirribosa por el ribosa• Se sustituye la timina (TT) por el uracilo (UU)• Se forma una única hebra que puede formar enlaces entre sus bases

Algunos tipos de ARN

• mRNA (mensajero)• tRNA (de transferencia)• rRNA (ribosómico)• snRNA (pequeño nuclear)• gRNA (de guía)

Estructura de las Estructura de las proteinasproteinas (I)(I)

proteinasproteinas : polímero formado por aminoácidos

N C

H

H OHR

O

Cgrupo amino

Hgrupo carboxil

cadena residual(diferencia cada uno de los 20 posibles aminoácidos)

carbono α

5

Estructura de las Estructura de las proteinasproteinas (II)(II)

Enlaces peptídicos entre los aminoácidos

N C

H

H R

O

C

H

N C

H R

O

C

H

Tipos de Tipos de proteinasproteinasglobulares (enzimas)*fibrilares (colágeno, elastina)de membrana

* facilitan o aceleran ciertas reacciones químicas

Del ADN a las Del ADN a las proteinasproteinas

ADNADN

ARN deARN detranscripcióntranscripción

mRNAmRNA

proteinaproteina

transcripción

traducción

splicing

TATA ...

núcleonúcleo

secuencia promotora(RNA polimerasa)

A C G TA C G T

U G C AU G C A

célulacélula

6

Medidas sobre el ADN Medidas sobre el ADN (los periféricos de lectura) (I)(los periféricos de lectura) (I)

longitud del ADNADN =

en hebras simples es el número de nucleótidos (mer)

en hebras dobles es el número de pares de bases (bp)

Técnica de medida de la longitud : electroforesis con gel

++--movimiento del ADNADN

Medidas sobre el ADN Medidas sobre el ADN (los periféricos de lectura) (II)(los periféricos de lectura) (II)

Localización de moléculas específicas de ADNADN

αα = ATTCGCC .... CGT= ATTCGCC .... CGT

αα = TAAGCGG .... GCA= TAAGCGG .... GCA

αααα αα -- αα+ =

αα αααααα

ββ ββ ββββ ββ ββ

αα αα -- αααα -- αα

7

Operaciones con ADNOperaciones con ADN

Separación y fusión de hebras de ADN

desnaturalización : Separación de dos hebras de ADNADN (por calentamiento)

renaturalización : Fusión de dos hebras de ADNADN (por enfriamiento)

hibridación : Fusión de dos hebras de distinto origen

ADNADN-ADN (radiado)ADN-ARNADN-ADN (de distintos organismos)


Alargamiento de hebras de ADN

Enzimas agentes : ADNADN polimerasasOtros componentes : nucleótidos y una hebra complementaria

ACG ...TGCGCCGCGCC ...

ACGCGGC ...TGCGCCGCGCC ...

5’-3’

Enzimas agentes : ADNADN transferasas terminalesOtros componentes : nucleótidos

3’-5’

ACGCGGCGCGGTGCGCCGCGCC

ACGCGGCGCGGAAAAAAAATGCGCCGCGCC

8


Acortamiento de hebras de ADN

Enzimas agentes : ADNADN nucleasas (exonucleasas)


ACGCGGCGCGGCGCCGCGCC

ACGCGGCGCCGCCGCGCC


CGCGGCGCGGCGCCGCGC

GCGGCGCCGCCGCG

Bal31

Bal31

Exonucleasa III

Exonucleasa III


Fragmentación de ADN

Enzimas agentes : ADNADN nucleasas (endonucleasas)


ACGAATTCCGGTGCTTAAGGCC

EcoRIS1

no específicas

ACGCTGCG

GGCGCGGCCGCGCC

restrictivas

ACGTGCTTAA

AATTCCGGGGCC

9


Enlaces de ADN

Enzimas agentes : ADN ADN ligasas


enlace de hidrógeno

ACGTGCTTAA

AATTCCGGGGCC

ACGTGCTTAA

AATTCCGGGGCC

OH

OH

P

P

ADNADN ligasas


Modificación de los nucleótidos del ADN

Enzimas agentes : ADN ADN metilasas

Multiplicación del ADN (Reacción en Cadena de la Polimerasa, RCP)

1 desnaturalización


ACGAATTCCGG

TGCTTAAGGCC

ACGAATTCCGGGCC

ACGTGCTTAAGGCC



2 “priming” 3 extensión

10

Operaciones con ADNOperaciones con ADN: : Leyendo la secuencia de nucleótidos

Técnica de secuenciación (método de Sanger)Polimerasa + nucleótidos análogos

cadena objetivo α

ββ

GCTA tubos con nucleótidos análogos

AC

G

T

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



Experimentos con ADNExperimentos con ADN1.1. El experimento de El experimento de AdlemanAdleman: Resolviendo el “: Resolviendo el “Camino Camino HamiltonianoHamiltoniano””2.2. LiptonLipton: Resolviendo SAT: Resolviendo SAT3.3. RoweissRoweiss y otros: Resolviendo la “y otros: Resolviendo la “Cobertura MínimaCobertura Mínima””4.4. Garzón y otros: Implementando autómatas finitosGarzón y otros: Implementando autómatas finitos

Bibliografía del temaBibliografía del tema

• DNA Computing. G. Păun, G. Rozenberg, A. Salomaa. Springer. 1998• Proceedings of the DIMACS Workshop on DNA Based Computers II. Landweber,

Baum, (Eds.). AMS. 1999• Proceedings of the Second International Workshop on Implementing Automata.

Wood, Yu (Eds.). Springer. 1998.

11

El experimento de El experimento de AdlemanAdleman (I)(I)(Adleman, 1994)

El Problema del Camino Hamiltoniano (CH)

3

4

0

1

2 5

6

vin = 0vout = 6

Solución : 0-1-2-3-4-5-6

GTeorema: CH es NP-completo

El experimento de El experimento de AdlemanAdleman (II)(II)

Algoritmo no determinista para el Problema del Camino Hamiltoniano

Input : G, vin y vout

Paso 1: Generar aleatoriamente caminos en G

Paso 2: Eliminar los caminos que no comienzan por vin o no terminan por vout

Paso 3: Eliminar los caminos que no tienen exactamente n vértices

Paso 4: Para cada vértice v, rechazar los caminos que no incluyan a v

Output : SI (si queda algún camino) NO (en caso contrario)

12

El experimento de El experimento de AdlemanAdleman (III)(III)

Codificación mediante ADN de los datos de entrada

• Cada vértice se codifica con una hebra de 20 nucleótidos (si)

s2 = TATCGGATCGGTATATCCGAs3 = GCTATTCGAGCTTAAAGCTA

• Cada arista se codifica a partir de los 10 últimos nucleótidos del vértice de origeny los 10 primeros nucleótidos del vértice de destino. Posteriormente se le aplica unhomomorfismo complementario h(A)=T, h(T)=A, h(C)=G y h(G)=C

e23 = CATATAGGCTCGATAAGCTC

El experimento de El experimento de AdlemanAdleman (IV)(IV)

Posibles hebras de ADN formadas en un tubo

s1 s3 s4 s1 s2 s3

e13 e34 e41 e12 e23 e32

s0 s3 s2 s1

e03 e32 e21 s0 s6

e06

13

El experimento de El experimento de AdlemanAdleman (V)(V)

Formalización del experimento de Adleman

Un tubo es un multiconjunto de cadenas sobre el alfabeto { A,T,C,G }

Operaciones sobre tubos

merge(N1,N2) Forma la unión de los tubos N1 y N2

amplify(N) Produce dos copias del tubo N

detect(N) Detecta si en el tubo N hay al menos una hebra de ADN (booleano)

separate(N,w) Produce dos tubos +(N,w) y –(N,w) con las hebras de ADNque contienen w como subcadena y con las que no la contienen

Length-separate(N,n) Produce un tubo (N,≤n) con todas las hebras de ADNcon longitud menor o igual que n

Position-separate(N,w) Produce un tubo B(N,w) ó E(N,w) con todas las hebrasde ADN que empiezan o terminan por w

El experimento de El experimento de AdlemanAdleman (VI)(VI)

El algoritmo de resolución con operaciones sobre ADN

(1) input(N)(2) N ← B(N,s0)(3) N ← E(N,s6)(4) N ← (N, ≤ 140)(5) para i=1 hasta 5 hacer

N ← +(N,si)(6) detect(N)

14

Resolviendo el problema Resolviendo el problema SATSAT (I)(I)(Lipton, 1995)

El Problema SAT

X = { x1, x2, … , xn } (variables)C = {c1, c2, … , cm} (cláusulas)

ci = xi1 ∨ xi2 ∨ … ∨ xip xij ∈X

¿ Existe alguna asignación a las variables xi que haga ciertala fórmula c1 ∧ c2 ∧ … ∧ cm ?

Teorema: SAT es NP-completo

Resolviendo el problema Resolviendo el problema SATSAT (II)(II)(Lipton, 1995)

Grafo asociado a las variables del Problema SAT

X = { x1, x2, … , xn }

vin vout

x0

1

x1

1

x0

2

x1

2

x0

3

x1

3

xn

0

1−

xn

1

1−

xn

0

xn

1

v1 v2 vn-1

Cada camino desde vin hasta vout representa una posible combinación de valores True (1) o False (0) de todas las variables.

Los caminos del anterior grafo se pueden obtener mediante una estrategiasimilar a la que Adleman utilizó en el problema del Camino Hamiltoniano.

15

Resolviendo el problema Resolviendo el problema SATSAT (III)(III)(Lipton, 1995)

Algoritmo de resolución del Problema SAT

Partimos de un tubo N0 que contiene todos los caminos del grafo asociado a lasvariables.El tubo N0 sirve para diferentes instancias del SAT con cláusulas distintas yconjuntos de variables idénticos.

Ejemplo de resolución: (x1 ∨ x2 ) ∧ (¬x1 ∨ ¬x2)

S(N,i,j) denota +(N, )x j

i

S-(N,i,j) denota -(N, )x j

i

(1) input(N0)(2) N1 = S(N0,1,1)(3) N’1 = S-(N0,1,1)(4) N2 = S(N’1,2,1)(5) merge(N1,N2) = N3(6) N4 = S(N3,1,0)(7) N’4 = S-(N3,1,0)(8) N5= S(N’4,2,0)(9) merge(N4,N5)(10) detect(N6)

La resolución general se produce enO(m) pasos de separación + merge

Resolviendo la Cobertura Mínima Resolviendo la Cobertura Mínima (I)(I)(Roweiss y otros, 1996)

El problema de la Cobertura Mínima

S = { 1, 2, …, p}C = {C1, C2, …, Cq} Ci ⊆ S (ci

j denota el elemento j-ésimo de Ci )

Encuentre el subconjunto mínimo I de {1,2, …, q} tal que SCIi

i =∈U

Teorema: El problema de la Cobertura Mínima esun problema NPO-completo

16

Resolviendo la Cobertura Mínima Resolviendo la Cobertura Mínima (II)(II)(Roweiss y otros, 1996)

Memorias de stickers

GAGAG TTTTT AAAAA GGGGG

n bases (k subhebras de m bases n ≥ k·m)

subhebra 1 subhebra k

GAGAG TTTTT AAAAA

CTCTC

1 0 1

GAGAG TTTTT AAAAA

AAAAA

0 1 0

GAGAG TTTTT AAAAA

TTTTT

0 0 1

Configuraciones de una memoria de 3 bits (complejos de memoria)

Operaciones con memorias de stickers

merge(N1,N2): produce la combinación de los tubos N1 y N2 en uno nuevo

separate +(N,i) selecciona las memorias con el bit i con valor 1–(N,i) selecciona las memorias con el bit i con valor 0

set(N,i) produce un nuevo tubo asignando el valor 1 al bit i-ésimo de todas las memorias

clear(N,i) produce un nuevo tubo asignando el valor 0 al bit i-ésimo de todas las memorias

Resolviendo la Cobertura Mínima Resolviendo la Cobertura Mínima (III)(III)(Roweiss y otros, 1996)

17

Librerías de memorias de stickers (k,l)

Resolviendo la Cobertura Mínima Resolviendo la Cobertura Mínima (IV)(IV)(Roweiss y otros, 1996)

Una librería (k,l) contiene memorías de stickers con la siguienteestructura

l bits

k bits

0k-lconfiguración de l bits

2l complejos de memoria distintos

Librería de memorias de stickers (k,l)

Algoritmo de resolución

Resolviendo la Cobertura Mínima Resolviendo la Cobertura Mínima (V)(V)(Roweiss y otros, 1996)

S = { 1, 2, …, p} C = {C1, C2, …, Cq} Ci ⊆ S

Se parte del tubo N0 que contiene una librería (p+q,q)q

p + q(1) Para i=1 hasta q

separate +(N0,i) y –(N0,i)Para j=1 hasta Card(Ci)

set(+(N0,i), q + cij )

N0 ← merge(+(N0,i), –(N0,i))(2) Para i= q+1 hasta q+p

N0 ← +(N0,i)(3) Para i=0 hasta q-1

Para j=i hasta 0separate +(Nj,i+1) y –(Nj,i+1)Nj+1 ← merge(+(Nj,i+1), Nj+1)Nj ← –(Nj,i+1)

(4) Leer N1si N1 es vacío leer N2

si N2 es vacío leer N3…

Actualiza los complejos de memoria poniendo a 1 las componentes de S que quedan cubiertas por los subconjuntos Ci

Selecciona los complejos de memoria que cubrentodas las componentes de S

Introduce en el tubo Ni aquellos complejos dememoria con exactamente i componentes Cjcon valor 1

Selecciona los complejos de memoria con un mínimo número de componentes Ci con valor 1

18

Implementando autómatas finitos Implementando autómatas finitos (I)(I)(Garzon y otros, 1997)

A = (Q, Σ, δ, q0, F)

Σ = { 0, 1 }

δ: Q × Σ → Q

0 1 2

0

0

0

1

1

1

Estrategias de implementación

(a) Basadas en la recombinación del ADN (ligazón)(b) Basadas en moléculas reusables

Implementando autómatas finitos Implementando autómatas finitos (II)(II)(Garzon y otros, 1997)

A = (Q, Σ, δ, q0, F)

Codificación del estado inicial (molécula inicial)

0 1 2

0

0

0

1

1

1

Codificación de los estadosEstado 0 ttatEstado 1 gctgEstado 2 ctca

GGGGAGATCttatCTTAACCCCTCTAG

Implementación basada en la recombinación del ADN (ligazón)

Codificación de los símbolos 0, 1

adaptadores

19


A = (Q, Σ, δ, q0, F)

0 1 2

0

0

0

1

1

1


Codificación de las transiciones (adaptadores) : {00, 10, 20, 01, 11, 21}

aataGAATTGGGCCCCTC

TCttA

atCTTAAGAG cTAGAATTCTC

CCCGGGGAG00

Estado 0 ttatEstado 1 gctgEstado 2 ctca

aataGAATTGGGCCCCGT

GCgcT

tgCTTAAGAG cACGAATTCTC

CCCGGGGCA

cgacGAATTGGGCCCCTC

ACctC

caCTTAAGAG cGTGAATTCTC

CCCGGGGAG

cgacGAATTGGGCCCCGT

TCttA

atCTTAAGAG cTAGAATTCTC

CCCGGGGCA

gagtGAATTGGGCCCCTC

GCgcT


CCCGGGGAG

gagtGAATTGGGCCCCGT

ACctC

caCTTAAGAG cGTGAATTCTC

CCCGGGGCA

01

10

11

20

21


A = (Q, Σ, δ, q0, F)

0 1 2

0

0

0

1

1

1


Funcionamiento de la máquina

Estado 0 ttatEstado 1 gctgEstado 2 ctca


+molécula inicial transición 01

ligasa


SmaI, EcoRIGGGGCATGCgctgCTTAACCCCGTACG

aataGAATTGGGCCCCGT

GCgcT


CCCGGGGCA

aataGAATTGGGCCCCGT

GCgcT


CCCGGGGCA

fundamentos de bioquímica experimentos con adn · fundamentos de bioquímica experimentos con adn...

Documents