Evolving Graph Compression using Similarity Measures for Bioinformatics Applications
Many real world graphs, including those storing various forms of biological data, are of such large size that storing and processing their information has too high a cost. As a result, one possible solution is to compress the graphs by merging nodes into supernodes. This study introduces a genetic algorithm for graph compression that is based on the similarity of nodes, where two nodes are considered similar if a high proportion of their neighbours are in common. The methodology was applied to three real world graphs storing widely varying data, as well as the gene regulatory network of E. coli. This study used a fixed compression rate of 25 as a target for the graphs. Results for a parameter study of variation operators exhibit a strong preference for crossover, in comparison to mutation which was found to be disruptive to graph structure.
2016 IEEE Conference on Computational Intelligence in Bioinformatics and Computational Biology (CIBCB)