Bioinformática Sufijos Rodrigo Santamaría

Sufijos • Búsqueda de patrones en genomas • Tries • Suffix Tries • Suffix Trees • Suffix Arrays

Búsqueda de patrones en genomas Complejidad computacional

Buscando patrones en genomas • En la sesión 2 buscamos patrones en secuencias < 1K – Prueba, por ejemplo findPattern para buscar la DNA box de E coli TTATACACA en todo el genoma de E coli • [Cuando te rindas, podemos continuar]

Complejidad computacional • Pensemos un poco más en el problema que nos ocupa: encontrar todas las ocurrencias de una colección de patrones en un texto • Entrada: una cadena Text y un conjunto de cadenas más cortas Patterns • Salida: Todas las posiciones de Text donde comienza una cadena de Patterns

• En los casos vistos, la colección Patterns solía ser todas las posibles mutaciones de d posiciones de un patrón dado

Complejidad computacional • La solución propuesta en la sesión 2 podemos considerarla de fuerza bruta:

– Para cada posición en Text, revisar si alguno de los Patterns comienza igual – O(|Text|·|Patterns|)

• En el caso que nos ocupa, al menos |Text| va a ser muy grande – Y a veces (p.ej. alineamientos) |Patterns| también – P.ej. para un genoma humano, el genoma de referencia (Text) ocupa 3GB, y las lecturas de una secuenciación (Patterns) 1GB

Sufijos • Búsqueda de patrones en genomas • Tries • Suffix Tries • Suffix Trees • Suffix Arrays

Tries Estructura de datos algoritmo de búsqueda análisis de la complejidad

Tries • Uno de los mayores problemas de la solución por fuerza bruta es que para cada patrón recorremos una vez todo el texto – Es como si tenemos que llevar 20 ovejas de Salamanca a Barcelona y las vamos llevando de una en una – Tiene mucho más sentido agrupar las ovejas y luego llevarlas todas juntas

• En términos formales, queremos organizar todos los patrones en una única estructura de datos

Tries Root

a b n

p n

a

a d

t

b

n a

d

n

e

a

n

n

a

s

n

a

n

a

a

a

a

n

n

a

Trie para los patrones “ananas”, “and”, “antenna”, “banana”, “bandana”, “nab”, “nana” y “pan”

Ejercicio 1 • Implementar la función trie: – entrada:

• patterns (lista de cadenas)

– salida: trie correspondiente

• Ejemplo:

– patterns: ["GGTA", "CG", "GGC"] – salida: {'2:G': 3, '3:C': 6, '4:A': 5, '7:G': 8, '1:C': 7, '3:T': 4, '1:G': 2}

• Prueba:

– patterns=['ananas', 'and', 'antenna', 'banana', 'bandana', 'nab', 'nana’, 'pan’] El modo de representar el Trie puede variar. Para el ejemplo hemos utilizado un diccionario con claves {origen:arista} y valores {destino}. Las aristas son letras y los nodos son números, siendo el número 1 el nodo raíz

9

Tries y búsqueda de patrones • Para cada posición de texto: – Recorremos el trie desde la raíz por aristas que coincidan con el texto en la posición y con un patrón de los que buscamos • Si llegamos a un nodo hoja, el patrón correspondiente a la ruta está presente • En otro caso, ningún patrón está presente en el texto para dicha posición

10

Búsqueda en tries Root

a b n

p n

a

a d

t

b

n a

d

n

e

a

n

n

a

s

n

a

n

a

a

a

a

n

n

a

Buscando en la posición 0 de panamabananas encontramos pan* *Patrones de búsqueda: ananas and antenna banana bandana nab nana pan

Búsqueda en tries Root

a b n

n

a

a d

t

n

e

a

n

s

p

n a

b

n a n a

a

a

d

n

n

a

a n a

Buscando en la posición 2 de panamabananas ningún patrón encaja *Patrones de búsqueda: ananas and antenna banana bandana nab nana pan

Tries y búsqueda de patrones PrefixTrieSearch(Text, Trie) symbol