Problema da clique corrompida: teoria de grafos na análise de clusters de genes

Resumo

Os avanços da biotecnologia permitem pesquisas que medem o nível de expressão de milhões de genes simultaneamente nas diferentes condições e tempo. O gene é um segmento de uma molécula de DNA que contém um código de informações necessárias para a produção de proteínas. Analisar grandes quantidades de genes é uma tarefa difícil, por isso um dos métodos de pesquisa provém da análise e agrupamento dos genes que se manifestam com padrões de expressões similares. Pequenos vetores medem o nível de expressão dos genes em n tempos diferentes. Esses dados são transformados nas matrizes de intensidade que permitem aos biólogos perceber como as funções dos genes podem ser relacionadas. Os dados são representados como pontos no espaço n-dimensional. Calculando-se a distância euclidiana entre cada dois genes, constrói-se uma matriz de distância dos genes (Figura 1). Genes com distâncias pequenas, os quais partilham as mesmas características e podem ser relacionados funcionalmente, são vistos na formação de clusters (grupos). Existem algumas técnicas de análise da formação de clusters, uma delas é baseada na teoria dos grafos. O modelo que estudamos a seguir foi proposto em [1]. Um grafo G(V,E) é um conjunto finito não-vazio V e um conjunto E de pares não ordenados de elementos distintos de V . Uma clique de um grafo G(V,E) é um subconjunto S de V tal que G[S] é completo. Fixando um Ɵ que delimitará a distância entre os genes e utilizando a matriz de distância, podemos construir o grafo de distâncias: associamos um vértice para cada gene; e para cada par de genes, se a distância entre eles for menor que Ɵ, desenhamos uma aresta entre eles (Figura 1). Desse modo, no grafo de distâncias as cliques representam clusters. O grafo de cliques é um grafo onde cada componente é um grafo completo. Um grafo pode ser transformado em um grafo de cliques, removendo-se ou incluindo-se arestas, conforme a Figura 2. Este é o chamado Problema da Clique Corrompida, cuja principal pergunta é: dado um grafo G, qual seria o menor número de arestas inseridas e removidas para transformar G num grafo de cliques? Este problema foi provado ser NP-Difícil e existem algumas Heurísticas para resolvê-lo [1]. Neste trabalho, estudamos o problema para as classes de grafos: caminhos e ciclos. Uma sequência de vértices v1,...,vk tal que (vj, vj1) ϵ E, 1  j  (k-1) é denominado caminho de v1 a vk, conforme a Figura 2. Um ciclo é um caminho v1,...,vk, sendo v1  vk e k4. Definimos como custo a soma do número de arestas removidas com o número de arestas inseridas necessárias para transformar o grafo em um grafo de cliques.