Búsqueda de Motivos para Casos de Prueba Reales Juan Marcelo Ferreira Aranda...

Búsqueda de Motivos para Casos Búsqueda de Motivos para Casos de Prueba Realesde Prueba Reales

Juan Marcelo Ferreira Aranda [jmferreira1978@gmail.com]Silvano Christian Gómez [cgomezpy@gmail.com]Marcelo Darío Rodas [rodas.marcelo@gmail.com]

Guido Andrés Casco [guiancs82@gmail.com]

Algoritmos para Biocomputación8vo Semestre, 2008

Algoritmos PatternBranching y WeederAlgoritmos PatternBranching y Weeder

MotivaciónMotivación

Muchos de los proceso celulares importantes incluyen el reconocimiento de pequeñas sub-secuencias (motivos) en el ADN.

Los motivos controlan la producción de proteínas prendiendo y apagando los genes que tienen la información necesaria para producirlas.

Por ello, el problema de búsqueda de motivosbúsqueda de motivos es de gran importancia para la biología molecular

Definición del ProblemaDefinición del Problema

El problema de búsqueda de motivos consiste entonces en identificar pequeños sitios conservadospequeños sitios conservados en el ADN sin conocer, a priori, la longitud ni la composición química de éstos.

La dificultad de este problema recae en que los motivos presentan mutacionesmutaciones, inserciones o ausencia de algunos nucleótidos y usualmente no ocurren exactamente igual.

•Ocurrencias aproximadasOcurrencias aproximadas de un solo patrón pueden ser encontradas eficientemente.•Buscar todos los posibles 44ll patrones patrones se vuelve más costoso.

Definición Formal del ProblemaDefinición Formal del Problema

El problema utilizado en este trabajo corresponde al Problema de Búsqueda de Motivos ImplantadosProblema de Búsqueda de Motivos Implantados, y se describe como sigue:

Dado un conjunto de NN secuencias secuencias cada una de longitud longitud TT y dada la longitud del motivo motivo ll y el número máximo de mutaciones permitidas mutaciones permitidas dd, encontrar todas las ocurrencias del motivo-(l, d) que se encuentran implantadas en las N secuencias.

Enfoques AnalizadosEnfoques Analizados

Algoritmo Pattern BranchingAlgoritmo Pattern Branching

Algoritmo WeederAlgoritmo Weeder

Pattern BranchingPattern Branching

un algoritmo deterministadeterminista

basado en patronespatrones

usa búsqueda local avara búsqueda local avara para encontrar el motivo correcto

alternativa de búsqueda en el espacio de motivosespacio de motivos

propone buscar por branching from sample stringsbranching from sample strings

Pattern BranchingPattern Branching

1 PATTERNBRANCHING(S, l, k);2 bestMotif = arbitrary motif pattern;3 bestScore = d(bestMotif , S)4 for each l-mer A0 in S do5 for j = 0 to k do6 if d(Aj , S) < bestScored(Aj , S) < bestScore7 bestMotif = Aj ;8 bestScore = d(bestMotif , S);9 fi10 Aj+1 = BestNeighbor(Aj )BestNeighbor(Aj );11 od12 od13 output bestMotif ;

•Como evaluar el Score?•Como definir BestNeighbor(A)

Pattern BranchingPattern Branching

Score:Score:PatternBranching usa distancia totaldistancia total:Dado un patron A, por cada secuencia Si en la muestra S = {S1, . . . , Sn}, sea d(A, Si) = min{d(A, P) | P Si} (Hamming)

Entonces la distancia total de A para la muestra esd(A, S) = ∑ Si S d(A, Si).

BestNeighbor:BestNeighbor:Para un patron A, sea D=Neighbor(A) el conjunto de patrones para el cual A difiere en exactamente 1 posición.

Se define BestNeighbor(A) como el patron B D=Neighbor(A) con la distancia total mas baja d(B, S).

WeederWeeder

Árbol de Sufijo

WeederWeeder

Corte en el árbol de Sufijo

Buscar patrones (p, e) con un árbol de sufijos en el algoritmo exacto. En el inicio de la búsqueda, todos los caminos de longitud e son validos.

WeederWeeder

Cálculo de una ocurrencia validaSe introduce el concepto de un umbral de error . Ejemplo: Si lo que se quiere estudiar son motivos de tamaño m, que admitan e mutaciones.

= e / m

WeederWeeder

Cálculo de una ocurrencia valida (cont.)

Descomposición de bloque de un patrón de longitud 16, y cantidad de mutaciones 4, Esto quiere decir que el umbral de error es con = 0.25. A lo máximo un error permitido en el primer bloque, dos errores en el segundo bloque y así sucesivamente.

WeederWeederProcedimiento de Expansión.

La Letra a es agregado al final del patrón p. Locp es un conjunto de punteros (Pos, e) en las terminales de ocurrencias del patrón p en el árbol, con el correspondiente error e, OccBits es una cadena de k-bit representando las ocurrencias de p en la cadena k. Next(Pos) retorna un conjunto de punteros de las posiciones en el árbol de búsqueda para mover por una letra abajo del camino apuntado por Pos, Occ(Pos) retorna la cadena de bit del primer nodo siguiente al camino apuntado por Pos; Lastpos’ es la ultima letra sobre el final del camino en la posición apuntada por Pos’.

WeederWeeder

Calculo del Score

donde obs(p) es el número de veces p fue encontrado en las regiones regulatorias, y totalm es el número total de longitud m oligos en las secuencias

Estimación de frecuencia como

Estimación de frecuencia esperada

donde H(p, e) es el conjunto de patrones con distancia Hamming e desde p

dado un patrón p de longitud m

si p aparece con e mutaciones

WeederWeeder

Calculo del Score (cont).Entonces, ya que p es el patrón que aparece con mayor e mutaciones en q secuencias del conjunto de secuencias S = S1…Sk, de longitud l1,...,lk. Primero que todo, usamos un puntaje basado en su mejor ocurrencia en cada secuencia. Ya que ei es el mínimo numero de mutaciones que p aparece en la i-th secuencia. Entonces, el puntaje especifico de las secuencias Seq(p) de p esta dado po

Así, esta medida refleja cuanto p esta conservado entre las secuencias de la base de datosj, también asociaremos con p un puntaje general

EvaluaciónEvaluación de Casos Reales de Casos Reales

• Se utilizo la base de datos TRANSFAC.

• Métricas evaluadas a nivel de nucleótidos.

• Las métricas utilizadas solo describen un bajo nivel de características de las muestras.

• La Sensibilidad es una métrica de cantidad.

• La Especificidad es una métrica de calidad.

• Existen muchas variables estadísticas que también pueden describir la solución.

• Las variables NO capturan la corrección del resultado de forma totalmente correcta.

Métodos de Evaluación Métodos de Evaluación PropuestaPropuesta

Métricas Estadísticas de evaluaciónMétricas Estadísticas de evaluación

xTP = es el numero de posiciones de nucleótidos en ambos sitios conocidos y sitios predichos.xFN = es el numero de posiciones de nucleótidos en los sitios conocidos, pero no en los sitios predichos.xFP = es el numero de posiciones de nucleótidos que no están en los sitios conocidos, pero que están en los sitios predichos.xTN = es el numero de posiciones de nucleótidos que ni están en los sitios conocidos, y tampoco están en los sitios predichos. OBS.: x puede ser s o n.

Métodos de Evaluación Métodos de Evaluación PropuestaPropuesta

Métricas Estadísticas de evaluación (Cont.)Métricas Estadísticas de evaluación (Cont.)

•Sensibilidad = xSn = xTP / (xTP + xFN)

•Especificidad = nSP = nTN / (nTN + nFP)

•Valor Predictivo Positivo = xPPV = xTP / (xTP + xFP)

•Coeficiente de Rendimiento = nPC = nTP / (nTP + nFN + nFP)

•Coeficiente de Correlación = nCC = nTP * nTN – nFN * nFP ((nTP+nFN)(nTN+nFP)(nTP+nFP)(nTN+nFN))1/2

Métodos de Evaluación Métodos de Evaluación PropuestaPropuesta

Propuesta de Cambio sobre el Cálculo de Propuesta de Cambio sobre el Cálculo de las Métricas Anterior de Evaluación.las Métricas Anterior de Evaluación.

Optimizaciones PropuestasOptimizaciones Propuestas

Pattern BranchingPattern Branching

Dos mejoras ya fueron implementadas en [1].*mejores evaluaciones (ranking) *eficiencia del algoritmo (GoodNeighbors)

Mejoras adicionales no son propuestas, debido a:•naturaleza biológica•modelo real

[1]Price, A.; Ramabhadran, S.; Pevzner, P.A. Finding subtle motifs by branching from sample strings. Bioinformatics. 2003;19(Suppl. 2):ii149–ii155. [PubMed].

Optimizaciones PropuestasOptimizaciones Propuestas

WeederWeeder

1. 1. En cuanto al tiempo de consumo.En cuanto al tiempo de consumo.

Gran parte del consumo de tiempo del algoritmo Weeder lo realiza una evaluación estadística de los motivos, mejoras hechas sobre esta parte seria recomendables para versiones futuras del programa. (Pavesi, 2005)

Optimizaciones PropuestasOptimizaciones Propuestas

Weeder

2. 2. En cuanto a la estructura utilizada para la solucion.En cuanto a la estructura utilizada para la solucion.

Optimizaciones PropuestasOptimizaciones Propuestas

Weeder

3. 3. En cuanto al tiempo de BEn cuanto al tiempo de Búsqueda de ocurrenciaúsqueda de ocurrencia utilizadautilizada..

Nuestro consejo seria, realizar una Búsqueda Bidireccional [10] sobre el Grafo de sufijo, cuando se evalúa una secuencia para determinar si es o no una ocurrencia, en los 2 sentidos (una búsqueda comienza del nodo root y se expande hacia abajo y la otra búsqueda comienza desde cualquiera de los nodos hojas) de la secuencia se van realizando una evaluación sobre el costo del umbral de error, en cada sentido se tiene que verificar que sea menor o igual de la mitad del umbral de error, esto quiere decir que la suma de las umbrales de las 2 búsquedas no podrían ser mayor que el umbral de error admitido.

Optimizaciones PropuestasOptimizaciones Propuestas

Weeder

3. 3. En cuanto al tiempo de BEn cuanto al tiempo de Búsqueda de ocurrenciaúsqueda de ocurrencia utilizada (Cont)utilizada (Cont)..

Con esto se podría descartar más rápidamente todas aquellas secuencias que el numero de mutaciones admitidos se encuentre al final de la secuencia estudiada o que la suma la cantidad de mutaciones superen tempranamente combinando los 2 extremos. Pero esto aumentaría el recurso de memoria utilizada para la búsqueda debido a que se ejecutaran 2 búsquedas paralelamente. Esta mejora tendría un costo exponencial pero con la diferencia que el exponente se dividiría por 2 comparado con la situación anterior cuando se utiliza una búsqueda unidireccional.

Optimizaciones PropuestasOptimizaciones Propuestas

Weeder

4. 4. En cuanto a la forma de Evaluación de las secuenciasEn cuanto a la forma de Evaluación de las secuencias para considerar si es o no una ocurrencia para casospara considerar si es o no una ocurrencia para casos realesreales

Actualmente Weeder utiliza una el cálculo de una distancia de hamming entre el patrón y la secuencia y que esté por debajo o igual a un umbral de error multiplicado el índice de la posición de comparación de la secuencia, para casos reales esta forma de evaluación no es optimo, una sugerencia en cuanto a esta parte es la siguiente:

- Probar utilizando una función de distancia de Manhattan. (Esta función ayudaría a corregir las situaciones donde se borra nucleótidos de la secuencia dándole una cierta puntuación).

Experimentos y ResultadosExperimentos y Resultados

A continuación se presentan los valores de: • Sensibilidad• Valor Predictivo Positivo• Especificidad• Coeficiente de Rendimiento • Coeficiente de Correlación,

para 8 muestras de casos reales de prueba en la ejecución del algoritmo de Weeder y Pattern Branching.

Experimentos y ResultadosExperimentos y Resultados

Sensibilidad para Weeder.

Sensibilidad (nSn)

0

0.025

0.05

0.075

Experimentos y ResultadosExperimentos y Resultados

Valor Predictivo Positivo para Weeder.

Valor Predictivo Positivo (nPPV)

0

0.05

0.1

0.15

0.2

dm02

dm06

hm12

hm25

mus

01

mus

02

yst0

5ys

t08

Experimentos y ResultadosExperimentos y Resultados

Especificidad para Weeder

Especificidad (nSP)

0.90.920.940.960.98

11.021.04

Experimentos y ResultadosExperimentos y Resultados

Coeficiente de Rendimiento para Weeder

Coeficiente de Rendimiento (nPC)

00.0060.0120.0180.0240.03

0.0360.0420.048

Experimentos y ResultadosExperimentos y Resultados

Coeficiente de Correlación para Weeder

Coeficiente de Corelación (nCC)

-0.05

-0.03

-0.01

0.01

0.03

0.05

0.07

0.09

Experimentos y ResultadosExperimentos y Resultados

Sensibilidad para PB.

Sensibilidad (nSn)

0

0.025

0.05

0.075

0.1

0.125

Experimentos y ResultadosExperimentos y Resultados

Valor Predictivo Positivo para PB.

Valor Predictivo Positivo (nPPV)

0

0.05

0.1

0.15

0.2

Experimentos y ResultadosExperimentos y Resultados

Especificidad para PB.

Especificidad (nSP)

0.90.920.940.960.98

11.021.04

Experimentos y ResultadosExperimentos y Resultados

Coeficiente de Rendimiento para PB.

Coeficiente de Rendimiento (nPC)

00.0060.0120.0180.0240.03

0.0360.0420.0480.0540.06

Experimentos y ResultadosExperimentos y Resultados

Coeficiente de Correlación para PB.

Coeficiente de Correlación (nCC)

-0.05

-0.03

-0.01

0.01

0.03

0.05

0.07

0.09

ConclusionesConclusiones

Pattern Branching y WeederPattern Branching y Weeder

Las pruebas con PatternBranching y Weeder revelan un pobre rendimiento en la búsqueda de motivos en casos reales debido a ciertos factores: Los motivos biológicos no siempre se ajustan al modelo basado en patrones (contando con pruebas extras utilizando un ranking).

PatternBranching presenta problemas al buscar motivos con muchas posiciones degeneradas, a pesar del enfoque de búsqueda local que encuentra eficientemente el optimo global.

ConclusionesConclusiones

Pattern Branching y WeederPattern Branching y Weeder

- El tiempo de ejecución de los algoritmos esta muy relacionadocon: * la longitud de motivo. * la cantidad de mutaciones maxima admitida. * el tamaño de la secuencia. * y los cálculos estadísticos de las frecuencias.

- La estructura de solución que se ofrece el Weeder para la busqueda de ocurrencias se podría mejorar.

MUCHAS GRACIAS POR MUCHAS GRACIAS POR LA ATENCIÓN!!!LA ATENCIÓN!!!