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í