Prediction of GO terms for IDPs based on highly connected components in PPI networks

Abstract

Partitioning large biological networks can help biologists to retrieve new information for particular biological structures. In literature, various methods for partitioning and clustering biological networks have been proposed. The aim of such a network partitioning is to retrieve smaller structures which are easier to analyse, but still containing important information about relations between the network elements. Highly connected deletion problem is one of such network partitioning, with the aim to partition a network into highly connected components (hcd components) by deleting minimum number of edges. A network component with n nodes is a hcd component if the degree of every vertex is larger than n/2. For the purpose of this research, we used a specially constructed local search based heuristic approach to identify hcd components. Dealing with protein-protein interaction (PPI) networks, it has been noticed that proteins from the same hcd component in a network have same Gene Ontology (GO) annotations. Based on that, we proposed a new method for prediction of GO annotations, which consists of the following steps: (a) starting PPI network is partitioned to hcd components; (b) the obtained hcd components are expanded by proteins which became singletons in the partition set; (c) the newly formed extended hcd components are the subject of further enrichment analysis in DiNGO tool, which returns a list of existing GO terms for proteins from the considered extended component; (d) after propagation through GO hierarchy, the extended list of GO is obtained; (e) each protein from the extended hcd component is annotated by a number of GO terms obtained from the previous step; The proposed method is tested on the data from CAFA-3 challenge. Comparing the F1-measure of the obtained results, a combination of parameters (type of extension, cutoff for enrichment analysis and maximum number of GO terms) with the best performances is selected for the further usage. The method with the selected parameters was further applied on a class of Intrinsically Disordered Proteins (IDP). Preliminary results indicate that this method can be useful for proposing new GO terms for IDP proteins.