engalçament de seqüències

Engalçament de seqüències

S’aplica en dos línies:

• Engalçament d’EST: trobar el gen que s’expressa en aquella celula a partir d’un segment del RNA corresponent.

• Seqüenciació del DNA: trobar la seqüència de bases de la cadena de DNA.

Seqüenciació del DNA

De quines tècniques es disposa:

• Trets: permet disparar sobre la seqüència i trencar-la en trossos.

• Hibridació: permet saber quins mots d’una longitud fixa es troben a la seqüencia.• Hibridació: permet saber quins mots d’una longitud fixa es troben a la seqüencia.

Hibridació

Imaginem que volem conèixer la seqüència xxxxxxxxxxxxx

i sabem que conté els següents mots de tres lletres:

AAC GAT TGCACG CGG GCC TTG GGA ATT

Com podem deduir la seqüència?

Hibridació

Crear un graf de coincidències sufix-prefix de dues bases

AAC GAT TGC

ACG CGG GCC TTG

GGA ATT

AACGGATTGCC

Seguir el camí determinat en el graf

Quin és el cost de trobar el camí?

Hibridació

Considerem un cas més real:

Buscar el camí Hamiltonià (NP-Complet)

Quin és el cost de tot el procés?

AAC CAA GAT TGC

ACG CGG GCC TTG

GGC GGA CCG ATT

Hibridació: mètode

Cost: 1. Trobar els mots AAC, CAA, ACG,... :

2. Trobar els enllaços AAC ACA,... :

Generar en el laboratori els 4L trossos i buscar-los

Si hi ha m mots de longitud L, doncs O(m2 L2 ) comparacions

3. Crear el graf i buscar el camí Hamiltonià

NP- Complet

Excursió: cost

Cost quadràtic: O(m2 )

Cost lineal: O(m)

Cost exponencial: O(2m )

m t = 1 mseg10m 10t = 10 mseg1000m 1000t = 1 seg

m t = 1mseg.10m 100t = 100 mseg.1000m 1000000t = 16 min

m t = 1 mseg.10m 210 t = 1 seg1000m 21000 t = 1030 t = 1018 anys

Hibridació: mètode

Cost: 1. Trobar els mots AAC,CAA,ACG,... :

2. Trobar els enllaços AAC ACA,... :

Generar en el laboratori els 4L trossos i buscar-los

Si hi ha m mots de longitud L, doncs O(m2 L2) comparacions

3. Crear el graf i buscar el camí hamiltonià

NP- Complet

Com podem evitar la NP-completesa?

Hibridació: dues reduccions

Buscar el camí Hamiltonià (NP-complet)

AAC GAT TGC

ACG CGG GCC TTG

GGC GGA CCG ATT

o bé buscar el camí Eulerià (lineal) AA

AC

GG

CG

GA

CC

GC

TG

TT

AT

Hibridació: camí Eulerià

Definir nodes desequilibrats: grau entrada=grau sortida(Nodes de començament o acabament: )

Definir nodes equilibrats: grau entrada=grau sortida(nodes de pas: )

Buscar el camí Eulerià d’un graf:

Hibridació: camí Eulerià

Algorisme: Crear un camí a l’atzar des d’un node inicial Afegir circuïts des de nodes equilibrats

Hibridació: camí Eulerià

Algorisme: Crear un camí a l’atzar des d’un node inicial Afegir circuïts des de nodes equilibrats

Hibridació: mètode

Cost: 1. Trobar els mots AAC,CAA,ACG,... :

2. Trobar els enllaços AAC ACA,... :

Generar en el laboratori els 4L trossos i buscar-los

Si hi ha m mots de longitud L, doncs O(m2 L2) comparacions

3. Crear el graf i buscar el camí hamiltonià

NP- Complet

Quin és el factor limitant?

Hibridació: problemes

AAC CAA GAT TGC

ACG CGG GCC TTG

GGA ATT

Trossos repetits

Quina és la probabilitat de que un tros es repeteixi?

CAACGGATTGCC

CAACGGACGGATTGCC

GAC

Hibridació

Model: seqüència aleatòria de longitud N amb distribució equiprobable (1/4),

Estimem la probabilitat de que un tros es repeteixi:

Donats 2 trossos, probabilitat de que siguin iguals: 4-L

Donats 3 trossos, probabilitat de que n’hi hagi dos d’iguals: (32)4-L

Donats m trossos, probabilitat de que n’hi hagi dos d’iguals: (m2)4-L

Si L=8 i volem una probabilitat del 1%, llavors m =32

Conclusió: la tècnica d’hibridació només serveix per conèixer seqüències molt curtes.

Excursió: hipòtesi d’equiprobabilitat

Cromosoma 21 té unes 34Mb distribuïdes:

A: 30% C: 20% G:20% T:20%

i si tenim en compte parells de bases, per exemple

AA: 10% AC: 5%

Fins a quin punt són equiprobables les seqüències?

Seqüenciació del DNA

De quines tècniques es disposa:

• Trets: permet disparar sobre la seqüència i trencar-la en trossos.

• Hibridació: permet saber quins mots d’una longitud fixa es troben a la seqüencia.

Trets

Imaginem que volem conèixer la seqüència xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

i la nostra tècnica ens permet :

• copiar-la

• partir-la a l’atzar en trossos de diferent llargada i sense saber-ne l’ordre

Què podem fer?

Trets: algorisme

Imaginem xxxxx|xxxxxxx|xxxxxxx|xxxx xxxxxxxx|xxxxxx|xxxxxx|xxxxxxx|xxxxxx|xxxxxx|xxxxxxx

L’algorisme serà:

1er. Comparar tots els trossos dos a dos per esbrinar com es superposen (eliminant inclusions).

2on. Construir el graf sufix-prefix

3er. Buscar el camí

Trets

La copiem tres cops xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

n’obtenim els trossos

accgt, aggt, acgatac, accttta, tttaac, gataca, accgtacc, ggt, acaggt,taacgat, accg, tacctt

Trets

Cal comparar els trossos per veure quins engalcen sufix-prefix

• Directament amb programació dinàmica (Cost quadràtic)

(tots contre tots i la majoria no engalceran)

• En dos passos:• Detectar els que engalcen

(Cost lineal amb l’Algorisme hash)

• Aplicar Prog. Dinàmica només als que engalcen

Excursió: algorisme de hash

Trets

accgtaccaccttta

tacctt

tttaac taacga

acgatac

accgaccgt

tacaggt

gataca

construïm el graf (cost quadràtic)

accgtacctttaacgatacaggt

i aconseguim la seqüència (cost exponencial)

Trets: problemes

Problemes

xxxxxxxxxxxxx

xxxxx

xxxxxx xxxxxx xxxxxxxx

accgaccgt

xxxxxxxxxxxxxx

• Repeticions consecutives• Repeticions curtes llunyanes• Falta de recobriment (problemes al seqüenciar)• Errors en els trossos (problemes al seqüenciar)

Trets: propietats del recobriment

Estudiem el recobriment:

Qüestions importants:

• Quina és la llargada mitja dels “contigs”?

• Quin es el nombre esperat de “contigs”?

• Quin és el percentatge de recobriment de la seqüència?

Trets: percentatge de recobriment

Grau de cobertura de la seqüència N d / L

Quin és el percentatge de recobriment de la seqüència?L

N d

Suposem que els segments estan uniformament distribuïts.

que una base de la seqüència sigui recoberta per k segments ve donada per la Dist. Binomial (N,d / L):

La probabilitat de

Prob{X=k}= (d/L)k (1-d/L)n-kNk

Excursió: distribució binomial

Distribució binomial B(n,p):

amb probabilitats p i 1-p de que hi caigui una bola.

Tenim dues urnes:

p 1-p

Quina és la probabilitat de que d’entre n boles en caiguin ka la primera urna?

Prob{X=k}= pk (1-p)n-knk

Excursió: distribució de Poisson

Quin és el límit de la distribució binomial quan n i p 0

conservant-se constant el producte np=

Distribució de Poisson P()

Prob{X=k}= e- (demostració a classe)k

k!

Llavors la probabilitat de que almenys caigui una bola és

Prob{X>0}= 1-Prob{X=0}= 1- e-

Trets: percentatge de recobriment

Si volem un recobriment del 99% cal que N d / L = 4.6

Distribució Binomial (N ,d / L)

Distribució de Poisson (N d / L)N d/L 0

Llavors el percentatge de recobriment ve donat per

la probabilitat de que al menys un tros cobreixi cada punt

1- e(N d / L)

Si volem un recobriment del 99.9% cal que N d / L = 6.9

Engalçament d’EST

Tenim milers de trosso de unes 500 bases de longitud,que pertanyen a diferents

L’algorisme serà:

1er. Comparar tots els trossos dos a dos per esbrinar quins estan relacionats(eliminant inclusions).

2on. Construir el graf sufix-prefix: (surten molts petits grafs)

3er. Buscar el camí