Modelos de redes bayesianas en el estudio de secuencias genómicas y otros problemas biomédicos (página 4)

Paso 3. Para cada Xi ? ListaVariablesSign hacer • Crear un enlace desde la variable C hasta Xi Paso 4. Ordenar (ListaVariablesSign)

Paso 5. Para i =1 hasta |ListaVariablesSign|-1 hacer

Para j =i+1 hasta |ListaVariablesSign| hacer

Si No (Terminar (Xi, Xj)) entonces

• Pr [i, j] = ChiCuadrado [Xi ; Xj]

51 Capítulo II. Nuevos algoritmos de aprendizaje estructural de Redes Bayesianas

• Sí (Pr [i, j] < 0.05) entonces

Crear un enlace desde Xi a Xj Paso 6. Retornar (Red G)

En el Paso 1 de inicialización, al igual que en el algoritmo explicado anteriormente, G representa la estructura de RB; en ListaVariablesSign se almacenan las variables predictivas que resultan significativas acorde a la prueba Chi-cuadadro y ListaVariablesPosibles almacena todas las variables predictivas del problema.

En el Paso 2 se llama a una función, a la que denominamos ChiCuadrado que calcula la significación estadística mediante la prueba Chi-cuadrado, entre las variables predictivas y la variable clase.

En el Paso 3 se crea un enlace desde el nodo correspondiente a la variable clase a cada uno de los nodos asociados a las variables significativas en ListaVariablesSign.

En el Paso 4 se ordena ascendentemente la ListaVariablesSign según la significación estadística.

En el Paso 5 |ListaVariablesSign| representa la cardinalidad de la lista de variables significativas y Terminar (Xi, Xj) es una función que, como se explicó con anterioridad, chequea las condiciones de terminación del algoritmo para Xi y Xj. En el Paso 6 se devuelve la RB en G.

Entre el Paso 4, es posible cambiar el orden de las variables según criterio de expertos, lo que permite introducir en el modelo de RB variables con significado biológico. 2.1.2.3 Algunas consideraciones sobre el algoritmo BayesChaid El algoritmo BayesChaid se basa también en el criterio de la prueba Chi-cuadrado para obtener la estructura de la red. Debido a que no construye árboles de decisión, este método no se ve afectado por la presencia de variables predictivas altamente correlacionadas. En su primer paso funciona de manera similar al algoritmo Naïve Bayes, pero con un proceso incluido de selección de rasgos (según el criterio del Chi-cuadrado). De esta forma se garantiza que las variables más relacionadas con la clase, se encuentren en relación directa

Capítulo II. Nuevos algoritmos de aprendizaje estructural de Redes Bayesianas 52 con ella. El algoritmo es capaz de “modelar” además, las relaciones existentes entre otras variables predictivas.

Obsérvese que ni en este caso ni en el anterior se tienen en cuenta las limitaciones de la prueba Chi-cuadrado, ver anexo 5. Ello no constituye un problema, pues la prueba estadística en este caso se utiliza sólo como criterio de selección de un nodo en la RB. 2.2 Aprendizaje Estructural de Redes Bayesianas basado en técnicas de Inteligencia Artificial

En el capítulo I se ha explicado que el aprendizaje de la estructura de una red bayesiana se convierte en un problema de optimización combinatoria, consistente en la búsqueda de la mejor red de todas las posibles en un espacio en el que intervienen N atributos para identificar los objetos del dominio de aplicación. Para el caso de redes múltiplemente conexas se trata de un problema de tipo NP (Cooper 1990), (Chickering 1996). Debido a esto, es que surge la necesidad de utilizar algoritmos que hacen uso de heurísticas para facilitar la búsqueda de la RB que representen satisfactoriamente el problema. 2.2.1 Técnicas de IA usadas en el manejo de información en Redes Bayesianas La IA ha jugado un papel importante como fuente inagotable de técnicas, métodos, modelos y algoritmos tanto para el análisis de datos biológicos como para el modelado y simulación de sistemas biológicos. Técnicas tales como redes neuronales artificiales, algoritmos evolutivos, autómatas celulares, RB y modelos ocultos de Markov, resultan ser enfoques ideales para dominios que se caracterizan por una explosión de datos y muy poca teoría, como es el caso de la Bioinformática.

En la actualidad los modelos bioinspirados se muestran eficientes en la solución de problemas prácticos, y en particular se pretende utilizar la técnica PSO en la búsqueda de la estructura de una RB. Este método muestra similaridades con otras técnicas de la computación evolutiva, como los AG (Davis 1991), pero no usa operadores de mutación y cruce, y tiene pocos parámetros a ajustar por lo que resulta más fácil de implementar (Beielstein et al. 2002), (Mahamed et al. 2005).

Capítulo II. Nuevos algoritmos de aprendizaje estructural de Redes Bayesianas 53 Una alternativa de los AG son los algoritmos de estimación de distribuciones (Estimation of distribution algorithms, EDAs), utilizados en Cuba fundamentalmente por (Ochoa et al. 2000), (Ochoa et al. 2003), (Caballero 2007) y (Piñero 2005) y un resumen de la aplicación en Bioinformática en (Armañanzas et al. 2008). En la tesis de (Caballero 2007) se muestran algunas deficiencias relacionadas con este método, y en la tesis de (Piñero 2005) se utilizan los EDAs en la optimización de reglas borrosas.

Aprendizaje estructural de Redes Bayesianas con PSO, combinación con la reducción de atributos

PSO ha sido exitosamente utilizado en la resolución de problemas de optimización con variables continuas. En este caso se selecciona el algoritmo propuesto por (Wang et al. 2006) de selección de atributos para usarlo en el aprendizaje de RB, pero considerando que se trata de un PSO binario (Correa et al. 2007). En (Chávez et al. 2007c) se muestra que si se realiza una selección de atributos previa, con el propio algoritmo PSO propuesto por (Wang et al. 2006), el aprendizaje de RB tiene mejor eficiencia que las que se obtienen con todos los rasgos de la base de casos, específicamente en problemas con muchas variables (digamos, más de 100). 2.2.2 Fundamentos generales del Algoritmo Como se ha explicado anteriormente, la búsqueda de la estructura de la red puede formularse como un problema de optimización en el espacio de las posibles redes ?, en otras palabras, determinar Xópt ? ?, H(Xópt) = H(Xi), ? Xi ? ?.

La función objetivo H es una métrica de calidad de las descritas en el capítulo cuatro de la tesis de Bouckaert (Bouckaert 1995) para el caso de búsqueda local se utiliza cualquiera de las métricas implementadas en Weka, o medidas que miden la exactitud en el caso de una búsqueda global cuando se trabajan con validaciones cruzadas de los datos según implementaciones en el ambiente Weka (Witten y Frank 2005) u otras implementadas como parte de este trabajo.

Entre las métricas de calidad local ya implementadas en Weka están:

a.La métrica de entropía según expresión

H(Bs, D) = – N??? QBayes(BS, D)= P(BS)?? ? Capítulo II. Nuevos algoritmos de aprendizaje estructural de Redes Bayesianas 54 Nijk Nij Nijk N log n qi ri

i=1 j=1 k=1 (2.1) donde

D: base de datos

BS: estructura de red

ri: cardinalidad del rasgo xi, i = 1, …, n

qi: cardinalidad del conjunto de padres de xi en BS, se puede calcular como el producto de las cardinalidades de los nodos padres de xi

Nij: número de casos en D para los que los padres de xitoman su j-ésimo valor, j =1, …, qi

Nijk: número de casos en D para los que los padres de xi toman su j-ésimo valor, y para los casos que xi toma su k-ésimo valor, k =1, …, ri

n

i=1

b. La métrica AIC (Akaike Information Criterion, Criterio de Información de Akaike), según la expresión QAIC (BS, D) = H(BS, D)+K (2.2) c. La métrica MDL (Minimum Description Length, longitud de descripción mínima), según expresión logN K 2 QAIC (BS, D) = H(BS, D)+ (2.3) d. La métrica Bayesiana según n qi i=0 j=1 ri

k=1 G(N'ij+Nijk) G(N'ijk ) ) G(N'ij ) G(N'ij+Nij (2.4) donde

P(BS) es una red a priori, en la implementación de Weka no se tiene en cuenta.

G(.)es la función gamma

N´ij y N´ijk representan selección de cantidades a priori, limitadas por: N'ij =?k i=1N'ijk QK2(BS, D)= P(BS)?? (ri -1)! ?Nijk! 55 r Capítulo II. Nuevos algoritmos de aprendizaje estructural de Redes Bayesianas

Si N´ij=1 , o lo que es lo mismo, N´ ij=rise obtiene la métrica K2.

e. La métrica K2 n qi i=0 j=1 ri (ri -1+ Nij)! k=1 (2.5) Si Nijk = 1/ri.qi, o lo que es lo mismo, N´ij =1/qi se obtiene la métrica BDe

Es posible utilizar otras medidas propuestas en la literatura en el caso de conjuntos de datos con clases desbalanceadas como fitness, (Beielstein et al. 2002), (Ye 2003), (Eitrich et al. 2007), (Guo y Viktor 2007), las que se han añadido como métricas de calidad global en el trabajo.

Las métricas de calidad global que se han implementado, se han utilizado frecuentemente para bases de datos desbalanceadas, se basan en los resultados del modelo clasificador, es por ello que en su mayoría se utilizan medidas para evaluar clasificadores en problemas de clasificación supervisada, a partir de la matriz de confusión que se obtiene cuando se prueba el clasificador en un conjunto de datos que no intervienen en el entrenamiento.

Entre las métricas de calidad global que se han implementado en Weka como parte de este trabajo se tienen:

a. La métrica G-means, según expresión (2.6) g = sensibilidad*especificidad b. La métrica de la sensibilidad relativa se representa en la expresión sensibilidad especificidad (2.7) RS =

c. La métrica GM en la expresión (2.8) GM = rVP + rVN d. El coeficiente de correlación de Matthews en la expresión

Capítulo II. Nuevos algoritmos de aprendizaje estructural de Redes Bayesianas 56 VP *VN – FP*FN (VP + FN)(VN + FP)(VP + FP)(VN + FN) mcc = (2.9) e. Otra métrica de efectividad se muestra en la expresión 1-(ß 2 +1) * precisión*sensibilidad ß 2 * precisión+ sensibilidad ?ß = (2.10) En la expresión 2.10 si ß =1 se obtiene la media armónica entre sensibilidad y precisión, si ß =0, ?ß =1- precisióny si ß =8, ?ß =1-sensibilidad .

En la modelación del problema de búsqueda a partir del algoritmo PSO se define cada partícula como una RB, la cual se representa como una matriz de adyacencia B. Se puede 2

con dicho espacio, pero habría que chequear que no existan ciclos. La eliminación de ciclos se puede lograr, por ejemplo, eliminando de forma aleatoria arcos que formen parte de ciclos existentes (Chávez et al. 2007c).

Se conoce que un grafo dirigido representa un ordenamiento topológico, si y solo sí este no presenta ciclos, es posible a partir de una permutación formar un grafo acíclico dirigido. Partiendo de esto en (Chávez et al. 2007c), (Chávez et al. 2008c), (Chávez et al. 2008a) se propone una forma de generar el espacio de búsqueda garantizando que no existan ciclos.

Para comprender la idea del algoritmo BayesPSO, se decidió utilizar en su cuerpo una función booleana “Terminación” que devuelve “verdadero” en caso de que se cumpla una de las condiciones de terminación. Ellas son: •

• Cantidad de generaciones que van a interactuar las partículas o iteraciones del algoritmo (CantGeneraciones),

El algoritmo puede terminar si en dos iteraciones sucesivas no se mejora el resultado de la métrica de calidad que evalúa la RB.

Capítulo II. Nuevos algoritmos de aprendizaje estructural de Redes Bayesianas 57 2.2.3 Algoritmo BayesPSO El algoritmo que se propone es PSO binario, por lo que el algoritmo PSO original (Wang et al. 2006), (Ferat et al. 2007) se adapta, de modo que la actualización de las partículas se realiza como propone (Correa et al. 2007).

Entrada: Un conjunto de variables {X1, …,XN, C}

Salida: Una estructura de RB G

Paso 1. Inicializar •

•

•

•

• Xi es una partícula, en este caso una RB representada como una matriz de adyacencia (matriz del espacio ?),

{X1, X2, …, XN} es una bandada (conjunto de partículas),

{V1, V2, …} son velocidades (matrices del espacio ? asociadas a cada partícula que indican su movimiento),

{XpBest1, XpBest2, …, XpBestN} son los mejores puntos del espacio localizados por cada partícula,

XgBest es el mejor punto localizado por la bandada. Paso 2. Repetir

Paso 3. Actualizar la velocidad. Las velocidades de todas las partículas (1,2,…, cantPart) se actualizan acorde a la expresión (1.14) que se detalló en el epígrafe 1.1.3.2 del capítulo I. y que repetimos en 2.11. (2.11) Vi = wVi + c1 rand(X iBesti – X i)+ c2 Rand(X gBest – X i)

Según la expresión (2.12) la velocidad se convierte al intervalo [0, 1]. S(Vi)= 1 1+ e-Vi (2.12) Paso 4. Actualizar la posición. Para lograr actualizar las partículas se debe añadir la velocidad a cada partícula según expresión (2.13).

Capítulo II. Nuevos algoritmos de aprendizaje estructural de Redes Bayesianas

X i(t +1)= X i(t)+ Vi 58

(2.13) Paso 5. Actualizar la memoria. Actualizar XpBest y XgBest acorde a los resultados de la función objetivo o fitness en dicha iteración y el objetivo que se persigue ya sea minimizar o maximizar la métrica de calidad empleada.

Paso 6. Hasta Terminación ()

Paso 7. Retornar (XgBesten G)

En el Paso 1 se asigna aleatoriamente valores a la población de Xi (la generación de las redes acíclicas se logra a partir de una permutación aleatoria p de (1, 2,…, n) con distribución uniforme, dicha red se representa como una matriz de adyacencia), de esta forma se propone en (Chávez et al. 2007c), Vi y XpBesti de cada partícula se inicializan como copia de Xi y XgBest se inicializa con la mejor partícula de acuerdo a la métrica.

En el Paso 3, cantPart es la cantidad de partículas que van a existir en cada generación.

El algoritmo se repite del Paso 2 al Paso 6 mientras no se cumpla la condición de terminación.

En el Paso 5 se puede seleccionar como función fitness una de las implementadas en Weka, u otras que se le han añadido al mismo como se explicó previamente. 2.2.4 Algunas consideraciones sobre el algoritmo BayesPSO El algoritmo BayesPSO difiere de manera notable con respecto a los otros dos. Es más complejo desde el punto de vista espacial, pues parte de estructuras de redes seleccionadas al azar y después de un proceso iterativo, se llega a la estructura final de la red.

El algoritmo garantiza una buena solución. Se señala como desventaja que es necesario mantener almacenadas en cada paso, las matrices triangulares superiores relacionadas con cada partícula (RB), la matriz que almacena la mejor red obtenida hasta el momento por cada una de ellas, y además la correspondiente a la mejor RB global, que es la candidata a ser la solución final en cada paso y que será la solución definitiva en el último paso.

No obstante a estas deficiencias, cabe señalar que, con los ejemplos que se han corrido y que se mostrarán en epígrafes posteriores de esta tesis, no han existido nunca dificultades

Capítulo II. Nuevos algoritmos de aprendizaje estructural de Redes Bayesianas 59 de memoria. Más importante es el análisis de la complejidad computacional desde el punto de vista temporal que se hará en el siguiente epígrafe. 2.3 Análisis del comportamiento de los algoritmos El análisis teórico de los algoritmos que se proponen para el aprendizaje estructural de RB se hace mediante el orden de complejidad temporal de cada uno, y a su vez se utiliza un fichero de datos extraído del UCIML (Asuncion y Newman 2007) para el estudio de los resultados que muestran dichos algoritmos si se utiliza la RB como clasificador junto a otros clasificadores. Además, se hace una comparación con otras 18 bases de la UCIML. 2.3.1 Análisis de la complejidad temporal Para realizar el análisis de la complejidad temporal debemos tener en cuenta las siguientes variables:

A ? número de árboles a crear en el algoritmo ByNet,

M ? número de casos en la base de datos13,

N ? número de atributos del problema,

T ? cantidad máxima de valores diferentes que pueden tomar los atributos,

K ? número máximo de padres por nodos de la RB,

N´? variables significativas según la prueba Chi-cuadrado y que forman la ListaVariablesSign,

V ? niveles o profundidad en los árboles para el algoritmo ByNet o camino mas largo en la RB y que relacionamos con la variable MaxDepth,

P ? cantidad de partículas en el algoritmo BayesPSO,

I ? cantidad de generaciones o iteraciones en el algoritmo BayesPSO, y

C ? número de clases diferentes. 13 Es equivalente a número de instancias o tamaño máximo de la población.

?V *N' = O(N'*T Capítulo II. Nuevos algoritmos de aprendizaje estructural de Redes Bayesianas 60 2.3.1.1 Análisis de la Complejidad temporal del Algoritmo ByNet El análisis de la complejidad temporal se hace sobre la base de la descripción por pasos del algoritmo descrito previamente en el epígrafe 2.1.1.2:

La complejidad temporal del Paso 1 de inicialización es un O (N), pues el tamaño de la lista de variables posibles coincide con la cantidad de atributos del problema.

La complejidad temporal del Paso 2 es un O(M * N) pues hay que recorrer todos los atributos y la función que determina la probabilidad del estadístico Chi-cuadrado tiene complejidad O(M). El Paso 3 que ordena la lista de variables significativas tiene orden de complejidad temporal O(N’LogN’), pues N’ es la cantidad de elementos de esta lista.

En el Paso 4 se entra en un ciclo donde se construyen los árboles; se sabe que la complejidad para construir los árboles es a lo sumo O(N * T 2) (Quinlan 1986), (Quinlan 1993).

En el peor caso se construye un árbol completo en el cual cada camino en el árbol prueba cada variable de la lista de variables significativas, se asumen N´ atributos y T valores diferentes que pueden tomar los atributos.

En cada nivel V, en el árbol, se debe examinar los T-V valores que quedan para cada atributo en ese nivel para calcular la probabilidad aplicando Chi-cuadrado, de donde se obtiene: ) 2 T

V=1 (2.14) Si se llegan a construir todos los árboles, resulta finalmente una complejidad temporal máxima de: O(A * M * N´ * T 2), el cual puede ser aún menor, si se hace el análisis como (Ruiz 2006) que reporta un orden de complejidad temporal medio para árboles: O(M*N*log2M). 2.3.1.2 Análisis de la Complejidad temporal del Algoritmo BayesChaid El análisis de la complejidad temporal del algoritmo BayesChaid se hace sobre la base de la descripción por pasos del algoritmo descrito previamente en el epígrafe 2.1.2.2.

Capítulo II. Nuevos algoritmos de aprendizaje estructural de Redes Bayesianas 61 La complejidad temporal del Paso 1 de inicialización es un O (N), pues el tamaño de la lista de variables posibles coincide con la cantidad de atributos del problema.

La complejidad temporal del Paso 2 es O (M * N) pues hay que recorrer todos los atributos y determinar la probabilidad del estadístico Chi-cuadrado.

Para el Paso 3 la complejidad es un O (N´ ).

En el Paso 4 se ordena la lista de variables significativas cuyo orden de complejidad temporal es O (N’LogN’) donde N’ es la cantidad de elementos de esta lista.

En el Paso 5 se evalúa la función que determina la probabilidad del estadístico Chi- cuadrado dentro de dos ciclos anidados, obteniéndose un O (N’ 2 * M), que coincide con el orden de complejidad temporal del algoritmo BayesChaid. 2.3.1.3 Análisis de la Complejidad temporal del Algoritmo BayesPSO Para el análisis de la complejidad temporal del algoritmo BayesPSO, descrito en el epígrafe 2.2.3 se debe conocer el orden de la métrica que mide la calidad de la red que se obtiene. La complejidad temporal es un O (I * P * max(N 2, O(métrica))).

La complejidad de las métricas se reportan en el capítulo cuatro de la tesis de Bouckaert (Bouckaert 1995), en el peor caso es un O(M.K.T).

Hasta aquí se demuestra que los tres algoritmos tienen una complejidad temporal polinomial si se hace una selección adecuada de los parámetros. 2.3.1.4 Comparación de los algoritmos Si se toma el valor que pueden tomar los parámetros que se utilizan para realizar el análisis de complejidad temporal de los algoritmos, es posible hacer una comparación entre los tres algoritmos descritos en este capítulo, cuyo orden de complejidad temporal se muestra en la Tabla 2.1.

Si se parte de la definición de RB hay algunos parámetros a los que se le asignan valores suficientemente pequeños, de modo que la RB que se obtiene sea lo menos compleja posible, sin descuidar la calidad de los resultados que ofrece la misma.

Capítulo II. Nuevos algoritmos de aprendizaje estructural de Redes Bayesianas 62 Por ejemplo, en el algoritmo ByNet el parámetro que mide la cantidad de árboles a construir es importante, como ya se explicó previamente, pues para valores pequeños se logra evitar obtener modelos asimétricos, este parámetros está estrechamente relacionado con el número de padres en los algoritmos BayesChaid y BayesPSO.

Los valores que pueden tomar las variables resultan también significativos en el análisis de la complejidad.

Si se pretende establecer un orden en cuanto a la complejidad temporal de los algoritmos, el de menor complejidad resulta ByNet, le sigue BayesChaid y por último BayesPSO.

Tabla 2.1. Resultado del análisis de la complejidad temporal de los algoritmos propuestos en el trabajo. 2.3.2 Ejemplo de aplicaciones para validar los resultados Para mostrar los resultados de los algoritmos se seleccionó originalmente una base de datos de las donadas en el UCIML (Asuncion y Newman 2007): la base de datos para reconocimiento de Promoters en secuencias de la E. Colic. La base de datos se crea por (Harley y Reynolds 1987). Esta base de datos se ha utilizado en la evaluación de algoritmos de aprendizaje automatizado (Towell et al. 1990).

Está formada por 106 casos y 58 atributos (incluida la clase), de ellos 57 rasgos predictores se corresponden con posiciones de pares de bases de secuencias nucleotídicas, representadas por A, G, T y C (ver anexo 1) y la variable clase por (positivos o negativos).

Se utilizaron los algoritmos que se proponen en la tesis, y según se aprecia en la Tabla 2.2 los tres algoritmos muestran resultados similares, el algoritmo BayesPSO hace mejor clasificación de los casos positivos con razón 0.906. Atendiendo al área bajo la curva ROC el mejor resultado es para el algoritmo BayesChaid con valor 0.942, pero si se utiliza el coeficiente de correlación de Matthews el mayor valor lo obtiene el algoritmo ByNet con valor 0.7.

Capítulo II. Nuevos algoritmos de aprendizaje estructural de Redes Bayesianas 63 Tabla 2.2. Resultados de la evaluación realizada con los algoritmos propuestos en el trabajo, en la base de datos para reconocimiento de Promoters en secuencias de la E. Colic. Se hicieron además pruebas con 18 bases de datos del repositorio UCIML (Asuncion y Newman 2007).

En el anexo 6 se puede ver las características de las bases de datos utilizadas. Estas son diversas, 11 de ellas tienen rasgos discretos, 3 tienen rasgos continuos y 4 presentan combinación de ellos; 10 de ellas tienen 2 clases y el resto tiene, entre 3 y 19. La cantidad de casos varía también en las bases de datos, desde bases con 24 casos hasta bases con 3196 casos. De esta manera podemos ver la comparación para bases internacionales de propósito general y en particular el comportamiento de estos métodos ante bases bioinformáticas.

En las Tablas 2.3 y 2.4 se muestran los resultados de la exactitud y área bajo la curva ROC, para cada uno de los algoritmos propuestos en el trabajo, descritos en los epígrafes 2.1-2.3 de este capítulo.

La comparación en cuanto a exactitud con las 18 bases de datos de la UCIML se hace entre los algoritmos propuestos: ByNet, BayesChaid y BayesPSO y tres clasificadores bayesianos: RB K2, RB TAN y CBN.

Se seleccionó la prueba no paramétrica de Friedman (Siegel 1987) para analizar si hay diferencias significativas entre los resultados obtenidos por los métodos utilizados.

Como se observa en la Tabla 2.5, la significación en cuanto a exactitud es 0.199, mayor que 0.05, por lo que no se evidencian diferencias significativas entre los clasificadores.

64 Capítulo II. Nuevos algoritmos de aprendizaje estructural de Redes Bayesianas

Tabla 2.3. Resultados de la ejecución con bases de datos de la UCIML para exactitud Tabla 2.4. Resultados de ejecución de los algoritmos con bases UCIML para el área bajo la curva ROC.

Capítulo II. Nuevos algoritmos de aprendizaje estructural de Redes Bayesianas 65 Tabla 2.5. Resultados de la prueba de Friedman si se comparan los algoritmos en cuanto a la exactitud en las 18 bases de datos de la UCIML. En la Tabla 2.6 se observan los rangos promedios de esta prueba para la exactitud, el mejor resultado se obtiene con el algoritmo BayesChaid con rango promedio 4.06 y le sigue en rango promedio BayesPSO con valor 3.94.

Tabla 2.6. Rangos promedios obtenidos con prueba de Friedman para la exactitud. Para los valores de las áreas bajo la curva ROC se verifican diferencias entre los métodos empleados. Para analizar cuáles son los métodos que difieren, se realizan pruebas no paramétricas de Wilcoxon (Siegel 1987).

En la Tabla 2.7 se muestran los resultados de la prueba de Friedman en la comparación entre los tres algoritmos propuestos y los tres clasificadores bayesianos escogidos para la comparación según el área bajo la curva ROC. Se aprecia que la significación es de 0.00 valor menor que 0.05, por lo que se rechaza la hipótesis de que el comportamiento de los clasificadores en similar para esta medida de validación (área bajo la curva ROC).

Para ver entre que clasificadores hay diferencias, se aplica la prueba de rangos de Wilcoxon (Siegel 1987). Estos resultados se muestran en la Tabla 2.8.

Capítulo II. Nuevos algoritmos de aprendizaje estructural de Redes Bayesianas 66 Tabla 2.7. Resultados de la prueba de Friedman si se comparan los algoritmos en cuanto al área bajo la curva ROC en las 18 bases de datos de la UCIML. Las pruebas de Wilcoxon evidencian que el único algoritmo que tiene diferencias significativas con los demás es ByNet en cuanto a las áreas bajos las curvas ROC

Tabla 2.8 Resultados de la prueba de rangos de Wilcoxon basada en las áreas bajo la curva ROC en las 18 bases de datos de la UCIML entre los seis clasificadores. Los resultados de la comparación evidencian que los métodos BayesChaid y BayesPSO muestran resultados en cuanto a eficiencia mejor a K2, TAN y Naïve Bayes, pero ByNet difiere del resto cuando se evalúan los resultados con las áreas bajo las curvas ROC.

El algoritmo ByNet no ofrece buenos resultados como clasificador en todas las aplicaciones, pero tiene valor teórico ya que permite obtener sub-grupos de relaciones entre posiciones distantes en secuencias genómicas para inferir en cualquier posición de la misma.

Capítulo II. Nuevos algoritmos de aprendizaje estructural de Redes Bayesianas 67 2.4 Conclusiones parciales del capítulo En este capítulo se proponen tres nuevos algoritmos para la obtención de la estructura de la RB, dos basados en criterios estadísticos (prueba de independencia Chi-cuadrado) y uno basado en medidas de ajuste y búsqueda.

Se demuestra que la complejidad temporal de los tres algoritmos es polinomial. Se logra establecer un orden en cuanto a la complejidad temporal de cada uno, siendo el algoritmo ByNet el de mejor resultado, seguido del algoritmo BayesChaid y por último BayesPSO.

El algoritmo ByNet es el más simple de los tres, pero las relaciones estadísticas de independencia no quedan correctamente reflejadas en la red lo que influye en la calidad de los resultados cuando se hacen inferencias sobre la misma. Este algoritmo se presenta en el trabajo pues constituye un antecedente a los que se desarrollan posteriormente: BayesChaid y BayesPSO, el primero de estos dos ofrece buenos resultados como clasificador. Si se escoge un número de niveles pequeño, las redes que obtiene son bastantes simples pues tiene incluida la selección de atributos basada en la significación estadística, resultado que es muy fácil de extender a significación biológica, si se tiene conocimiento sobre el domino del problema.

El algoritmo BayesPSO, es el de mayor complejidad desde el punto de vista de la representación de las redes, y también desde el punto de vista temporal pues depende del número de atributos en el conjunto de datos y de la métrica que se escoja. Además se obtienen redes múltiplemente conexas más complejas, esto influye directamente en la complejidad en la propagación de evidencias. Pero se ha demostrado que si el problema no tiene demasiados atributos (digamos, menos de 100) o se hace una selección previa de estos, el movimiento sobre el espacio de búsqueda garantiza obtener las mejores propiedades sobre la red resultante.

Se comparan los métodos con otros clasificadores bayesianos reportados en la literatura y se demuestra estadísticamente que los algoritmos propuestos muestran un desempeño similar a los clásicos para esta tarea.

Los algoritmos BayesChaid y BayesPSO tienen eficiencia similar o mejoran los resultados de los demás clasificadores con los que se compararon.

3. APLICACIONES DE LOS ALGORITMOS PROPUESTOS

En este capítulo se describen las implementaciones computacionales realizadas y se presentan dos aplicaciones Bioinformáticas: una sobre predicción de interacciones de proteínas y otra sobre predicción de sitios de splicing o búsqueda de genes. Además se muestra otra aplicación real sobre diagnóstico de la HTA, lo que ilustra la factibilidad de usar los algoritmos desarrollados en otras áreas. 3.1 Sobre la implementación de los algoritmos Como se explicó en el epígrafe 1.1.4 se cuenta en el mercado internacional con numerosos productos de software para el aprendizaje, edición y ejecución de RB. En múltiples casos estos sistemas tienen un alto precio debido esencialmente a los beneficios que les reportan a las organizaciones que los utilizan. Esta es una de las causas por lo que se hace necesario que las investigaciones lleven conjuntamente desarrollos de productos de software para los modelos que se proponen.

En los inicios de esta investigación, se propuso el primer algoritmo explicado en el epígrafe 2.1.1. Las aplicaciones se dedicaron, fundamentalmente a problemas de diagnóstico médico, y para el aprendizaje de RB se usaron productos de software tradicionales como: Mathematica, SPSS, Microsoft Excel, etc. Para hacer inferencias con estas redes se hizo un primer desarrollo de software denominado ByShell (Chávez y Rodríguez 2002), después se desarrolló un sistema que incluyó el aprendizaje y la propagación, pero que aún no estaba totalmente validado (Rodríguez et al. 2006). Estos software se desarrollaron en Borlan Delphi, y esta plataforma no es de código libre.

Si se tiene en cuenta que, la implementación de nuevos algoritmos como extensión de la plataforma de aprendizaje automatizado Weka, ha mostrado ventajas tales como (Morell et al. 2006): • Se simplifica la implementación pues solo hay que redefinir métodos ya existentes en Weka o crear otros nuevos con las funcionalidades específicas del algoritmo a adicionar.

Capítulo III. Aplicaciones de los algoritmos propuestos 69 •

•

•

•

• Se facilita la validación de un nuevo modelo. No es necesario preocuparse por implementar las variantes de validación, ni las medidas de desempeño a emplear; se pueden utilizar las ya existentes en la herramienta. Es posible hacer ejecuciones en lotes y en varias terminales, sin esfuerzos adicionales de programación utilizando el modo Experimentador.

Se propicia y facilita la comparación del nuevo algoritmo con otros ya reportados en la literatura e implementados en la herramienta, facilitando el análisis de la factibilidad de este último, algo que sería más costoso en tiempo si se hubiera implementado como un modelo aislado.

Facilidades para el pre-procesamiento de los datos, y el hecho de que los filtros estén separados de los algoritmos facilita la implementación y el reuso.

Se propicia el uso y divulgación de los nuevos modelos implementados. El hecho de queden incorporados a Weka los hace disponibles para la comunidad de científicos y usuarios de este campo.

El tiempo de desarrollo del prototipo de un software a la medida, utilizando un algoritmo implementado en Weka, se disminuye a partir de reutilizar su código.

Para fortalecer esta plataforma, al lograr una contribución en este campo, se pueden incluir los tres algoritmos definidos en el capítulo dos.

El Weka está desarrollado en Java, y está estructurado de forma tal que se hace muy sencillo hacer cambios en el código. Por las características del trabajo que se está desarrollando, sólo se hará referencia a lo concerniente a la adición de los algoritmos de aprendizaje estructural propuestos como nuevos modelos de clasificación.

En este sistema existe una clase abstracta que implementa los métodos que debe usar cualquier clasificador, y que es denominada weka.classifiers.Classifier. Si se desea implementar un nuevo modelo de clasificación se deben redefinir el método buildClassifier(), y al menos uno entre los métodos clasifyInstance() y distributionForInstance().

Capítulo III. Aplicaciones de los algoritmos propuestos 70 Si la adición a Weka es un nuevo clasificador bayesiano, el cual forma parte del paquete “weka.classifier.BayesNet”, el clasificador BayesNet usa diferentes tipos de algoritmos para el aprendizaje automatizado de la RB a usar en el proceso de clasificación, a los que denomina algoritmos de búsqueda, cuya tarea principal es definir la estructura de la RB.

La clase que contenga la codificación del nuevo algoritmo debe quedar ubicada en este nombre de espacio: “weka.classifier.bayes.net.search”, en los paquetes ya definidos: ci, fixed, global y local, o crear uno nuevo si el algoritmo no se ajusta a ninguno de los ya existentes. Los algoritmos ByNet y BayesChaid se ubicaron en un nuevo paquete que nombramos: deterministic, y el algoritmo BayesPSO en el paquete global de los ya definidos en Weka. Las relaciones que se establecen entre los paquetes y clases se pueden ver en el diseño del diagrama de relación de clases, que se muestra en el anexo 10, la cual se elaboró con un lenguaje de modelo unificado: Paradigma Visual para UML VisualParadigm (Hernandis 2005), (Headquarters 2007).

Los ficheros de datos se deben definir de uno de los dos tipos siguientes: •

• ARFF (Attribute-Relation File Format)

CSV (delimitado por comas) En el anexo 11 se especifica la sintaxis de estos ficheros.

Para utilizar la herramienta Weka previamente se debe instalar la maquina virtual de java, y Weka se ejecuta simplemente ejecutando el fichero weka.jar, o desde la línea de comandos: java -jar weka.jar o por ejemplo C:WINDOWSsystem32java.exe -Xmx290m -jar " D:mchavezWekaweka.jar"

En el ejemplo la ejecución permite aumentar la memoria virtual con -Xmx290m a partir 290MB como memoria mínima, además se índica el camino en el que está instalado el java y el camino al fichero weka.jar.

Cuando se ejecuta Weka se tiene una ventana selectora de interfaces, la que se utiliza para realizar pruebas: Explorer y para hacer experimentos: Experimenter.

Capítulo III. Aplicaciones de los algoritmos propuestos 71 Se le puede indicar a Weka por línea de comandos la ejecución de un clasificador específico, como los implementados para crear RB, se deben incluir todos los parámetros necesarios: parámetros para abrir ficheros, el clasificador a utilizar, etc.

Esta opción es más difícil, de hecho para usar Weka en la versión Weka parallel (Arboláez 2008), que permite ejecute la validación cruzada (Kohavi 1995), (Efron y Tibshirani 1997), (Fu y Carroll 2005), (Varma y Simon 2006), con varias terminales, se crearon dos ficheros que ejecutan Weka para poder indicar los puertos de conexión, uno para weka cliente y uno weka servidor, y si no se va a realizar la validación cruzada con varios subconjuntos de datos con distintas terminales, porque no merece la pena hacerlo, se puede usar el Weka cliente. En el anexo 11 se pueden ver las características de estos dos ficheros.

Cuando se utiliza el algoritmo PSO se selecciona una medida de calidad, en Weka ya se encuentran incorporadas medidas basada en validaciones cruzadas o la medida basada en el método LOO-CV (Leave one out crossvalidation: validación cruzada dejando uno fuera). Se hizo la extensión a Weka de otras medidas de calidad global: dos medidas presentadas en (Eitrich et al. 2007), que a su vez se consideran medidas de calidad robustas para clasificación, se trata del coeficiente de correlación de Matthews y una medida de calidad basada en la sensibilidad y una medida que mide la precisión de la clasificación de (Fawcett 2004), las cuales se han descrito en el capítulo dos.

Alternativamente se incorporó a Weka un filtro para selección de atributos propuesto por (Wang et al. 2006) el cual se usa previamente a la construcción de la RB, especialmente cuando hay demasiados atributos (digamos, más de 100) (Chávez et al. 2007b). 3.2 Planteamiento del problema sobre predicción de interacciones de proteínas

Se trata de predecir interacciones de proteínas desde una base de datos de Arabidopsis thaliana, la misma se obtuvo por el Departamento de Biología de Sistemas de Plantas14, a partir de documentación reportada en la literatura. Dicha base contiene información relevante de las interacciones de proteínas de la Arabidopsis thaliana: atributos de 14 Department of Plant Systems Biology, Flanders Interuniversity Institute for Biotechnology (VIB), Ghent University, Belgium.

Capítulo III. Aplicaciones de los algoritmos propuestos 72 dominios conservados, valores de expresión para calcular coeficientes de correlación de Pearson, información de anotaciones de GO (Gene Ontology, genes ontólogos), OG (Orthologous Group, grupos ortólogos), entre otros.

Resultados sobre interacciones de proteínas en esta planta se pueden ver en (Cui et al. 2007). Otras investigaciones de interacciones de proteínas se pueden ver en los trabajos de (Long et al. 2005) en el que se utiliza el CBN para predicción de interacciones de proteínas en hongos, se utiliza por su simplicidad para integrar distintas fuentes de datos genómicos, pero se tiene una alta dependencia estadística entre rasgos, reportan coeficientes de correlación entre 0.904 y 0.97. En (Qi et al. 2006) se explica la importancia del estudio de las interacciones de proteínas en hongos, pero a veces se tienen resultados incompletos, por lo que se obtienen valores altos de la razón de falsos positivos y razón de falsos negativos, en este trabajo se enfrenta el problema con seis clasificadores: árboles aleatorios (Random Forest, RF), k vecinos más cercanos (k NN)-RF, árboles de decisión, CBN, regresión logística y máquinas de vectores soportes (Supor Vector Machine), los mejores resultados se obtienen con el k NN –RF, la mayor exactitud es del 68 %.

En humanos hay resultados muy interesantes con RB en (Scott y Barton 2007), aquí se reporta un estimado de la razón de falsos positivos del 90%, dada la existencia de pocas bases de datos para el mayor proteoma: el humano. 3.2.1 Análisis de los datos El conjunto de datos consta de 4314 pares de proteínas, 1438 son ejemplos de verdaderas interacciones y 2876 son ejemplos negativos (o al menos dudosos). Los resultados reportados anteriormente demuestran que identificar simultáneamente ejemplos positivos y negativos resulta difícil, pues es raro encontrar reportes de pares de proteínas que no interactúan, especialmente a gran escala y los casos negativos para el aprendizaje no son del todo seguros. Se siguió el enfoque descrito por (Zhang et al. 2004): se usa un conjunto aleatorio de pares de proteínas (después de filtrar las positivas); esto se justifica porque la fracción de pares de proteínas que interactúan, en el conjunto total de pares de proteínas es pequeño.

Capítulo III. Aplicaciones de los algoritmos propuestos 73 3.2.2 Rasgos del problema Se seleccionaron en total 11 rasgos, mas la variable especial denominada clase, la cual identifica si hay o no una interacción de proteína: 1.

2.

3.

4.

5.

6.

7.

8.

9. “GO similarity score biological process: average” (GO_sim_bp_avg)

“GO similarity score biological process: sum” (GO_sim_bp_sum)

“GO similarity score biological process: maximum” (GO_sim_bp_max)

“GO similarity score cellular component: average” (GO_sim_cc_avg)

“GO similarity score cellular component: sum” (GO_sim_cc_sum)

“GO similarity score cellular component: maximum” (GO_sim_cc_max)

“Pearson correlation coefficient for micro-array type 1” (PCC_1_devtissues)

“Pearson correlation coefficient for micro-array type 2” (PCC_2_heterog)

“Domain score 1: number of common domains” (domain_match) 10. “Domain score 2: number of common domains/ total number of different domains for the two proteins together” (domain_score)

11. “Orthology information” (orthology_score)

12. clase (valor cero identifica que no interactúan las proteínas, y el valor uno que hay una interacción de proteínas) 3.2.3 Discusión de los resultados La tarea de predicción de interacciones de proteínas se ha enfrentado con múltiples métodos de clasificación, con técnicas estadísticas, de IA y en este caso con RB.

En la Tabla 3.1 se muestran los resultados con técnicas estadísticas: análisis discriminante (AD), regresión logística (RL), árboles de clasificación CHAID (AC CHAID) y árboles de clasificación QUEST (AC QUEST), con técnicas de IA: dos métodos de RB: RB K2 y RB obtenidas mediante pruebas de independencia condicional (RB CI), este caso no se utiliza el CBN, pues se tiene una alta correlación entre los rasgos del problema, el valor mayor del coeficiente de correlación es 0.782, lo que indica dependencia estadística entre los rasgos

Capítulo III. Aplicaciones de los algoritmos propuestos 74 del problema, además se muestran resultados de árbol de decisión con el algoritmo ID3 (AD ID3) (Quinlan 1986).

Tabla 3.1. Resultados con otras técnicas de aprendizaje supervisado para el problema de predicción de interacciones de proteínas Con ninguno de los métodos de clasificación utilizados se ha logrado incrementar los porcientos de verdaderas interacciones de proteínas. Tanto la exactitud como el área bajo la curva ROC se mantienen con valores similares, igual sucede con la razón de negativos y positivos.

Los resultados con los algoritmos que se proponen en la tesis se muestran en la Tabla 3.2, estos son similares a los que se muestran en la Tabla 3.1 para otras técnicas de aprendizaje supervisado, pero estos resultados son mejores a los que se describieron en el epígrafe 3.2 para interacciones de proteínas de otros organismos.

Tabla 3.2. Resultados de los algoritmos propuestos en la tesis para obtener RB en el problema de predicción de interacciones de proteínas En todas las ejecuciones de los algoritmos se usó la validación cruzada con 10 subconjuntos para estimar la predicción de error de los métodos propuestos y ver el comportamiento frente a otros algoritmos (Varma y Simon 2006).

Capítulo III. Aplicaciones de los algoritmos propuestos 75 Si se evalúa los algoritmos por el área bajo la curva ROC y la razón de verdaderas interacciones, el algoritmo BayesChaid muestra el mejor desempeño, si se mide por la exactitud es el algoritmo BayesPSO. 3.2.4 Validación mediante el uso del modelo obtenido con el algoritmo ByNet Cuando se obtiene un modelo de RB, este se puede evaluar por el uso que se le da a la red, en este caso se escoge el algoritmo ByNet para mostrar cómo se puede usar las RB, a pesar de que no es el que mejores resultados obtuvo se demostró en el capítulo anterior que es el de menos complejidad temporal. Con la RB se puede inferir cualquier variable tanto predictivas como la variable dependiente o clase.

Como se explicó, desde el punto de vista estadístico es posible definir cuál es la importancia de las variables con respecto a la variable dependiente.

En este caso las 11 variables están correlacionadas, y en la red están todas las variables, pero como se aprecia en la Figura 3.1 las variables que más se relacionan con la clase son domainmatch y PCC1devtissues.

Según los resultados de la prueba Chi-cuadrado domainscore y PCC2hetreog están más relacionados con la variable clase que PCC1devtissues, pero como hay correlación entre todas las variables predictivas, estas variables forman parte del primer árbol que se crea, y la red queda como se observa en la Figura 3.1.

Debe quedar claro que esta dependencia es puramente estadística, y si coincide con el significado biológico, las predicciones deben ser mejores.

Cuando no se tienen evidencias en la red se tienen las probabilidades a priori para cada valor de las variables, por ejemplo la probabilidad a priori de una interacción de proteínas es 0.34, lo que se observa en la Figura 3.2.

Capítulo III. Aplicaciones de los algoritmos propuestos 76 Figura 3.1. RB obtenida con el algoritmo ByNet Figura 3.2. Red Bayesiana obtenida con el algoritmo ByNet sin evidencias

Si domainmach es mayor que 0.5 se obtiene una probabilidad de 0.97 de que exista una interacción de proteína, lo cual se observa en la Figura 3.3.

Capítulo III. Aplicaciones de los algoritmos propuestos 77 Figura 3.3. Red Bayesiana cuando la evidencia es: domainmach mayor que 0.5

Si las evidencias son que GO_sim_bp_max es menor que 4.5, domain_score es menor que 0.21 y PCC_devtissues es menor que 0.00001 la probabilidad de una interacción de proteína es 0.85, además se tiene probabilidad uno de que domain_match es menor que 0.5.

Si se quiere saber cómo se comportan las variables cuando se tiene certeza de una interacción, los resultados en la red son los que se aprecian en la Figura 3.4. Figura 3.4. Red Bayesiana cuando la evidencia es: se conoce que hay una interacción de proteína, o sea la variable clase toma el valor 1.

Capítulo III. Aplicaciones de los algoritmos propuestos 78 3.2.5 Mejorando el balance de verdaderos positivos y negativos Todo aprendizaje supervisado es más eficiente y eficaz si la base de entrenamiento tiene casos muy bien distinguidos en cada clase, digamos, se conocen positivos sin duda y negativos sin duda. Es un principio natural y obvio, incluso del aprendizaje no computarizado, por ejemplo el de un niño.

La base de entrenamiento de interacciones de proteínas no presenta estas características idóneas. De hecho, de los denominados negativos, no se está absolutamente seguro que lo sean, sólo se conoce que esas interacciones no están reportadas como positivas. Entonces el aprendizaje puede estar sesgado y hasta es natural que este grupo tenga el mejor porcentaje de clasificación, simplemente porque el clasificador aprende con dudas.

Una técnica para aliviar este sesgo es filtrar los falsos negativos, concretamente seleccionar dentro de los negativos, aquellos de los cuáles podemos tener “un poco más de confianza” de que sean negativos.

Nos basamos en reglas puramente probabilísticas y se siguen los siguientes criterios:

1. Eliminar de la muestra de aprendizaje aquellos casos en que la predicción de falsos negativos tuvo una probabilidad por debajo de un cierto umbral.

2. Al mismo tiempo, evitar eliminar demasiados casos para no perder información que puede ser útil. Esto se logra fijando dicho umbral no demasiado alto y al mismo tiempo escogiendo el clasificador que más Verdaderos Positivos (y por tanto menos Falsos Negativos) tuviese: resultó el BayesChaid, ver Tabla 3.2.

Los resultados con los algoritmos, una vez que se ha reducido la base de datos con los falsos positivos que obtienen el algoritmo BayesChaid se muestran en la Tabla 3.3. Estos mejoran sustancialmente, pues son superiores a los de las Tablas 3.1 y 3.2, para todas las medidas de validación.

Mahdavi ya había utilizado esta técnica, auxiliándose de criterios biológicos pero este reduce los falsos positivos (Mahdavi y Lin 2007).

Los resultados con respecto a otros clasificadores, confirma el buen desempeño de los algoritmos ByNet, BayesChaid y BayesPSO.

Capítulo III. Aplicaciones de los algoritmos propuestos 79 Tabla 3.3. Resultados de los algoritmos propuestos para el problema de interacciones de proteínas cuando se reducen falsos negativos. Otra alternativa consiste en estudiar el comportamiento de los modelos desde las posibilidades de análisis que permiten las curvas ROC. En la Tabla 3.4 se muestra el comportamiento del modelo obtenido con el algoritmo BayesChaid en función de distintos puntos de corte. Puede observarse que cuando la probabilidad de ser positivo en la clasificación se reduce a 0.18 se logra un balance de las razones de FP y FN, pero por supuesto, a costa de pérdidas en la exactitud.

Tabla 3.4. Resultados del análisis de balance de verdaderas y falsas interacciones de proteínas Para este problema de predicción de interacciones de proteínas, los resultados de los algoritmos que se proponen en la tesis muestran un comportamiento similar a los que se

Capítulo III. Aplicaciones de los algoritmos propuestos 80 reportan en la literatura, además para algunas de las medidas que evalúan la calidad de los resultados estas se mejoran. Por ejemplo una de los problemas fundamentales en esta aplicación es el bajo porciento de verdaderos positivos, sin embargo con el algoritmo BayeChaid este valor es relativamente mejor al obtenido por el resto de los clasificadores aplicados. En cuanto a exactitud el algoritmo BayesPSO muestra los mejores resultados. 3.3 Planteamiento del problema sobre localización de splice sites Uno de los problemas fundamentales de la Bioinformática, específicamente de la genómica consiste en la localización de genes dentro del genoma de un cierto organismo. Las secuencias de ADN de la mayoría de los genes se transcriben en ARN mensajero que a su vez se traducen en las proteínas. En los procariotas (organismos menos desarrollados) el ARN mensajero es una mera copia del ADN. Sin embargo, en los eucariotas, el ADN contiene en los genes segmentos codificantes (exones) y no codificantes (intrones) y estos últimos son “cortados” durante el proceso de transcripción, mecanismo conocido como splicing que coloca a los exones de un gen consecutivamente, y listos para traducirse en la secuencia de aminoácidos que conforman la proteína (Figura 3.5) (Foley y Lewin 2004). La detección de intrones y exones constituye una de las vías para abordar el problema de la localización de los genes. Codón de inicio Codón de parada Exón Exón Exón Exón Intrón Intrón Intrón Transcripción

P R O T E Í N A

Figura 3.5. Esquema de la conformación de un gen como sucesión de exones e intrones. En la transcripción a RNA mensajero se desechan los intrones y se colocan los exones consecutivamente para traducirse en la proteína

Capítulo III. Aplicaciones de los algoritmos propuestos 81 Los bordes de estos intrones es lo que se conoce como splice sites. El splice sites en el principio del intrón es conocido como donor, mientras que el que lo finaliza es conocido como acceptor. Los “donors” se caracterizan por la presencia del par de nucleótidos “GT” al inicio del intrón, los “acceptors” se identifican por el par “AG” al final del intrón (Figura 3.6). Entonces se podría intentar reconocer donors y acceptors a través de estos dinucleótidos y con ellos los intrones. La limitación de este enfoque es que estos dinucleótidos abundan en el genoma, y sólo un pequeño por ciento de estas combinaciones son splice sites reales (Saeys 2004).

Si se tienen secuencias con el par “GT” de las cuales se conozca si son verdaderos o falsos donors se puede intentar “aprender” a clasificarlos utilizando la información de las bases nucleotídicas de su entorno y otro tanto podría hacerse a partir de secuencias con el par “AG” de las cuales se conozca si son verdaderos o falsos acceptors. Así el problema original se descompone en dos problemas de clasificación. Figura 3.6. Esquema general de un intrón entre dos exones. Observe como el inicio y el fin del intrón se marcan por los splice sites

Se ha abordado el problema de detectar si las combinaciones de estos nucleótidos (“GT” o “AG”) son verdaderos o falsos splice sites desde diversas técnicas de clasificación de Estadística y de IA. En la presente tesis se aplican las RB para afrontar el problema. Donors Exón 1 Exón 2 acceptors intrón CCTCAGGTCACTCTTTGGCAACCGTCACAATAAAGATAGGGG

Capítulo III. Aplicaciones de los algoritmos propuestos 82 3.3.1 Análisis de datos La base de datos de splice sites para humanos fue construida en la Universidad de Ghent, Bélgica, a partir de obtener ARN mensajero desde la base de datos pública EMBL (Base de datos de secuencias nucleotídicas) (EMBL 2009). Se eliminaron los genes redundantes y se obtuvo una base de 1115 genes. Desde estos genes sólo se tuvieron en cuenta los intrones con splice sites canónicos, o sea GT para donor y AG para acceptor, que fueron usados como positivos. Las instancias negativas fueron definidas a partir de los dinucléotidos GT y AG que se encontraban en sitios que no eran de splice sites.

Quedaron construidas dos bases de datos de secuencias de nucleótidos, con el objetivo de clasificar verdaderos y falsos splice sites: identificación de donors y acceptors. Las bases de datos para este trabajo se conformaron con 7000 casos cada una, 6000 falsos y 1000 verdaderos, tal como sugiere la proporción aproximada real de verdaderos y falsos splice sites en los genomas (Saeys 2004). 3.3.2 Rasgos del problema La longitud de las secuencias de pares intrón-exón es muy variable. Debido a esto, se realizó un análisis estadístico acerca de la distribución de la longitud de exones e intrones en los genes del homo sapiens con el objetivo de encontrar una ventana que permitiera todas las secuencias de la misma longitud (Grau et al. 2007a). De este estudio se obtuvo que es suficiente con 80 bases nucleótidas en los intrones y 22 en los exones. En la base de los donors, por ejemplo, ello se traduce en 22 posiciones (del exón) a la izquierda del par GT y otras 78 posiciones (del intrón) a la derecha de dicho par.

En las dos bases de datos se representan las posiciones nucleotídicas a partir del álgebra Booleana primal (Sánchez 2006). Esto es: G-00, T-10, A-01, C-11. De esta manera, como se tienen 102 posiciones (22 exón, 80 intrón), se convierten en 204 variables predictivas, que se etiquetan como v1_1, v1_2, v2_1, v2_2,…, v102_1, v102_2 y cada una de ellas es un valor binario (0 ó 1). En particular, en la base de donors se tienen las posiciones v23 y v24 constantes porque representan a GT, esto es v23_1=v23_2=0 porque corresponden a G y v24_1=1, v24_2=0 porque corresponden a T. Como son constantes, no intervendrán en el

Capítulo III. Aplicaciones de los algoritmos propuestos 83 proceso de clasificación pero se incluyen en la base para claridad de la interpretación de la misma. 3.3.3 Discusión de los resultados El problema de clasificación de donors se seleccionó para medir el desempeño de uno de los métodos propuestos, cuando se utiliza la validación cruzada con 10 subconjuntos distribuida entre distintas máquinas, debido a que la base de datos es la que mayor cantidad de variables y de casos cuenta entre los tres problemas que se intentan resolver. Se realizó con el método BayesChaid, pero se puede probar con cualquier método, ya sea de los que se proponen, o cualesquiera de los implementados en Weka. Los parámetros seleccionados para realizar las pruebas fueron: dos padres, tres niveles y 100 casos como mínimo en las sub-poblaciones., pero esto fue sólo para realizar el experimento, podrían escogerse otros. Las ejecuciones se hicieron en varias computadoras utilizando desde dos hasta cinco terminales remotas para realizar la validación cruzada.

El resultado de este experimento es que se logró disminuir el tiempo de más de cinco horas a menos de una hora. Esta mejora en tiempo resulta fundamental si el problema a resolver es de Bioinformática, porque en la mayoría de los problemas que se presentan tienen grandes volúmenes de información a procesar. Los resultados obtenidos por los algoritmos propuestos para el aprendizaje de la estructura de RB, descritos en el capítulo dos se muestran en las Tablas 3.5 y 3.6.

Tabla 3.5. Resultados en donnor con varios clasificadores 1 Obtenido con el Algoritmo QUEST para obtener árboles de decisión, resultados reportados en (Grau et al. 2007b)

Capítulo III. Aplicaciones de los algoritmos propuestos 84 En ambos problemas la clasificación con los modelos obtenidos es satisfactoria, el método BayesChaid obtiene los mejores resultados de falsos positivos en acceptors y ByNet en donors, esta medida es una de las que se quiere minimizar, una de las causas de este resultado es el desbalance de los verdaderos splice sites con respecto a los sitios aleatorios o casos negativos.

En (Degroeve et al. 2002) se obtienen mejores resultados para clasificación de splice sites en arabidopsis thaliana, lo que se logra con una buena selección de rasgos, resultados similares para esta planta en la tesis de (Saeys 2004), pero no ocurre lo mismo en la clasificación de sitios de splice sites en humanos.

Cuando se usa el método BayesPSO no se reportan mejoras, aún usando las medidas fitness que han sido implementadas por otros autores para estas situaciones de desbalance y que se han incluido en la tesis como métricas de calidad, las cuales se describen en el capítulo dos de la tesis. Sin embargo es conveniente usar PSO cuando se hace una selección de atributos previa a la clasificación como se propone en (Chávez et al. 2007b), lo que ha reportado mejores resultados.

Tabla 3.6. Resultados en Acceptors utilizando distintos algoritmos para clasificar 3.3.4 Validación mediante el uso del modelo obtenido con el algoritmo ByNet Para clasificación de donors y acceptors con el algoritmo ByNet el mejor modelo de RB se obtiene cuando la red tiene un solo nivel, o sea la clase depende de las variables más relacionadas con esta desde el punto de vista estadístico. Se escogen 10 variables, para tener en cuenta algunos nucleótidos alrededor del sitio de splicing.

La red para donor se muestra en la Figura 3.7, las variables que forman la red están alrededor del sitio donor, las variables que le corresponden a este sitio son v23 y v24:

Capítulo III. Aplicaciones de los algoritmos propuestos 85 Figura 3.7. Red bayesiana para clasificación de donors con el algoritmo ByNet

Cuando aún no se tienen evidencias, la red muestra las probabilidades a priori para cada una de las variables, y a medida que se conoce el valor de determinada variable, se infieren otras probabilidades en base a la evidencia. A continuación se describen algunos ejemplos, en los que para dar la evidencia de un nucleótido es necesario conocer dos posiciones acorde a la representación que se explicó en el epígrafe 3.3.2, pero si sólo se conoce una de las variables asociada a un nucleótido la posición puede ser uno u otro.

Si se tienen evidencias de posiciones en la secuencia (las que se indican en las columnas a la izquierda de la Tabla 3.7 y 3.8, la probabilidad de inferir o no un sitio donor se indica en la última columna de dichas tablas. Las redes con los resultados de la propagación ante distintas evidencias para donors y acceptors se pueden ver en los anexos 7 y 8.

La red obtenida para acceptors se muestra en la Figura 3.8, y en las Tablas 3.9 a la 3.11 se muestran resultados de la propagación de evidencias en la clasificación de acceptors (posiciones que corresponden a las variables v81 y v82) del mismo modo que se explicó para la clasificación de donors.

Tabla 3.7. Probabilidad de que se tenga un sitio donor cuando se conocen tres posiciones antes y tres después de este sitio

Capítulo III. Aplicaciones de los algoritmos propuestos 86 Tabla 3.8. Probabilidad de que no se tenga un sitio donor cuando se conocen tres posiciones después de este sitio Figura 3.8. Red bayesiana para clasificación de acceptors con el algoritmo ByNet

Tabla 3.9. Probabilidad de se tenga un sitio acceptors cuando se evidencia la presencia de los nucleótidos T o C en diez posiciones antes de este sitio. Tabla 3.10. Probabilidad de no se tenga un sitio acceptors cuando se evidencia la presencia de los nucleótidos A o G en siete posiciones antes este sitio

Capítulo III. Aplicaciones de los algoritmos propuestos 87 Tabla 3.11. Probabilidad de que no se tenga un sitio acceptors cuando se evidencia la presencia de los nucleótidos A o G en once posiciones antes de este sitio 3.3.5 Mejorando la predicción de verdaderos splice sites Para lograr mejorar la predicción de verdaderos splice sites se plantea la necesidad de reducir los casos considerados falsos positivos (FP), o sea los casos negativos de donors o acceptors que se predicen erróneamente como positivos. En la predicción de genes (en este caso a través de la localización de sitios de splicing), la disminución de los FP es fundamental porque dicha clasificación es apenas un primer paso para un conjunto de investigaciones costosas en dinero y tiempo destinadas a caracterizar completamente el gen y su funcionalidad y no pueden desgastarse estos recursos en un gen dudoso (Chuang y Roth 2001).

En la Tabla 3.12 se muestra cómo se comporta esta modificación, usando el punto de corte que utiliza el clasificador para emitir una respuesta ante un caso dado. Los resultados se obtienen desde la curva ROC. Se escogieron los resultados en donors con el algoritmo BayesChaid para mostrar este resultado. Como se aprecia en la Tabla 3.12 el punto de corte se escoge por encima de 0.5 con el objetivo de lograr una sensibilidad dada, y en consecuencia la reducción de los falsos positivos.

Tabla 3.12. Resultados en la predicción de verdaderos splice sites cuando se reducen los falsos positivos para la base de donors.

Capítulo III. Aplicaciones de los algoritmos propuestos 88 De esta forma se verifica la presencia de un donor solamente si se está muy seguro de ello, aunque existe pérdida de exactitud esta no es significativa (Chuang y Roth 2001).

Los mejores resultados los obtiene el algoritmo ByNet, la red muestra relaciones desde el punto de vista estadístico de variables alrededor del sitio donor (acceptor) directas con la variable clase. Los algoritmos que se proponen en la tesis muestran mejores medidas de validación que el resto de los clasificadores aplicados. 3.4 Predicción de la Hipertensión arterial Los modelos de RB pueden ser utilizados en otros dominios de aplicación, específicamente se han desarrollado aplicaciones en varios problemas biomédicos, uno de los cuales, relacionados con la HTA, se describe en el trabajo. También han sido utilizados en otros campos, por ejemplo, en la elaboración de sistemas tutoriales inteligentes, ver por ejemplo la tesis de maestría de (Medina 2007), (Medina et al. 2007).

La HTA es un factor de riesgo para numerosas enfermedades, entre las que se destacan con una incidencia mayor las coronarias. Muchos autores coinciden en asegurar que la HTA es por sí misma una enfermedad.

El corazón bombea sangre a través de las arterías a todo el cuerpo, la tensión que se genera en el interior arterial se denomina presión arterial. La HTA ó presión alta es la elevación de esta presión arriba de un límite que se considera normal (140/90 mmHg). Es la principal enfermedad crónica degenerativa y la más común causa de muerte, afecta aproximadamente al 20% de la población mundial. La elevación anormal de la presión constituye un importante factor de riesgo coronario.

Varios estudios realizados consideran esta enfermedad como la primera causa de muerte en el mundo (Ordúñez et al. 2001), (Silva 2009). En Cuba y en particular en el municipio de Santa Clara, es la segunda causa de muerte.

Al medirse la presión arterial se anotan dos números, el mayor es la presión sistólica, corresponde a la presión del corazón al contraerse para bombear la sangre y el número menor es la presión diastólica, que es la presión de la sangre en las arterias en la fase de relajamiento del corazón. Para un correcto diagnóstico de hipertensión, el médico mide

Capítulo III. Aplicaciones de los algoritmos propuestos 89 varias veces la presión arterial, en diferentes condiciones de esfuerzo y en diferentes horas del día. En personas hipertensas, la variación es mayor y permanece alta la mayor parte del día, incluso en los períodos de descanso.

La Organización Mundial de la Salud la ha denominado epidemia silenciosa pues por lo regular se presenta de forma asintomática, ocasionando daños como: trombosis, hemorragias cerebrales, infarto del miocardio, muerte súbita, insuficiencia renal, entre otras.

El conocimiento actual de éste problema de salud pública a nivel mundial, obliga a buscar estrategias de detección, control y tratamiento (Benet et al. 2003).

Los factores de riesgo de esta enfermedad son tan disímiles que pueden ir desde factores económicos y sociales, hasta ambientales y étnicos, por lo que su diagnóstico no debe limitarse simplemente a la toma de la presión arterial sistólica y diastólica sino analizar cada uno de estos factores. Sin lugar a dudas el estudio de todos los factores requiere de una gran cantidad de recursos materiales y humanos de los que no siempre es posible disponer.

Como parte de un proyecto de investigación conjunta entre la UCLV y la Universidad de Oviedo, hace algunos años se creó la “Proyección del Centro de Desarrollo Electrónico hacia la Comunidad” (PROCDEC) cuyo objetivo principal es desarrollar un estudio de personas supuestamente normotensas primero en la ciudad de Santa Clara y luego en toda la nación de modo que se desarrolle una Campaña contra la HTA y el riesgo vascular.

En el desarrollo de este proyecto participa un grupo multidisciplinario formado por psicólogos, cardiólogos, nefrólogos, genetistas, fisiólogos, clínicos, médicos de laboratorio, ingenieros, matemáticos especialistas en estadística y cibernéticos.

Participan además especialistas en Medicina Integral General de los centros hospitalarios José Ramón León, Chíqui Gómez y Ramón Pando Ferrer. Estos especialistas realizan la captura de los datos, mientras el grupo multidisciplinario es quien realiza el diagnóstico (Gutiérrez 2003).

Capítulo III. Aplicaciones de los algoritmos propuestos 90 3.4.1 Análisis de los datos En este estudio la muestra estuvo constituida por un total de 849 individuos entre 18 a 78 años de edad, de ambos sexos, pertenecientes a cinco policlínicos de la ciudad de Santa Clara.

Se confeccionó una historia clínica con información del paciente contenida en las siguientes variables: edad, sexo, raza, índice de masa corporal, consumo de bebidas alcohólicas, fuma, diabetes mellitus, dislipidemia, número de padres con HTA, número de abuelos con HTA, tensión arterial sistólica y diastólica basal, al primer y segundo minuto, presión arterial media, glicemia, triglicéridos, colesterol total hdl y ldl, entre otras. A partir del análisis de todas las variables, el comité de expertos clasificó a cada paciente como normotensos o hipertensos. La base de casos cuenta con 23 rasgos además de la clase (diagnóstico).

Los casos hipertensos incluyen los casos declarados hipertensos o hiperreactivos (pre- hipertensos). El estado de hiperreactividad vascular se consiguió mediante una ergometría isométrica denominada Prueba del Peso Sostenido (PPS) (Benet et al. 2001). Esta prueba basa su principio en introducir al método clásico de la medición de la tensión arterial la condición de que los pacientes realicen, en posición sentada, un ejercicio físico isométrico, que consiste en mantener un peso de 500 gramos con el brazo izquierdo extendido en ángulo recto al cuerpo durante 2 minutos. La presión arterial se toma en el brazo contrario antes del ejercicio y a partir del segundo 50 del segundo minuto. 3.4.2 Discusión de los resultados Se ejecutaron los algoritmos propuestos y los resultados de las principales medidas para su evaluación se aprecian en la Tabla 3.13.

Se usó la validación cruzada con 10 subconjuntos en la estimación del error de la clasificación. En esta aplicación los resultados se consideran suficientemente buenos.

En el capítulo dos de la tesis se ha expresado que el algoritmo ByNet se ha utilizado en problemas de diagnóstico médico con buenos resultados, se confirma en la predicción de la HTA que aunque no es el mejor clasificador, el resultado es satisfactorio.

Capítulo III. Aplicaciones de los algoritmos propuestos 91 Tabla 3.13. Resultados para la predicción de la HTA usando los algoritmos propuestos y otros tres clasificadores. 1

2

3.4.3 La clase de los positivos se corresponde con los casos hipertensos.

La clase de los negativos son los casos normotensos.

Validación mediante el uso del modelo obtenido con el algoritmo BayesChaid Para mostrar el uso de la RB obtenida para el diagnóstico de la HTA, se puede escoger cualquiera de los modelos obtenidos con buenas características. Para ejemplificar tales inferencias se utilizó el modelo obtenido con el algoritmo BayesChaid que es el que mejores resultados dio como modelo clasificador.

Para la propagación de evidencias se utilizó el software ELVIRA descrito en el capítulo uno. El algoritmo de propagación utilizado es el de eliminación de variables.

Algunos ejemplos para ver el comportamiento del modelo de RB obtenido: por ejemplo sin evidencias la probabilidad de ser hipertenso es de 0.52. Otro ejemplo, un caso con la presión sistólica al minuto uno alta, se eleva la probabilidad de hipertenso a 0.97, también aumenta la probabilidad de la presión sistólica al segundo minutos, así como las presiones diastólicas y la presión arterial media. En el anexo 9 se muestran otros ejemplos para distintas evidencias. Existe la posibilidad de propagación conocidas varias evidencias simultáneamente, o por ejemplo si se conoce a priori que el paciente es hipertenso, como se comportan las otras variables que lo caracterizan. 3.4.4 Mejorando la predicción de falsos sanos Se hace necesario reducir los casos falsos negativos, pues en los problemas de diagnóstico médico es más peligroso declarar un enfermo como sano, que lo inverso. Ello se logra si se reduce el umbral de probabilidad de enfermo por debajo de 0.5. Se escoge para este análisis

Capítulo III. Aplicaciones de los algoritmos propuestos 92 el modelo obtenido con el algoritmo BayNet pues es el que peores resultados obtiene en cuanto a verdaderos sanos o normotensos.

Este comportamiento para distintos puntos de corte para realizar esta predicción se aprecia en la Tabla 3.14. A medida que se disminuye el punto de corte se reducen los falsos negativos de treinta casos a cinco. La exactitud en la clasificación se mantiene alta.

Tabla 3.14. Resultados de HTA cuando se reducen casos falsos negativos Los resultados obtenidos para este problema de predicción HTA son suficientemente buenos, tanto con los algoritmos de aprendizaje estructural de RB que se proponen, como con los algoritmos utilizados en la comparación.

Estos resultados consolidan que los algoritmos que se proponen en la tesis muestran desempeño similar a los que se reportan en la literatura ante tareas similares.

Conclusiones parciales del capítulo

Se han aplicado los algoritmos que se describen en el capítulo anterior para el aprendizaje estructural de RB a tres problemas, dos de la Bioinformática y al diagnóstico de la HTA. En todos los casos los resultados son satisfactorios. Los mejores resultados se obtienen con los algoritmos BayesChaid y Bayes PSO.

Para cada una de las aplicaciones se hace un análisis de cómo mejorar los resultados del clasificador en función del dominio de la aplicación que se desarrolla. Para el caso de la predicción de interacciones de proteínas se trata de balancear los resultados de la

Capítulo III. Aplicaciones de los algoritmos propuestos 93 clasificación, cuando se clasifican sitios de splice sites se trata de reducir los falsos positivos, y cuando se diagnóstica la HTA se reducen los falsos sanos.

Se muestra para cada aplicación un ejemplo de cómo utilizar un modelo de RB y así mostrar la generalidad en las posibilidades del uso de las mismas.

Teniendo en cuenta la factibilidad de los resultados, se sugiere que los algoritmos propuestos se pueden usar en otros campos de aplicación además de la bioinformática y la medicina.

CONCLUSIONES Y RECOMENDACIONES Como resultado de esta investigación, se arriba a las siguientes conclusiones: 1. Se propone un algoritmo de aprendizaje estructural de RB basado en árboles de decisión con la técnica CHAID al que se le llamó ByNet. Este algoritmo reporta los mejores resultados en dominios Biomédicos, pero se puede utilizar en dominios de la Bioinformática, pues permite tener en el modelo subgrupos de variables interrelacionadas entre sí y con la variable dependiente o clase. 2. Se presenta un algoritmo de aprendizaje de la estructura de RB al que se le llamó BayesChaid, que utiliza la técnica CHAID, pero no construye árboles de decisión, sino que primero selecciona las variables más relacionadas con la variable dependiente, y a su vez analiza la relación entre las variables predictoras hasta un nivel en profundidad que especifica el usuario, lo cual mejora el resultado anterior. 3. Se presenta un algoritmo para la búsqueda de la estructura de una RB, que denominamos BayesPSO y que se basa en optimización inspirada en modelos de inteligencia colectiva, específicamente la optimización de enjambre de partículas. Este algoritmo garantiza buenas soluciones porque es más exhaustivo en la búsqueda de la estructura 4. Se logra la implementación de los algoritmos propuestos y se añaden a la plataforma de aprendizaje automático Weka, donde se incorporan como nuevos clasificadores bayesianos. Se implementaron además en versiones que permiten la paralelización de las validaciones cruzadas. La adición a Weka de los nuevos clasificadores propició la validación de los algoritmos propuestos en el contexto de otros reportados en la literatura. Los algoritmos BayesChaid y BayesPSO muestran mejores resultados que el algoritmo ByNet en los problemas resueltos en la tesis. De manera general los tres algoritmos se pueden utilizar en dominios Bioinformáticos, de hecho la semántica de las RB se presta para este tipo de dominio del conocimiento, en el que se tienen grandes volúmenes de datos, caracterizado por datos ruidosos y sujetos a errores. La incertidumbre de estos datos, hace que el uso de las RB resulte apropiado, pues estas ofrecen ventajas en el análisis de este tipo de datos sobre otros métodos estadísticos convencionales y de la IA.

Conclusiones y Recomendaciones 95 5. Los algoritmos desarrollados se aplicaron satisfactoriamente a la solución de los problemas de análisis de secuencia siguientes: predicción de interacciones de proteínas en la Arabidopsis thaliana y clasificación de verdaderos y falsos donors y/o acceptors en un problema de localización de splice sites. Los resultados obtenidos en ambas aplicaciones resultan acordes a los que se obtienen por otras técnicas clásicas de aprendizaje de RB, de estadística y de IA y pueden combinarse con estos para obtener soluciones más plausibles de estos problemas. Los algoritmos propuestos se aplicaron también a un problema de diagnóstico de la HTA, lo que demuestra que los algoritmos se pueden aplicar de modo general para la búsqueda de la estructura de una RB desde datos.

Los resultados obtenidos de ninguna forma agotan el desarrollo ulterior de esta temática. Estos, al igual que los resultados de cualquier desarrollo teórico, constituyen las bases para nuevas líneas de investigación. A continuación se enumeran algunos temas que pudieran ser fuentes de trabajos futuros a manera de recomendaciones:

1. Realizar un análisis de los algoritmos propuestos para determinar si es posible obtener versiones paralelizadas. Ello aumentaría notablemente las posibilidades de aplicación en dominios Bioinformáticos.

2. Incorporar los nuevos clasificadores a los sistemas multiclasificadores que se elaboran en el grupo de Bioinformática con el objetivo de ganar en los resultados de los problemas analizados o en nuevos problemas Bioinformáticos.

3. Analizar la posible aplicación de otros algoritmos bioinspirados, como el de colonia de hormigas o bandadas de insectos a la creación de nuevos métodos para el aprendizaje estructural en RB.

REFERENCIAS BIBLIOGRÁFICAS Acid, S. y De Campos, L. M. (2003). Searching for Bayesian Network Structures in the Space Restricted Acyclic Partially Directed Graphs. Artificial Intelligence Research 18: 445- 490. Acid, S., De Campos, L. M. y Castellanos, J. G. (2005). Learning Bayesian Network Classifiers: Searching in a Space of Partially Directed Acyclic Graphs. Machine Learning 59(3): 213 – 235 Arboláez, A. (2008). Extensiones a Weka-Parallel con distintos algoritmos de aprendizaje en redes bayesianas. Aplicaciones Bioinformáticas. Trabajo de Diploma. Tutores: Chávez, M.C., Casas, G., Departamento Ciencia de la Computación, UCLV, Cuba. Armañanzas, R., Inza, I., Santana, R., Saeys, Y., Flores, J. L., Lozano, J. A., Van de Peer, Y., Blanco, R., Robles, V. y Larrañaga, P. (2008). A review of estimation of distribution algorithms in bioinformatics. BioData Min. . Asthana, S., King, O. D., Gibbons, F. D. y Roth, F. P. (2007). Predicting Protein Complex Membership Using Probabilistic Network Reliability. Cold Spring Harbor Laboratory Press. Asuncion, A. y Newman, D. J. (2007). UCI Machine Learning Repository. http://www.ics.uci.edu/~mlearnmlrepository.htm. Aytug, H. (2000). Decision Tree Induction. University of Florida. Baldi, P. y Soren, B. (2001). Bioinformatics: The machine learning approach. 2nd Ed., Massachusetts Institute of Technology: MIT Press: 365-369. Beielstein, T., Parsopoulos, K. E. y Vrahatis, M. N. (2002). Tuning PSO parameters through sensitivity analysis. Technical Report of the Collaborative Research Center, University of Dortmund: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.12.6598. Benet, M., Apollinaire, J. J. y Peraza, S. (2003). Cardiovascular Risk Factors among Individuals under Age 40 with Normal Blood Pressure. Revista Española de Salud Pública 77(1): 143-150. Benet, M., Yanes, A. J., González, J., Apollinaire, A. y García, J. (2001). Criterios diagnósticos de la prueba del peso sostenido en la detección de pacientes con hipertensión arterial. Medicina Clinica 116(17): 645-648. Benson, D. A., Karsch-Mizrachi, I., J., L. D., Ostell, O. y Wheeler, D. L. (2005). GenBank. Nucleic Acids Research 33. Billingsley, P. (1995). Probability and Measure., 3ra. Edic. John Wiley and Sons, New York. Bouckaert, R. R. (1995). Bayesian Belief Networks: From Construction to Inference. Promotor: Prof. Dr. J. Van Leeuwen, Co-promotor: Dr. L.C. Van der Gaag, Faculteit Wiskunde en Informatica, Utrecht University. Bouckaert, R. R. (2007). Bayesian Network Classifiers in Weka for Version 3-5-7. http://www.cs.waikato.ac.nz/~remco/weka_bn/. Brender, J., Talmon, J., Egmont-Petersen, M. y McNair, P. (1994). Measuring quality of medical knowledge. Medical Informatics in Europe Lisbon. Buntine, W. L. (1994). Operation for Learning with Graphical Models. Artificial Intelligence Research 2: 159- 225

Referencias Bibliográficas 97 Buntine, W. L. (1995). Graphical Models for Discovery Knowledge and Data Mining. International Conference on Discovery Science, LNCS 2534(5): 2-11. Buntine, W. L. (1996). A guide to literarture on learning graphical models. IEEE Transactions and Knowledge Data Engeniering. 8, 195- 210. Caballero, Y. (2007). Aplicación de la Teoría de los conjuntos aproximados en el preprocesamiento de los conjuntos de entrenamiento para los algoritmos de aprendizaje automatizado. Tesis en opción del grado de Doctor en Ciencias Técnicas, Universidad Central "Marta Abreu" de Las Villas, Cuba Tutor: Dr. Rafael Bello. Cai, D., Delcher, A., Kao, B. y Kasif, F. (2000). Modeling splice sites with Bayes network. Bioinformatics 16(2): 152- 158. Castillo, E., Gutiérrez, J. M. y Hadi, A. S. (1997). Expert Systems and Probabilistic Network Models,, Springer-Verlag, New York. Charles River Analytics, I. (2004). About Bayesian Belief Networks. Charles River Laboratories International Inc.: http://www.cra.com/commercial-solutions/belief- network-modeling.asp. Chávez, M. C. y Rodríguez, L. O. (2002). Bayshell, Software para crear redes Bayesianas e inferir evidencias en la misma. Copyright Chávez, M. C., Grau, R. y García, M. M. (1999). Un método para construir Redes Bayesianas. Revista Facultad de Ingenieria 19: 76-84 Chávez, M. C., Grau, R. y Sánchez, R. (2005). Construcción de árboles filogenéticos a partir de secuencias de ADN y su integración en una red bayesiana. Memorias de la XI Convención Expo Internacional de Informática, INFORMÁTICA 2005, La Habana, Cuba ISBN: 978-959-716-487-6. Chávez, M. C., Casas, G., González, E. y Grau, R. (2007a). BYNET Herramienta computacional para aprendizaje e inferencias de redes bayesianas en aplicaciones Bioinformáticas. Memorias de la XII Convención y Expo Internacional de Informática, INFORMÁTICA 2007, La Habana, Cuba, ISBN:978-959-286-002-5. Chávez, M. C., Casas, G., Bello, R. y Grau, R. (2008a). Modelo de red bayesiana para predicción de mutaciones en secuencias de la transcriptasa inversa del VIH usando PSO. Memorias de XIV Congreso Latino-Iberoamericano en Investigación de Operaciones (CLAIO 2008): http://socio.org.co/CLAIO2008. Chávez, M. C., Casas, G., Moya, I. y Grau, R. (2008b). A new Method for Learning Bayesian Networks. Application to Data Splice site Classification. Proceedings of the Second Workshop on Bioinformatics Cuba Flanders IWOBI 2008, Santa Clara, Cuba, 2008 ISBN:978-959-250-394-6. Chávez, M. C., Casas, G., Falcón, R., Moreira, J. L. y Grau, R. (2007b). Building Fine Bayesian Networks Aided by PSO-based Feature Selection. IN: ALEXANDER, G., MORALES, K. & FERNANDO, A. (Eds.) MICAI 2007, LNAI 4827: 441- 451. Chávez, M. C., Silveira, P., Casas, G., Grau, R. y Bello, R. (2007c). Aprendizaje estructural de redes bayesianas utilizando PSO. Memorias en Boletín de la Sociedad Cubana de Matemática, Trabajo IA7, Número Especial en CD de COMPUMAT, Holguín, Cuba 5. Chávez, M. C., Casas, G., Moreira, J., González, E., Bello, R. y Grau, R. (2008c). Uso de redes bayesianas obtenidas mediante Optimización de Enjambre de Partículas para

Referencias Bibliográficas 98 el diagnóstico de la Hipertensión Arterial. Octavo Congreso Internacional de Investigación de Operaciones, Revista Investigación Operacional 30(1): 52-59. Chávez, M. C., Casas, G., Moreira, J., Silveira, P., Moya, I., Bello, R. y Grau, R. (2008d). Predicción de mutaciones en secuencias de la proteína transcriptasa inversa del VIH usando nuevos métodos para Aprendizaje Estructural de Redes Bayesianas. Revista Avances en Sistemas e Informática 4(2): 77-85. Chickering, D. M. (1996). Learning Bayesian networks is NP-complete. . Learning from Data: Artificial Intelligence and Statistics, Springer-Verlag, University of California at Los Angeles: 121-130. Chow, C. y Liu, C. (1968). Approximating discrete probability distribution with dependence trees. IEEE Transactions on Information Theory 114: 462- 467. Christos, A. O. y Valencia, A. (2003). Early bioinformatics: the birth of a discipline – a personal view. Bioinformatics 19(17 ): 2176- 2190. Chuang, J. S. y Roth, D. (2001). Splice Site Prediction Using a Sparse Network of Winnows. Technical Report, University of Illinois, Urbana-Champaign, USA http://portal.acm.org/citation.cfm?id=871219. Cohen, J. (2004). Bioinformatics – An Introduction for Computer Scientists. ACM Computing Surveys 36(2): 122- 158.