University of Hull logo

On combinatorial optimisation in analysis of protein-protein interaction and protein folding networks

Chalupa, David



G. Squillero

P. Burelli


Abstract: Protein-protein interaction networks and protein folding networks represent prominent research topics at the intersection of bioinformatics and network science. In this paper, we present a study of these networks from combinatorial optimisation point of view. Using a combination of classical heuristics and stochastic optimisation techniques, we were able to identify several interesting combinatorial properties of biological networks of the COSIN project. We obtained optimal or near-optimal solutions to maximum clique and chromatic number problems for these networks. We also explore patterns of both non-overlapping and overlapping cliques in these networks. Optimal or near-optimal solutions to partitioning of these networks into non-overlapping cliques and to maximum independent set problem were discovered. Maximal cliques are explored by enumerative techniques. Domination in these networks is briefly studied, too. Applications and extensions of our findings are discussed.

Book Type Book Chapter
Start Date Mar 30, 2016
Publication Date 2016
Journal Applications of evolutionary computation
Print ISSN 0302-9743
Electronic ISSN 1611-3349
Publisher Springer Publishing Company
Peer Reviewed Not Peer Reviewed
Volume 9597
Pages 91-105
Book Title Applications of Evolutionary Computation; Lecture Notes in Computer Science
ISBN 9783319312033; 9783319312040
Keywords Combinatorial optimisation; Protein-protein interaction networks; Protein folding networks; Hybrid heuristics
Publisher URL The final publication is available at Springer via
Copyright Statement © 2016 the author


Downloadable Citations