PDF de programación - Modelos de Redes Bayesianas en el estudio de secuencias genómicas y otros problemas Biomédicos

UNIVERSIDAD CENTRAL “MARTA ABREU” DE LAS VILLAS

FACULTAD DE MATEMÁTICA, FÍSICA Y COMPUTACIÓN

DEPARTAMENTO DE CIENCIA DE LA COMPUTACIÓN



MODELOS DE REDES BAYESIANAS EN EL ESTUDIO DE SECUENCIAS

GENÓMICAS Y OTROS PROBLEMAS BIOMÉDICOS



Monografía



MSc. María del Carmen Chávez Cárdenas
Dr. Ricardo Grau Ábalo
Dra. Gladys Casas Cardoso



Santa Clara, 2008





“Vivir es el arte de derivar conclusiones suficientes de premisas insuficientes”

S. Butler

SÍNTESIS

Este trabajo está relacionado con problemas de análisis de regiones genómicas codificantes
para proteínas utilizando un tipo de modelo gráfico-probabilístico: las redes bayesianas.
Las posibilidades del uso de las redes bayesianas se fortalece si se realiza el aprendizaje de
las mejores estructuras y parámetros. En el trabajo se presentan tres nuevos algoritmos para
el aprendizaje estructural desde datos. Dos de estos algoritmos obtienen la estructura de
dependencias basándose en la detección de interacciones al estilo del algoritmo CHAID
(Chi-square Automatic Interaction Detector).

El tercero de estos algoritmos se basa en un método de optimización bioinspirado,
concretamente la optimización basada en enjambres de partículas (Particle Swarm
Optimization, PSO) para contribuir a la reducción de atributos.

En la validación de estos algoritmos se han utilizado 18 archivos de datos del repositorio de
aprendizaje automatizado, así como otros enfoques alternativos para el aprendizaje de la
estructura de redes bayesianas, reportados anteriormente; cuyos resultados demuestran la
validez de los modelos propuestos. Además se desarrollaron tres aplicaciones que
responden a problemas reales de distintas áreas.

Los dos primeros problemas pertenecen al área de la Bioinformática, la primera aplicación
es sobre la predicción de interacciones de proteínas y la segunda sobre predicción de sitios
de splicing en regiones genómicas codificantes para proteínas. Para concluir se presenta
una aplicación sobre un tema médico bien conocido: el diagnóstico de la hipertensión
arterial.

ABSTRACT

The current thesis is concerned with the analysis of coding regions for proteins by using a
type of graph-probabilistic model: Bayesian networks. The capabilities of the Bayesian
networks are significantly enhanced as long as the best structures and parameters are
properly learned. This study puts forward three new algorithms for structural learning from
data. Two of them become cognizant about the dependency structure owing to the detection
of the interactions like in the CHAID (Chi-square Automatic Interaction Detection)
algorithm.

The third one of these approaches is anchored on a bio-inspired optimization method, i.e.
the optimization driven by swarms of particles (Particle Swarm Optimization, PSO) to help
reduce attributes.

Eighteen widely used data repositories from University of California at Irvine have been
employed in the validation of the aforementioned algorithms, besides considering other
alternative models previously reported in literature. The results attained demonstrate the
feasibility of the proposed methods. In addition, three applications that respond to real
problems in different fields were developed.

The first two problems lie under the umbrella of bioinformatics; the former is concerned
with the prediction of protein interactions whereas the latter has to do with splicing sites
forecasting. Last but not least, an application addressing the well-known problem of
hypertension diagnosis is introduced.



Acrónimos

UCLV: Universidad Central “Marta Abreu” de Las Villas

CEI: Centro de Estudios de Informática

INIVIT: Instituto de Investigaciones de Viandas Tropicales

IA: Inteligencia Artificial, del inglés Artificial Intelligence

IBP: Instituto de Biotecnología de las Plantas

RB: Redes Bayesianas, del inglés Bayesian Networks

ADN: Ácido Desoxirribonucleico

ARN: Ácido Ribonucleico

ML: Aprendizaje automático o computarizado, del inglés Machine Learning

GDA: Grafo Dirigido Acíclico, del inglés Directed Acyclic Graph

BLAST: Herramienta de búsqueda de regiones similares entre secuencias biológicas, del
inglés Basic Local Alignment Search Tool

FASTA: Sistema para comparar nucleótidos o proteínas, del inglés FAST-All

CHAID: Detector automático de interacciones Chi-cuadrado, del inglés Chi-square
Automatic Interaction Detector

PSO: optimización basada en enjambres de partículas, del inglés Particle Swarm
Optimization

Weka: plataforma de aprendizaje automatizado, implementada en Java por la Universidad
de Waikato en Nueva Zelanda, del inglés Waikato Environment for Knowledge Analysis

HTA: HiperTensión Arterial

DPC: Distribución de Probabilidad Conjunta

IMC: Información Mutua Condicional

AIC: Criterio de Información de Akaike, del inglés Akaike Information Criterion

MDL: longitud de descripción mínima, del inglés Minimal Description Length

Acrónimos



MNB: Modelo Naïve Bayes o MBN: Modelo Bayesiano Naïve o CNB: Clasificador Naïve
Bayes

TAN: Naïve Bayes aumentado a árbol, del inglés Tree Augmented Naïve Bayes

kDB: clasificador bayesiano con k dependencias, del inglés k Dependence Bayesian
classifier

PC: Constructor eficiente, del inglés Power Constructor

VP: verdaderos positivos, del inglés true positive (TP)

rVP: razón de VP, del inglés true positive rate

FP: falsos positivos, del inglés false positive (FP)

rFP: razón de FP, del inglés false positive rate

VN: verdaderos negativos, del inglés true negative (TN)

rVN: razón de VN, del inglés true negative rate

FN: falsos negativos, del inglés false negative (FN)

rFN: razón de FN, del inglés false negative rate

ROC: Curva de operación del receptor, del inglés Receiving Operation Curve

UCI: Universidad de California Irvine

UCIML: Bases de datos del repositorio de aprendizaje automático, del inglés UCI
Repository of Machine-Learning Databases

EDAs: algoritmos de estimación de distribuciones, del inglés Estimation of distribution
algorithms

GO: genes ontólogos, del ingles Gene Ontology

AUC: área bajo la curva ROC, del inglés, Area under the Receiving Operation
Characteristic Curve

AD: Árbol de Decisión, del inglés Decision Tree

LOO-CV: validación cruzada dejando uno fuera, del inglés Leave one out crossvalidation



TABLA DE CONTENIDOS

1.1.2

1.1.2.1
1.1.2.2

1.1.1.1
1.1.1.2

INTRODUCCIÓN..................................................................................................................1
1. LAS REDES BAYESIANAS Y LA BIOINFORMÁTICA .........................................11
Redes Bayesianas ........................................................................................................... 11
1.1.1 Aprendizaje en Redes Bayesianas............................................................................................. 13
Aprendizaje estructural de Redes Bayesianas ................................................................. 13
Aprendizaje paramétrico de Redes Bayesianas ............................................................... 21
Propagación en Redes Bayesianas ............................................................................................ 24
Propagación en árboles de unión..................................................................................... 25
Algoritmo de propagación mediante la eliminación de variables.................................... 28
Las Redes Bayesianas como clasificadores .............................................................................. 29
Necesidad de la reduccion de atributos en algunos casos................................................ 31
Optimización de enjambres de partículas........................................................................ 32
Evaluación de las Redes Bayesianas como clasificadores............................................... 34
Productos de software para Redes Bayesianas......................................................................... 36
Aplicaciones de las Redes Bayesianas en Bioinformática ......................................... 37
Estudio de secuencias genómicas.............................................................................................. 38
Problemas bioinformáticos que se resuelven mediante Redes Bayesianas ............................... 39
Consideraciones finales del capítulo ............................................................................ 41

1.1.3.1
1.1.3.2
1.1.3.3

1.2.1
1.2.2

1.1.3

1.1.4

1.2

1.1

1.3

2. NUEVOS ALGORITMOS DE APRENDIZAJE ESTRUCTURAL DE REDES
BAYESIANAS......................................................................................................................42
Aprendizaje Estructural de Redes Bayesianas basado en técnicas estadísticas....... 42

2.1

2.1.1.1
2.1.1.2
2.1.1.3

2.1.1 Aprendizaje Estructural de Redes Bayesianas basado en árboles de decisión obtenidos con el
algoritmo CHAID.................................................................................................................................... 44
Fundamentos generales del Algoritmo ............................................................................ 44
Algoritmo ByNet............................................................................................................. 47
Algunas consideraciones sobre el algoritmo ByNet........................................................ 48
2.1.2 Aprendizaje Estructural de Redes Bayesianas basado en el algoritmo CHAID........................ 49
Fundamentos general