1. Introdução

Em geral, redes ou grafos (forma matemática de representar uma rede) são usados ​​para capturar relacionamentos entre entidades ou objetos. Em uma representação típica, um grafo é composto por um conjunto de vértices/nós , conectados por arestas/linhas/links/setas. Exemplos de redes com as quais interagimos na vida cotidiana incluem a rede elétrica, mapas rodoviários, a world wide web, a internet, conexões aéreas, redes de citações e idiomas, canais de telecomunicações, redes sociais, entre outros. A teoria dos grafos tem sido o campo matemático estabelecido para o estudo e a análise de tais redes, e é aplicável a uma ampla variedade de disciplinas, desde matemática, física, ciência da computação, engenharia e sociologia até biologia e medicina. No campo biomédico, por exemplo, muitas redes biológicas consistem em moléculas como DNA, RNA, proteínas e metabólitos, e grafos podem ser usados ​​para capturar as interações entre essas moléculas. Portanto, é imprescindível conhecer os diversos tipos de redes que podem ser utilizadas para poder comunicar e visualizar tais interações.

Começando com as noções básicas, em matemática, um conjunto A = {a1, a2, a3, ... an} é uma coleção de objetos a1, a2, a3, ... an, enquanto um grafo G = (V, E) é composto por um conjunto de vértices V e um conjunto de arestas E. Um subgrafo G′ = (V′, E′) do grafo G = (V, E) é um grafo onde V′ é um subconjunto de V e E′ um subconjunto de E. Embora um grafo possa ter várias representações, dois grafos diferentes podem ser isomórficos se contiverem o mesmo número de vértices conectados da mesma maneira.

O grafo abaixo possui V={1,2,4,5,6} e E={ (4,6); (4,5); (4,3); (2,5); (2,3); (1,5); (1,2) }.

2. Categorias de grafos

Existem várias categorias de grafos. Os mais conhecidos são não direcionados, direcionados, ponderados, bipartidos, multiarestas, hipergrafos e árvores.

Um grafo é não direcionado (undirected) se houver uma única conexão definida como E = {(i, j)| i, j ∈ V} entre os vértices i e j. Nesse caso, os vértices i e j são chamados de vizinhos diretos (por exemplo, rede de coexpressão de genes).

Um grafo é chamado de direcionado (directed) se uma aresta entre os vértices i e j é representada por uma seta, indicando assim uma direção do vértice i para o vértice j ou vice-versa. Um grafo direcionado é definido como um triplo ordenado G = (V, E, f) onde f é uma função que mapeia cada elemento no conjunto E para um par ordenado de vértices em V (por exemplo, via).

Um grafo ponderado (weighted) definido como um grafo onde E é um conjunto de arestas entre os vértices i e j (E = {(i, j) | i, j ∈ V}) associado a uma função de peso w: E → R, onde R denota o conjunto de todos os números reais. Na maioria das vezes, o peso wij da aresta entre os nós i e j representa a relevância da conexão (por exemplo, rede PPI ou de co-expressão).

Um grafo bipartido é um grafo não direcionado G = (V, E) no qual os vértices em V podem ser particionados em dois conjuntos V′ e V″, de modo que (i, j) ∈ E implica (i ∈ V′ e j ∈ V″) Ou (j ∈ V′ e i ∈ V″) (por exemplo, redes de doenças genéticas). Em outras palavras, qualquer vértice do conjunto V′ pode ser conectado a qualquer outro vértice do conjunto V″, mas nenhuma aresta entre vértices dentro do mesmo conjunto (V′ ou V″) é permitida.

Um grafo é chamado de múltiplas arestas se contiver arestas múltiplas ou arestas paralelas que incidem nos mesmos dois vértices (por exemplo, redes de conhecimento/integração). Um grafo simples, por exemplo, não possui arestas múltiplas.

Um hipergrafo consiste em um conjunto de vértices V e em um conjunto de hiperarestas E, onde uma aresta pode unir qualquer número de vértices (por exemplo, redes bioquímicas).

Uma árvore é um grafo não direcionado no qual quaisquer dois vértices estão conectados por exatamente um caminho ou, de forma equivalente, um grafo não direcionado acíclico conectado (por exemplo, ontologias, filogenias).

Um grafo é conectado se houver um caminho de qualquer ponto a qualquer outro ponto no grafo. Em um grafo completo, cada par de vértices distintos é conectado por uma aresta única.

Um cluster é um grafo formado a partir da união disjunta de grafos completos, e um clique em um grafo não direcionado é um subconjunto de vértices tal que cada par de vértices no clique está conectado.

3. Propriedades gerais

3.1 Degree

Definimos Degree (grau) como o número total de arestas adjacentes a um vértice. No caso de um grafo direcionado, distinguimos entre o “indegree” (deg-in) e o “outdegree” (deg-out). O indegree refere-se ao número de arestas incidentes a partir do vértice, enquanto o outdegree ao número de arestas incidentes ao vértice. Em uma rede social, por exemplo, o indegree representaria os seguidores, enquanto o outdegree representaria as pessoas que se segue. O degree total em um grafo direcionado é a soma do grau indegree e outdegree deg_i = deg-in_i + deg-out_i mostrando todas as conexões (tanto seguidores quanto pessoas seguidas). O grau médio da rede é deg-avg = Σdeg_i / |V|.

Olhando para todos os nós em uma rede, a fim de estudar a distribuição de graus p(k), consideramos a probabilidade de que um vértice selecionado aleatoriamente tenha grau igual a k. A mesma informação também pode ser encontrada como distribuição cumulativa de graus pc(k) que mostra a probabilidade a posterior de um vértice selecionado aleatoriamente ter um grau maior do que k. Notavelmente, a distribuição de graus é uma das características topológicas mais importantes e é característica de diferentes tipos de rede. No caso mais simples, p(k) pode ser estimado por um histograma de graus. As redes, cuja distribuição de graus segue uma lei de potência, são chamadas de redes sem escala (scale-free).

3.2 Densidade

Densidade é a razão entre o número de arestas em um grafo e o número de arestas possíveis no mesmo grafo. Em um grafo totalmente conectado (por exemplo, complexo de proteína), o número de arestas possíveis (conexões de pares) é Emax = V(V − 1)/2. Portanto, a densidade pode ser calculada como: densidade = E/Emax = 2E/V(V − 1). Se um grafo tem E ≃ V^k, 1<k<2, então esse grafo é considerado denso, enquanto que quando um grafo tem E ≃ V ou E ≃ V^k, k ≤ 1, ele é considerado esparso. (Aqui o simbolo ^ representa elevado).

3.3 Coeficiente de clusterização

O coeficiente de clusterização (Clustering coefficient) é uma medida que mostra se uma rede ou um nó tem a tendência de formar clusters ou comunidades fortemente conectadas (por exemplo, clusters de proteínas em uma rede de interação proteína-proteína). O coeficiente de clusterização de um nó é definido como o número de arestas entre seus vizinhos dividido pelo número de conexões possíveis entre esses vizinhos. O coeficiente de clusterização de um nó i é definido como Ci = 2e/k(k − 1), onde k é o número de vizinhos (degree) e e o número de arestas entre esses k vizinhos. O clustering médio de uma rede é dado por Cavg = ΣCi/|V|. O coeficiente de clusterização assume valores 0 ≤ Ci ≤ 1, portanto, quanto mais próximo de 1, maior a tendência de formação de clusters.

3.4 Shortest path

A distância dist_ij entre dois nós (por exemplo, metabólitos em uma rede metabólica) é definida como o comprimento do caminho mais curto (shortest path) entre eles. O caminho mais curto é definido como o número mínimo de arestas que precisam ser percorridas para alcançar o nó j a partir do nó i. No caso de existirem dois caminhos mais curtos de comprimento idêntico, qualquer um deles pode ser usado. Sempre que não houver conexão entre dois nós i e j, sua distância é definida como dist_ij = ∞. Além disso, o diâmetro, diametro = max(dist_ij), é a distância máxima entre qualquer par de vértices. O comprimento médio do caminho é definido como a distância média entre todos os pares de nós e é definido como dist_avg = 1/N(N − 1) ∑ N_i ∑ N_j dist_ij.

4. Centralidades de rede

Muitas vezes, na análise de rede, fazemos perguntas como: qual é o nó mais importante, qual nó se comporta como um hub (nó de grande importância e que faz muitas conexões), qual nó é a ponte entre duas comunidades diferentes, qual nó é importante para a robustez da rede (tolerância a falhas e perturbações), etc. Para responder a essas questões, várias centralidades de rede podem ser usadas.

4.1 degree centrality

O grau de centralidade (degree centrality) é uma medida para destacar nós altamente conectados (por exemplo, fatores de transcrição centrais). Uma rede com topologia em estrela, por exemplo, contém hubs que são nós centrais com muitos vizinhos ao seu redor. O grau de centralidade de um nó i é calculado como Ci = deg(i) onde deg(i) é o grau (degree) do nó.

Você pode executar um histograma do degree da sua rede e ponderar sobre as conexões prevalentes na sua rede.

4.2 closeness centrality

Da mesma forma, a centralidade de proximidade (closeness centrality) é uma medida para detectar nós importantes que podem se comunicar rapidamente com outros nós de uma rede. Para um grafo G = (V, E) é definido como C_clo = 1/∑dist_ij ou como C_clo = N − 1/∑dist_ij em sua forma normalizada. Em redes bioquímicas, é frequentemente usado para encontrar os principais metabólitos [por exemplo, metabólitos em E. coli como parte da glicólise e das vias do ciclo do ácido citrato].

4.3 betweenness centrality

A centralidade de intermediação (betweenness centrality) mostra os nós que formam tais pontes para que duas comunidades possam se comunicar entre si. É calculado como C_bet(i) = σxy(i)/σxy onde σxy é o número total de caminhos mais curtos do nó x ao nó y e σxy(i) é o número daqueles caminhos que passam pelo nó i. Foi demonstrado que proteínas com alta centralidade de intermediação em uma rede de interação proteína-proteína (PPI) desempenham um papel importante para a modularização da rede (Koschützki e Schreiber, 2008).

4.4 eccentricity centrality

A centralidade de excentricidade (eccentricity centrality) mostra como um vértice é facilmente acessível a partir de qualquer outro vértice da rede. A excentricidade é a distância máxima do grafo entre o vértice i e qualquer outro vértice j no grafo G. Para um grafo desconectado, todos os vértices são definidos como tendo excentricidade infinita. A centralidade da excentricidade é calculada como C_ecc = 1/max(dist_ij). A centralidade de excentricidade tem sido usada para detectar proteínas essenciais em um PPI.

Notavelmente, a excentricidade máxima é chamada de diâmetro do grafo, enquanto a excentricidade mínima do grafo é chamada de raio.

5. Redes de interação proteína-proteína (PPIs)

Este tipo de rede contém informações sobre como diferentes proteínas operam entre si para permitir um processo biológico dentro de uma célula. As interações em uma rede PPI podem ser físicas ou previstas. Notavelmente, um interactoma inteiro pode capturar todos os PPIs que acontecem em uma célula ou organismo. Os métodos in vivo e in vitro para a detecção de PPIs incluem: cristalografia de raios-X, NMR, purificação de afinidade em tandem (TAP), cromatografia de afinidade, coimmunoprecipitação, matrizes de proteínas, complementação de fragmentos de proteínas, exibição de fagos e dois híbridos de levedura (Y2H). Repositórios amplamente usados que hospedam PPIs para vários organismos são o BioGRID, MINT, BIND, DIP, IntAct, STRING e banco de dados HPRD.

Com relação à topologia, as redes PPI seguem uma propriedade de mundo pequeno e são redes sem escala. Os hubs centrais muitas vezes representam proteínas conservadas evolutivamente, enquanto os cliques (subgrafos totalmente conectados) têm um alto significado funcional.

Referências

Koschützki, D., & Schreiber, F. (2008). Centrality analysis methods for biological networks and their application to gene regulatory networks. Gene regulation and systems biology, 2, GRSB-S702.

Koutrouli, M., Karatzas, E., Paez-Espino, D., & Pavlopoulos, G. A. (2020). A guide to conquer the biological network era using graph theory. Frontiers in bioengineering and biotechnology, 8, 34.