Estudo de diferentes algoritmos visando o bandiwth minimization

Abstract

A quantidade de informações disponiveis sobre sistemas complexos como a internet, redes sociais e biológicas nunca foi tão grande. Por isso, desenvolver as ferramentas computacionais necessárias para analisar essas informações é uma tarefa que merece muita atenção. Nesse trabalho, estamos interessados em um problema em particular: encontrar as comunidades de uma rede metabólica ou de interação proteína-proteína (PPI de proteinprotein interaction). Devido a complexidade computacional do problema nós desenvolvemos dois algoritmos heurísticos e os comparamos com dois algoritmos tradicionais: Kruskal e PageRank. Muito embora os ordenamentos obtidos pelos nossos algoritmos pareçam aproximar os nós de uma maneira mais efetiva, ao compararmos nossos resultados com os termos GO (de Gene Ontology, que relacionam as proteínas com suas funções biológicas) associados não encontramos forte correlação.

The amount of available data on complex systems such as the internet, social and biological networks has never been bigger. As such, developing the necessary computational tools to handle this data is a task of great importance. In this work we are interested in one particular problem: finding the community structure of a metabolic or PPI network. Due to it’s computational complexity we propose two heuristic algorithms to tackle this problem and compare them to two traditional ones, namely Kruskal and PageRank. Even though our algorithms seem to be better at clustering the networks, when we compared our results with those of the GO terms (from Gene Ontology, they relate the proteins in the network to their biological functions) no strong correlation was found.