búsqueda de patrones

InformáticabiomédicaPatrones

RodrigoSantamaría

Patrones

Unpocodebiología

• Unpocodebiología• K-mers• DNAbox• Motivos

• Unpocodeestadística• Mutaciones• Combinaciones• Permutaciones

• Cazandomotivosesquivos

K-mer

• Esunasecuenciadeknucleótidos– Conceptomuyutilizadoenensamblado,alineamientoybúsquedadesecuencias

DNAbox• LaproteínaDnaA eselfactordeiniciodelareplicaciónenbacterias

• DnaA seuneadeterminadasregionesenoriC*,conocidascomoDnaA boxes.– Porejemplo,enE.coli hay4DnaA boxesquecontienenel9-mer5’-TTATCCACA-3’**

*oriC es una región abstracta,deuna longitud arbitraria,generalmente entorno alas 500basesEnelEjercicio 4delaSesión 1calculamos elsesgo mínimo deEcoli, que usaremos para eloriC deesta bacteria

http://www.ebi.ac.uk/pdb

e/entry/pd

b/1j1v

**https://en.wikipedia.org/wiki/Prokaryotic_DNA_replication

Contando k-mers

• Es sencillo,simplemente implica recorrer unasecuencia ycapturar cada subsecuencia delongitud kACTGGGTCGTAACGTGCAGTTTAAACGC

k=7

ACTGGGT +1CTGGGTC +1TGGGTCG +1...

¿Cuál es lacomplejidad delmétodo?

Ejercicio1

• ImplementarlafuncióncountKmers:– entrada:• seq (cadenaoriginal)• k (tamañodelk-mero)• n (nºdeocurrencias)

– salida:diccionarioquetengacomoclaveslosk-merosycomovaloreselnúmerodevecesqueapareceenseq.Sóloapareceráneneldiccionariolosk-merosqueaparezcann omásveces

6

Ejercicio1• Ejemplo– entrada:

• ACGTTGCATGTCGCATGATGCATGAGAGCT• 4• 2

– salida:• {'GCAT': 3, 'ATGA': 2, 'TGCA': 2, 'CATG': 3}

• Prueba– OriC deVibriocholerae

• http://vis.usal.es/rodrigo/documentos/bioinfo/avanzada/datos/oric.txt

– 9– 3

7

Motivos

• Losmotivossonk-merosqueaparecenrecurrentementeenalgúnaspectobiológico

UsandocountKmers,¿qué9-merosfrecuentespodemosencontrarenlaregiónoriC deVibrio cholerae?

¡Eureka!Hayunpatrónbastanteclaro:lassecuenciasCTTGATCAT ysucomplementariaATGATCAAG aparecen3vecescadauna.

Peroojo,nopodemos saltarrápidamentealaconclusióndequehayunmotivoparatodoslosgenomasbacterianosquecaractericeorígenesdereplicación.Einclusopodría serqueelpatrónencontradoparaVcholerae seasólodebidoalazarynotengasignificanciaestadística.

Deberemoscomprobarestasdoscuestiones8

Motivos

• PodemosusarcountKmers parabuscar9-mersqueaparezcan3omásveceseneloriC deThermotoga petrophila– ¿SonlosmismosqueenVCholerae?

Thermotoga petrophila esunabacteriaqueresistetemperaturasmuyaltas,graciasasucubierta(la‘togatérmica’)

Descubiertaenundepósito depetróleo,a70oC(’amigadelpetróleo’)

9

K-merosesquivos• SiusamoscountKmers eneloriC deEcoli,noencontramostodas

lasocurrenciasdelmotivoesperado(TTATCCACA)• Elcódigogenéticoesdegenerado

– Existenmutacionesquepuedenvariarligeramenteelpatróndeunmotivo

TTATCCACATTATCGACATGATCCATA

10

¿Hastaquépuntounpatrónesigualperodegenerado,odirectamentedistinto?¿Quécriteriosestadísticosobiológicosmarcamosparaestasdistinciones?¿Cómoafectaelcódigodegeneradoalabúsquedacomputacional(diseño dealgoritmos, rendimiento,etc.)?Todasestassonpreguntas importantesqueiremosdiscutiendo

Ejercicio2• ImplementarlafunciónfindMotif:– entrada:

• motif (motivodeADNabuscar)• seq (cadenadeADNdondebuscar)• d (nºdemutacionespermitidasrespectoamotif)

– salida:undiccionario{pos,motif} dondesealmacenaelpatrónencontradoysuposicióndeinicio

• Ejemplo:– seq:CGCCCGAATCCAGAACGCATTCCCCTGGCCTCCATTCTGGAACGGTACGGACGTCAATCAAAT– motif:ATTCTGGA– d:3– salida:{6: 'AATCCAGA', 7: 'ATCCAGAA', 33: 'ATTCTGGA’}

11

Ejercicio2

• Prueba:– seq:oriC deEcoli• Paracalcularla,tomamosunaseccióndelgenomadeEcoli de500bases,comenzandoporlaprimeraposiciónobtenidaconlafunciónminSkew (ejercicio4delasesión1)

– motif:DNAboxconocidopormétodosexperimentales• TTATCCACA

– d:1

12

Reflexión

• Conelejercicio2,¿seencuentranlas4ocurrenciasdeTTATCCACA eneloriC deEcoli?– ¡No!

• ¿Porqué,sitenemosencuentalosmutantes?– Porquesóloconsideramoslosk-mers mutantesqueyaseencuentrenenlasecuencia

– Necesitamospensarentérminosdetodoslosposiblesk-mers• Problemasdecombinatoria(estadística)• Problemasderendimiento(computación)

13

Secuenciaconsenso

• Secuenciamásfrecuentedeentrevarias

ATTCTGGAAATCTCGAACACTGGG--------A*TCTGGA31233232

14

Encaso deque nohayaningún valorque destaquepara una determinadaposición, sesuele utilizaralguna técnica dedesempate o,máscoherente,usar uncarácter que indique quepara esa posición nohayunconsenso claro (p.ej.unasterisco)

Consensoylogos

• Sepuedenusarmayúsculasyminúsculaspararepresentarelgradodeconsenso,otécnicasmáscomplejas(logosdesecuencia)

ATTCTGGAAATCTCGAACACTGGG--------A*tCTgGa31233232

15

Ejercicio3

• Implementarlafunciónconsensus:– entrada:

• seqs (listadesecuenciasdeADNdelamismalongitud)– salida:str conlacadenadeconsenso

• Encasodeempate,sedesempataalfabéticamente

• Ejemplo:– seqs: ['ATTCTGGA', 'AATCCAGA', 'ATCCAGAA']– salida:ATTCAGGA

• Prueba:– ADNmitocondrialdedistintosprimates*

16*http://vis.usal.es/rodrigo/documentos/bioinfo/filogenia/mitDNAprimates.fasta

Patrones

Unpocodeestadística

• Unpocodebiología• DNAbox• K-mers• Motivos



Mutaciones

• Lasmutacionesdelcódigogenéticoson– Unarealidadbiológica– Unacomplicacióncomputacional– Unproblemaestadístico

Combinacionesypermutaciones

• Combinación:mezclasinimportarelorden• Permutación:mezclaordenada– permutación– posición

• Enamboscasos,podemospermitirrepeticióndeelementosono

• Combinación:473,374,347sonlomismo• Permutación:473esdistintode374y347

Permutacionesconrepetición

• ¿CuántasposiblescadenasdeDNAdelongitudrexisten?– Tenemosn elementos(aquí,n=4nucleótidos)– Hacemosr elecciones:n·n·n…·n (r veces)– Permutacionesconrepetición:nr

– Paraunacadenade30nucleótidos• 430=1152921504606846976posiblescadenas!~ 1trillón

Permutacionessinrepetición

• Tenemosn elementosentrelosqueelegirr– Elnºdepermutacionesconrepeticiónposibleses• nx(n-1)x(n-2)…x(n-r)• Enotraspalabras,hayunaposibilidadmenosconcadanuevaelección

• Funciónfactorial– n!=nx(n-1)x(n-2)x…x3x2x1– 4!=4x3x2x1=24


• SeanlosnucleótidosA,T,C,G(n=4)• Lasposiblespermutacionessinrepeticióndecadenasdelongitudr=4serán:

A à T à C à GC GG

T à A à C à GC GG

…4 · 3 · 2 · 1 = 24


• Podemostenerpermutacionessinrepeticióndehastalongitudr=n

• Sir<n,laprobabilidadnoeselfactorial– n·(n-1)·(n-2)·…·(n-r+1)

n!(n− r)!

Combinacionessinrepetición

• Enunacombinaciónnoimportaelorden• Lamejorformadeverloestomartodaslasposiblespermutacionessinrepetición(r=n)

• Porejemplo,parar=n=3Importaelorden (3!) Noimportaelorden(1)

123

132

213 123

23 1

312

321

Combinacionessinrepetición

• Porlotanto,sólotenemosquedividirlaspermutacionessinrepeticiónentrer!

• Estaesunafunciónimportante(coeficientebinomial)yserepresentacomosevearriba

n!r!(n− r)!

= nr

"

#$

%

&'

Combinacionesconrepetición

• Estafórmulaesunpocomásdifícildededucirintuitivamente:

n+ r −1r

"

#$

%

&'=(n+ r −1)!r!(n−1)!

ResumenPosición? Repetición? Posibilidades

(n elems.,relecs.)Comentarios

Permutación(sí) Sí nr nposibilidades porelección

No n posibilidadesenla1ªelecciónn-1enla2ªelección,etc.

Combinación (no) Sí

No Comola permutaciónsinrepeticiónperoeliminando lasposiblescombinatoriasencadaronda(r!)

Más información: http://www.mathsisfun.com/combinatorics/combinations-permutations.html

(n+ r −1)!r!(n−1)!

n!(n− r)!

n!r!(n− r)!

Ejercicio• SeaunacadenaS de11nucleótidos– Cuantascadenasposiblesmutadasen2nucleótidosexistenparaS?

• 1ºpaso:– CuántasposiblescombinacionesdelugareshayparamutacionesdeS en2nucleótidos?1. Cuántovalennyr?

– reselnºdecambiosquequeremosà 2– neselnºdepuntosposiblesdecambioà 11

2. Importaelordendelasmutaciones?– no(combinación)

3. Puedeunamismaposiciónrecibirlasdosmutaciones?– Vamosaconsiderarqueno(sinrepetición)

Ejercicio

• Tenemos55posiblesparesdeposicionesdondepuedehabermutación

11!2!(11− 2)!

= 55

Ejercicio4

• 2ºpaso: paracadaunodeesospares,¿cuántasposiblesmutacionespuedehaber?– r,puntosdecambioà 2– n,opcionesdecambioà 3– Importaelorden?à Sí(permutación)– Hayrepetición?à Sí– 32=9

• 55·9=495posiblesmutacionesen2nucleótidosenunacadenade11

• Ytodaslasposiblesmutacionesen3nucleótidos?

Patrones

Cazandomotivosesquivos

• Unpocodebiología• DNAbox• K-mers• Motivos



Motivosesquivos

• Elproblemaqueteníamosantes*esquesóloteníamosencuentamotivosqueaparecieranennuestrasecuencia– Peropuedehabermotivosqueno aparezcanenlasecuenciaperopormutacionesseanlosmáscomunes!

– Conclusión:debemostenerencuentatodoslosmotivosposiblesparauntamañodek-mer

*Ejercicio 2

Ejercicio

• Usarlafunciónmutations*:– entrada

• word:palabradelaquebuscamostodaslamutaciones• letters:posiblesletrasenword oenlasmutaciones• num_mismatches: númerodemutacionespuntuales

– salida• vectorcontodaslasposiblesmutacionesdeword

• UsarlafunciónmutationsEqualOrLessquecalculatodaslasmutacionesconhastanum_mismatches

* http://vis.usal.es/rodrigo/documentos/bioinfo/muii/mutations.py

Solución

http://vis.usal.es/rodrigo/documentos/bioinfo/muii/mutations.py

Ejercicio5

• ImplementarlafunciónallMutations:– entrada• seq:secuenciadelaquebuscamostodoslosk-mers• k:tamañodelosk-mers• d:númerodemutacionespuntuales

– salida• longituddelvectorcontodoslosk-mer posiblesenseq,incluidosaquellosquenoseencuentranexplícitamenteenseq,considerandohastadmutacionespuntuales

Ejercicio5• Pista:– UtilizarlafunciónmutationsEqualOrLess yunavariableconjuntodetiposet

• Ejemplo:– seq:CGCCCGAATCCAGAACGCATTCCCATATTTCGGGACCACTGGCCTCCACGGTACGGACGTCAATCAAAT

– k:9– d:2– salida:20847

• Prueba:oriC deEcoli,conk=9 yd=3

36

Ejercicio6

• ImplementarlafuncióncountKmersV2:– entrada:

• seq (cadenadondebuscamos)• d (nºdemutacionespermitidas)• k (tamañodelk-mer)• n (nºmínimodevecesqueseencuentraelk-mer)

– salida:diccionarioconlosk-mers (clave)ylafrecuenciaconlaqueocurren(valor)• contandohastadmutaciones• filtrandolosk-mers conmenosden ocurrencias• teniendoencuentak-mers quenoestánenlasecuencia

37

Ejercicio6

• Ejemplo:– seq:AACAAGCTGATAAACATTTAAAGAG– k:5– d:1– n:3– salida:{'AACAG': 3, 'TAAAA': 3, 'ATTAA': 3, 'AAGAT': 3, 'AAAAA': 4, 'TTAAA': 3, 'AAAAG': 3}

• Prueba:– OriC deEcoli conk=9 yd=1 (n=3)

38

BuscandoDNAboxes

• RecordemosquelaDNAboxconocidaexperimentalmenteenEcoli esTTACCACA,queaparece4vecesenlaregiónoricEC*

• SiejecutamoscountKmersV2 conk=9, d=1, min=2– TTACCACA tiene2ocurrencias– Losk-mersmásfrecuentestienen3– SeguimosigualqueconfindMotif (ej.2)

*http://en.wikipedia.org/wiki/Prokaryotic_DNA_replication

¿Quéfalla?

Ejercicio7• ModificarligeramentelafunciónanteriorparahacerlafuncióncountKmersV3:– entrada:

• seq (cadenadondebuscamos)• d (nºdemutacionespermitidas)• k (tamañodelk-mero)• n (nºmínimodevecesqueseencuentraelk-mer)

– salida:diccionarioconlosk-mers enseq (clave)ylafrecuenciaconlaqueocurren(valor)• contandohastadmutaciones• filtrandolosk-mers conmenosden ocurrencias• teniendoencuentak-mers quenoestánenlasecuencia• teniendoencuentalasocurrenciasdelk-mer reversocomplementario

40

Ejercicio7• Ejemplo:

– seq:AACAAGCTGATAAACATTTAAAGAG– k:5– d:1– min:4– salida:{'AAAAA': 4, 'CTTTT': 4, 'AACAG': 4, 'TTTAA': 5, 'TAAAA': 5, 'TTAAT': 4, 'TTGAA': 4, 'GTTAA': 4, 'ATTAA': 4, 'TTCAA': 4, 'TTAAC': 4, 'TTATA': 4, 'TTAAA': 5, 'TTTTA': 5, 'TATAA': 4, 'CTGTT': 4, 'AAAAG': 4, ’TTTTT': 4}

• Prueba:– OriC deEcoli conk=9 yd=1 (min=4)

41

BuscandoDNAboxes

• Contandolasocurrenciasinversascomplementarias,síqueencontramoslascuatroocurrenciasdeTTATACACA:

AATGATGATGACGTCAAAAGGATCCGGATAAAACATGGTGATTGCCTCGCATAACGCGGTATGAAAATGGATTGAAGCCCGGGCCGTGGATTCTACTCAACTTTGTCGGCTTGAGAAAGACCTGGGATCCTGGGTATTAAAAAGAAGATCTATTTATTTAGAGATCTGTTCTATTGTGATCTCTTATTAGGATCGCACTGCCCTGTGGATAACAAGGATCCGGCTTTTAAGATCAACAACCTGGAAAGGATCATTAACTGTGAATGATCGGTGATCCTGGACCGTATAAGCTGGGATCAGAATGAGGGGTTATACACAACTCAAAAACTGAACAACAGTTGTTCTTTGGATAACTACCGGTTGATCCAAGCTTCCTGACAGAGTTATCCACAGTAGATCGCACGATCTGTATACTTATTTGAGTAAATTAACCCACGATCCCAGCCATTCTTCTGCCGGATCTTCCGGAATGTCGTGATCAAGAATGTTGATCTTCAGTG

mutación sentido antisentido

BuscandoDNAboxes• Hemostenidomuchasuertedequeelmotivoestuvierajustoenlos500nucleótidosquehemoselegidoparadefinirOriC

• Haymuchaspreguntasenelaire:– Hayotrosmotivoscon4ocurrenciasenoriC. ¿Sonequivalentesalencontrado?¿Paraquésirven?

– ¿Porqué9-mersyno8-merso10-mers?– ¿Porquéunasolamutación,ynoninguna,odos?– ¿Cuántotardatualgoritmoparaunasecuenciade500bases?¿seríafactibleparabuscarentodoungenoma?

http://xkcd.com/830/

búsqueda de patrones

Documents