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

Chalupa, David

Abstract

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.

Citation

Chalupa, D. (2016). On combinatorial optimisation in analysis of protein-protein interaction and protein folding networks. In G. Squillero, & P. Burelli (Eds.), Applications of Evolutionary Computation; Lecture Notes in Computer Science (91-105). Springer Publishing Company. https://doi.org/10.1007/978-3-319-31204-0_7

• Conference Name: 19th European Conference, EvoApplications 2016, Porto, Portugal
• Start Date: Mar 30, 2016
• End Date: Apr 1, 2016
• Online Publication Date: Mar 15, 2016
• Publication Date: 2016
• Deposit Date: May 25, 2016
• Publicly Available Date: May 25, 2016
• Print ISSN: 0302-9743
• 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
• DOI: https://doi.org/10.1007/978-3-319-31204-0_7
• Keywords: Combinatorial optimisation; Protein-protein interaction networks; Protein folding networks; Hybrid heuristics
• Public URL: https://hull-repository.worktribe.com/output/438747
• Publisher URL: The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-319-31204-0_7
• Contract Date: May 25, 2016