Algoritmos Métodos basados en grafos

Carlos Aguirre Maeso [email protected] Escuela Politécnica Superior Universidad Autónoma de Madrid

Introducción.


La teoría de grafos ha sido utilizada recientemente para: • • • •

Clasificación automática de secuencias de proteínas. Detección de jerarquías de proteínas. Análisis de redes genéticas. Reconstrucción de redes genéticas grandes obtenidas mediante modificación de genes.

Teoría de grafos.


Un grafo G es un par de conjuntos (V,E) • V={v1,v2,....vn} es el conjunto de vértices • E={(vi,vj),(vi’,vj’)......} es un conjunto de pares no ordenados de elementos de V. • E se denomina conjunto de ramas del grafo • El numero de nodos se denomina orden del grafo. • El número de ramas se denomina tamaño del grafo.

Ejemplo de grafo (Orden 8 y tamaño 11). v2

v4

v6

v1

v8 v3

v5

v7

V={v1,v2,v3,v4,v5,v6,v7,v8} E={(v1,v2),(v1,v3),(v2,v4),(v3,v5),(v4,v6), (v5,v7),(v6,v8),(v7,v8),(v2,v5),(v4,v5),(v6,v7)}

Bucles y ramas paralelas.


Un bucle es una rama que empieza y termina en el mismo nodo (vi,vi).
Cuando dos ramas conectan el mismo par de vértices se denominan paralelas.
Un grafo con bucles se denomina pseudografo.
Un grafo con ramas paralelas pero sin bucles se denomina multigrafo.
Un grafo sin bucles ni ramas paralelas se denomina grafo simple.

Bucles y ramas paralelas. Ramas paralelas

v2

v4

v6

v1 Bucle

v8 v3

v5

v7

Grafos dirigidos.
Se puede considerar que los enlaces entre nodos son dirigidos (vi,vj) = (vj,vi).
Los grafos dirigidos se denominan también digrafos. v2

v4

v6

v1

v8 v3

v5

v7

Grafos ponderados.
A cada rama del grafo se le puede asociar un número.
El número asociado a cada rama puede indicar entre otras cosas una distancia, una capacidad, un valor temporal, etc… v2 v1

1

v4

5

v6 7

2

9

12 4

v3

10

v5

v8

2

6

v7

-1

Grafos dirigidos y ponderados.
Los grafos dirigidos y ponderados poseen ramas dirigidas a las que se asocia un número.

v2 v1

1

v4

5

v6 7

2

9

12 4

v3

10

v5

v8

2

6

v7

-1

Grado de un nodo.


Dos nodos de un grafo son vecinos o adyacentes si existe una rama que los conecta.
El grado de un nodo es el número vecinos que tiene dicho nodo.
En los grafos dirigidos se calcula el grado de entrada y el grado de salida.
En los grafos ponderados, el grado se puede promediar por el número asociado a las ramas.
Un grafo se dice que es regular si todos los nodos tienen el mismo grado.

Grado del nodo V2. Grado 3

v2

v4

v6

v1 Grado de salida 1

Grado de entrada 2

v8

v2

v3

v5

v4

v7

v6

v1

v8 v3

v5

v7

Subgrafos.


Un grafo G’=(V’,E’) es un sugrafo de un grafo G=(V,E) si V’ es un subconjunto de V y E’ es un subconjunto de E..

G

v2

v4

v6

v1

G’

v2

v6

v8 v3

v5

v7

v8 v3

v5

v7

Subgrafos.
Un subgrafo G’=(V’,E’) de un grafo G=(V,E) se dice que es abarcador si V=V’.

G

v2

v4

v2

v6

v1

v8 v3

v5

v7

G’

v4

v6

v1

v8 v3

v5

v7

Paseos, caminos, circuitos y ciclos.


Un paseo de un nodo u a un nodo v es una secuencia de vértices {v0,v1,....vk} con v1=u vk=v y (vi-1,vi) rama del grafo.
El número de ramas del paseo es su longitud.
Un paseo en el cual no se repiten ramas se denomina rastro.
Un paseo en el cual todos los vertices {v0,v1,....vk} son distintos se denomina camino.
Un camino mínimo entre dos nodos es aquel de menor longitud de entre todos los posibles caminos entre ambos nodos.

v2

Paseo

v4

v6

v1

v8 v3

v5

v7

v4

v6

C={v1,v2,v5,v3,v1,v2,v4,v6,v7,v8} v2

Rastro v1

k=9

v8 v3

v5

v7

C={v1,v3,v5,v2,v4,v5,v7,v8}

k=7

v2

Camino

v4

v6

v1

v8 v3

v5

v7

v4

v6

C={v1,v2,v5,v4,v6,v7,v8} Camino mínimo

v2

k=6

v1

v8 v3

v5

C={v1,v2,v4,v6,v8}

v7

k=4

Paseos, caminos, circuitos y ciclos.


Un paseo cerrado es un paseo {v0,v1,....vk} tal que v0=vk.
Un paseo cerrado en el que no se repiten ramas es un circuito.
Un ciclo es un circuito en el que no se repiten vértices.

Paseos, caminos, circuitos y ciclos.

v2

Ciclo

v4

v6

v1

v8 v3

v5

v7

C={v1,v2,v4,v6,v8,v7,v5,v3,v1}

k=7

Conexidad.
Un grafo es conexo si para cada par de nodos del grafo existe al menos un camino que los une. Grafo conexo v1

Grafo no conexo

v2

v1

v2

v5 v3

v4

v5 v3

v4

Conexidad.
Una componente conexa de un grafo es cada uno de los subgrafos maximales conexos Componentes conexas v1

v2 v5

v3

v4

Conexidad.
Un punto de articulación es un nodo que desconecta un grafo conexo.
Un corte es un conjunto de ramas que desconecta un grafo conexo,
Si un corte esta compuesto por una única rama, se denomina puente.
Un corte mínimo de un grafo es el mínimo número de ramas que al ser eliminadas desconectan el grafo.

Conexidad. v1

v3

Corte

v2

v4

v6

v5

Puente v8

v7

Punto de articulación

Bosques y árboles.
Un grafo sin ciclos (acíclico) se denomina bosque.
Un arbol es un grafo acíclico conexo.
Cada componente conexa de un bosque, es un árbol.

Bosques y árboles.

G

v2

v4

G v5

v6

v1

v8 v3

v5

v7

v7

v3 v1

v2

v8

v4 v6

Bosques y árboles.
Un subgrafo abarcador acíclico de un grafo G se denomina un bosque abarcador.
Un subgrafo abarcador conexo acíclico de un grafo G se denomina un arbol abarcador.

Bosques y árboles.

G

v2

v4

v6

v1

v2 v8

v3

v5

v7

G’

v4

v6

v1

v8 v3

Árbol abarcador

v5

v7

Representación de grafos
Hay dos formas estándar de representar un grafo en un ordenador. • Matriz de adyacencia. • Lista de adyacencia.

v2

v4

v6

v1

v8 v3

Matriz de adyacencia 01100000 10011000 10001000 01001100 01110010 00010011 00001101 00000110

v5

v7 Lista de adyacencia 1 2 3 4 5 6 7 8

2

3

1

4

1

5

2

5

6

2

3

4

4

7

8

5

6

8

6

7

5

7

Matriz de Adyacencia

Lista de adyacencia


Consume mucha memoria.
Fácil de añadir o eliminar ramas
Fácil saber si existe la rama (a,b).
Lento enumerar los vecinos de un nodo.


Consumo limitado de memoria.
Costoso añadir o eliminar ramas.
Costoso saber si existe la rama (a,b).
Rápido enumerar los vecinos de un nodo.

Clasificación de grafos


Los grafos se clasifican en función de unas determinadas métricas topológicas.
Las métricas mas empleadas son: • • • • • •

Tamaño |E| y orden |V| Dispersión (|E|/|V|) Distribución del grado de los nodos Grado medio () Coeficiente de agrupamiento (C) Camino carácteristico (L)

Coeficiente de agrupamiento
El coeficiente de agrupamiento (C) es un valor métrico local que mide el nivel de agrupamiento de los nodos.
Cálculo de C

• Para cada nodo v del grafo se obtiene su vencidario, es decir, el cojunto de nodos que son vecinos de v, el tamaño del vecindario coincide con el grado de v (kv) • Se calcula el coeficiente Nv/(kv(kv-1)) donde Nv es el numero de ramas que hay entre los vecinos de v. • El valor anterior se promedia entre todos los nodos del grafo Cv= 6/(4*3)=1/2

v

Camino característo
El camino característico (L) es un valor métrico global que mide el nivel grado de separacion de los nodos.
Cálculo de C

• Para cada nodo v se calcula la distancia promedio a todos los demas |V| nodos del grafo, Lv= Σk=1d(v,vk)/(|V|-1) • Se calcula|V|el promedio del valor anterior entre todos los nodos del grafo L= Σv=1 Lv /|V| .

Algunas topologias.
Las topologías mas frecuentes son: • • • •

Grafos aleatorios Grafos regulares Mundo pequeño Grafos libres de escala

Grafos aleatorios
Fueron estudiados principalmente por Erdos y Renyi en los años 50.
Cada rama del grafo existe con una determinada probabilidad p.
Erdos y Renyi estudiaron los valores de las metricas topológicas para diferentes valores de $p$.
Para la grafos dispersos (p pequeña) se puede comprobar que tanto C (aproximadamente 0) como L (aproximadamemte Ln(|V|) son pequeños

Grafos Regulares
Son los mejor conocidos de forma analítica
Existen expresiones cerradas para todas las métricas.
Para la grafos dispersos se puede comprobar que tanto C (aprximadamente 0.75) como L (aproximadamente |V|/) son grandes

Mundo pequeño (Watts y Strogatz 1998)
Son grafos que presentan altos valores de C (aprox .8) y bajos valores de L (aprox ln(|V|).
Se obtienen introduciendo pequeño número de “atajos” en un grafo regular
Representan bien un gran número de redes tales como redes sociales.

Libre de escala (Albert y Barabasi 1999)
Son grafos que presentan bajos valores de C (aprox 0) y bajos valores de L (aprox ln(|V|).
Se obtienen mediante crecimiento de la red y enlace preferencial
Cuando la distribución de los nodos se dibuja en escala log-log aparece una línea recta.
Representan bien un gran número de redes tales como internet o redes de reacciones químicas.

Metricas Anillo Regular

125.438

0.643

Mundo Pequeño

14.2

0.626

Libre de escala

3.409

0.0186

Aleatorio

3.89

0.004

|V|=2000

k=8

Algorítmos sobre grafos


El algoritmo de búsqueda en anchura permite calcular un camino mínimo entre dos nodos de un grafo.
Dijkstra es una versión del algoritmo anterior para grafos ponderados.
Ambos algoritmos funcionan tanto en grafos dirigidos como no dirigidos.
Los algoritmos nos permiten calcular las métricas sobre el grafo.

BusquedaAnchura(V,E,s)

Para cada vertice u en V-s

visitado[u]=FALSE, d[u]=infinito,p[u]=NIL

visitado[s]=TRUE,d[s]=0,p[s]=NIL Encueue(Q,s)

While(NoVacia(Q)) u=Head(Q)

para cada v en adj(u)

if visitado[v]=FALSE

d[v]=d[u]+1,p[v]=u Enqueue(Q,v)

visitado[v]=TRUE

Dequeue(Q)

2

U=1

4

1

2

3

4

5

0

i

i

i

i

T

F

F

F

F

p

N

N

N

N

N

Q

1

d visitado

1 3

1 2 3 4 5

5

2

3

1

3

4

1

2

5

2

5

3

4

2

U=1

4

1

d

3

1 2 3 4 5

5

2

3

1

3

4

1

2

5

2

5

3

4

3

4

5

0

1

i

i

i

T

T

F

F

F

p

N

1

N

N

N

Q

1

2

visitado

1

2

2

U=1

4

1

d

1

1 2 3 4 5

5

2

3

1

3

4

1

2

5

2

5

3

4

3

4

5

0

1

1

i

i

T

T

T

F

F

p

N

1

1

N

N

Q

1

2

3

visitado

3

2

2

4

1

d

3

1 2 3 4 5

5

2

3

1

3

4

1

2

5

2

5

3

4

2

3

4

5

0

1

1

2

i

T

T

T

T

F

p

N

1

1

2

N

Q

2

3

visitado

1

1

U=2

2

4

1

d

3

1 2 3 4 5

5

2

3

1

3

4

1

2

5

2

5

3

4

2

3

4

5

0

1

1

2

i

T

T

T

T

F

p

N

1

1

2

N

Q

2

3

4

visitado

1

1

U=2

2

4

1

d

3

1 2 3 4 5

5

2

3

1

3

4

1

2

5

2

5

3

4

2

3

4

5

0

1

1

2

2

T

T

T

T

T

p

N

1

1

2

3

Q

3

4

5

visitado

1

1

U=2

2

4

1

U=3 1

2

3

4

5

0

1

1

2

2

T

T

T

T

T

p

N

1

1

2

3

Q

4

5

d visitado

3

1 2 3 4 5

5

2

3

1

3

4

1

2

5

2

5

3

4

2

4

1

1

d visitado

3

1 2 3 4 5

U=3

5

2

3

1

3

4

1

2

5

2

5

3

4

p Q

2

3

4

5

0

1

1

2

2

T

T

T

T

T

N

1

1

2

3

CLUSTERING-COEFFICIENT(w) 1 n = rows[w] 2 ci = 0 3 for i = 1 to n 4 do neighbor[i]= 0 5 for i = 1 to n 6 do k = 0 7 for j = 1 to n 8 do if W[i][j] = 1 9 then neighbor[k]= j 10 k = k + 1 11 12 realedges = 0 13 for p = 0 to k − 2 14 do for q = p + 1 to k − 1 15 do if w[neighbor[p]][neighbor[q]] = 1 16 then realedges = realedges + 1 17 18 19 totaledges = k(k − 1)/2 20 ci = ci + realedges/totaledges 21 ci = ci/n 22 return ci

DEGREE-DISTRIBUTION(w) 1 n = rows[w] 2 for i = 1 to n 3 do dist[i] = 0 4 for i = 1 to n 5 do numedges = 0 6 for j = 1 to n 7 do if w[i][j] = 1 and i != j 8 then numedges numedges + 1 9 10 distnumedges = distnumedges + 1 11 for i = 1 to n 12 do disti = disti/n 13 return dist


El algoritmo de Búsqueda en profundidad permite calcular puntos de articulación de un grafo.
El algoritmo de Ford-Fulkerson permite calcular cortes mínimos.

Aplicaciones


Las técnicas basadas en grafos se utilizan para el análisis o clasificación de cadenas de datos
La técnica suele consistir en la construcción de un grafo donde los nodos son cada uno de los datos obtenidos y las ramas posibles relaciones entre los datos y la aplicación de algún algoritmo conocido sobre este grafo.

Click


Click (Sharan & Shamir) es un algoritmo de clustering aplicado al análisis de expresiones genéticas (gene expressions).
Click también ha sido utilizado para clustering de conjuntos de datos de proteínas (ProtoMap).


El problema de clustering consiste en partir un conjunto V en k conjuntos disjuntos V1,V2,....Vk tal que la unión de todos ellos es V.
Para comprobar la calidad del clustering se definen dos medidas • Separación entre clusters • Homogeneidad de cada cluster

Click(G)

si V(G)={u}

Añade {u} al conjunto de vertices aislados

si G es un cluster

Añadir G a la lista de clusters

en otro caso

H, H’ = CorteMínimo(G) Click(H)

Click(H)’


Click se ha utilizado para clustering de expresiones genéticas donde cada nodo es una expresión.
Dos nodos se conectan si un coeficiente de similitud entre ambas expresiones genéticas es mayor que un cierto umbral.

Resultados de click cuando se aplica al conjunto de datos de la respuesta de los fibroblastos humanos al suero

ProtoMap


ProtoMap es un proyecto dedicado a la clasificación de secuencias de proteínas y jerarquización de familias de proteínas.
Cada vértice es una secuencia y el peso de cada rama es un coeficiente de similitud entre las proteínas.


Los clusters se obtienen buscando grupos de nodos altamente conectados entre sí.
Los autores aplicaron el método a la base de datos SWISS-PROT.
Los resultados se pueden consultar en http://www.protomap.cs.huji.ac.il

Redes de interacción


Tong et al. analizan redes de interacción de proteínas.
Cada nodo del grafo es una proteína.
Una rama significa una interacción entre ambas proteínas.


Un k-core de un grafo G es un subgrafo G’ tal que el grado de cada nodo de G’ es al menos k.
Este algoritmo produce una jerarquía de subgrafos basandose en el k de los k-cores obtenidos para cada posible k.

Dominio SH3 (|V|=206 |E|=394)

6-Core del dominio SH3

Cliff


Cliff (Xing & Karp) ha sido utilizado para clustering de datos con un número alto de dimensiones.
De nuevo cada nodo es una expresión genética (muy larga) y las ramas un coeficiente de similitud entre nodos.
Cliff usa cortes mínimos y técnicas bayesianas para definir los clusters.