Post on 13-Feb-2015
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!!!