Aprendizaje de clases de equivalencia de redes bayesianas basado en búsqueda competitiva de hormigas artificiales / Learning of bayesian networks equivalence classes based on competitive search of artificial ants

RESUMEN

Este artículo propone un algoritmo de aprendizaje de clases de equivalencia de redes bayesianas basado en un algoritmo de búsqueda Greedy y modelos de búsqueda inspirados en hormigas competitivas. Específicamente para el algoritmo propuesto, se obtuvo una mejor aproximación entre la red predicha y la red bayesiana teórica de ejemplo ASIA, con respecto a algoritmos anteriores, para conjuntos de datos con 20 y 500 muestras. En promedio el algoritmo desarrollado obtuvo una aproximación con respecto a la distancia estructural de hamming de 10.7% y 5.3% menor comparada con la obtenida por los algoritmos Greedy y de colonia de hormigas (ACO-E) respectivamente para 20 muestras, y de hasta el 6.8% menor con respecto al algoritmo ACO-E para 500 muestras. Además, para 500 muestras el número de llamadas a la función de puntaje realizadas por el algoritmo propuesto fue menor que las realizadas por el algoritmo ACO-E en el 90% de las combinaciones, concluyendo que hubo una reducción de la complejidad computacional. Finalmente se presentan los resultados de la aplicación del algoritmo propuesto a un microarreglo obtenido por muestras de pacientes con Leucemia Mieloide Aguda (LMA) con 6 nuevas interacciones con dependencias estadísticas como potenciales interacciones biológicas con alta probabilidad.

ABSTRACT

This article proposes an algorithm for learning equivalence classes of Bayesian networks based on a Greed search algorithm and search patterns inspired by competitive ants. Specifically, for the proposed algorithm, we obtained a better approximation between the predicted network and the theoretical network ASIA with respect to previous algorithms for data sets with 20 and 500 samples. On average, the algorithm developed an approximation with respect to Structural Hamming Distance of 10.7% and 5.3% lower than Greedy algorithms and ACO-E respectively to 20 samples, and up to 6.8% lower tan ACO-E algorithm for 500 samples. Furthermore, for 500 samples the number of calls to the scoring function performed by the algorithm proposed was smaller than in the ACO-E algorithm in 90% of the combinations, concluding that there was a reduction in the computational complexity. Finally, we present the results of applying the proposed algorithm to a microarray samples obtained from patients with acute myeloid leukemia (AML) with 6 new interactions with statistical dependencies as potential biological interactions with high probability.