Algoritmo ‘Random Walk’ en redes de proteínas

El Random Walk (“paseo aleatorio” en castellano) es un sistema teórico usado en estadística que consiste básicamente en ir tomando decisiones aleatorias en nuestro problema en cuestión cada vez que se requiera. Así dicho parece algo absurdo pero entrando en detalle veremos que es bastante útil para realizar predicciones sobre modelos poco definidos. Ha sido utilizado, por ejemplo, para predecir el camino que sigue una molécula a través de un fluido.

En nuestro caso vamos a centrarnos en los grafos. Un grafo no es más que un conjunto de nodos interconectados entre sí por aristas, las cuales pueden ser dirigidas (tener un sentido, en forma de flecha) o bidireccionales. Para simplificar nuestra explicación y que sea más didáctico vamos a suponer un grafo no dirigido. Cada una de estas aristas puede también tener un peso asociado, es decir, un número que identifica la importancia de esa conexión. De nuevo en nuestro ejemplo utilizaremos aristas equiprobables.

Bien, entrando un poco mas en materia y para que el lector vea la utilidad práctica de todo lo que aquí estoy comentando: grafos, algoritmos estadísticos, etc… Voy a explicar un problema bioinformático sencillo donde aplicarlo.

La base del cuerpo humano (y de todo ser vivo) son las proteínas. Son ellas las que estructuran el organismo y las que lo regulan en todos los niveles. El ADN tiene como función albergar toda la información para la fabricación de las proteínas y por lo tanto para la construcción y funcionamiento de cualquier organismo. Las proteínas, por si solas no son funcionales a nivel global, por lo que requieren de interacciones entre ellas formando asociaciones y grupos que actuan en rutas metabólicas.

Pues bien, podemos construir un esquema de cómo interactúa un grupo de proteínas entre sí representándolas mediante nodos en un grafo y con aristas sus relaciones. Para un estudio más real las aristas deberían estar ponderadas, ya que existen pares de proteínas con una interacción más sólida que otras. Además un grafo de este tipo puede estar compuesto de miles de nodos. No obstante simplificaremos el problema.

Una vez construido el grafo, queremos saber cuales de las proteínas pertenecientes al mismo están implicadas en un determinado proceso biológico: cáncer, crecimiento celular, etc… Para ello tenemos un grupo del cual sabemos a ciencia cierta que sí interviene en el proceso que queremos estudiar, ya que lo hemos comprobado experimentalmente. Sin embargo sospechamos que hay más proteínas de la red implicadas en este proceso, pero como tenemos demasiadas opciones, no sabemos por cual de ellas comenzar a experimentar en el laboratorio. Por cuestiones de tiempo y de costes no podemos probar a ciegas con los cientos de proteínas. Es ahí donde entra nuestro estudio con el ordenador.

Supongamos un caminante que sale desde el nodo que sabemos que SÍ pertenece a nuestro conjunto de proteínas implicadas en el proceso. Y aleatoriamente en cada paso va escogiendo un camino. Y al mismo tiempo, en cada paso, con una probabilidad dada puede volver al origen. Esto último se establece para que el andador no se disperse excesivamente y acabe en un nodo excesivamente lejano desvirtuando el resultado, además de para producir un mayor número de iteraciones en el algoritmo de forma que obtengamos una media estadística. El resultado final será una probabilidad para cada nodo de los del grafo de que el andador haya pasado un tiempo en dicho punto.

A nivel matemático la fórmula del “Random Walk With Restart” es la siguiente: 

Donde p(t+1) es el vector de probabilidades de estar en un nodo determinado en el paso t+1. r es la probabilidad de reiniciar el algoritmo. W es la matriz de adyacencia del grafo. p(t) es el vector de probabilidades en el momento actual. Y p(0) es el vector de probabilidades inicial.

Con todo este programa informático ejecutándose obtendríamos una matriz nxn (siendo n el numero de nodos en nuestro grafo [el número de proteínas en nuestro metabolismo]) donde cada casilla nos da un valor probabilístico de la vinculación de un nodo (x) con otro (y). La matriz resultado no es simétrica. No es igual la probabilidad de x->y que la de y->x. Y esto es sencillo de explicar. Cogiendo el grafo que aparece en esta entrada del blog como ejemplo, no es lo mismo la probabilidad de comenzar en el nodo 6 y acabar en el 4 (100%) que la inversa (33%), por lo tanto, este sistema estadístico nos da una visión no sólo de la lejanía de los nodos sino también de la topología de la red. Y nos permite aplicandolo a la Biología una gran capacidad de predicción a nivel de proteínas/genes implicados en determinadas enferemedades, simplemente conociendo la red de interacciones de proteínas y el punto de partida (proteínas que experimentalmente sí hemos demostrado que intervienen en dicha enfermedad). Tras el uso de nuestro sistema bioinformático podremos realizar un ranking con los potenciales genes implicados, de forma que facilitamos muchísimo la vida a nuestros colegas del lado húmedo, acotándoles la cantidad de experimentación a llevar a cabo.

Para más información al respecto se puede leer el paper de köhler:  Walking the Interactome for Prioritization of Candidate Disease Genes

Y si alguien quiere un ejemplo de implementación de este tipo de algoritmos (los dispongo en C++, MatLab y Python) que no dude en contactar conmigo.

Anuncios

2 pensamientos en “Algoritmo ‘Random Walk’ en redes de proteínas

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s