PGR: Protein Graph Repository
Computational Processing of Protein Structures

# Repository

### Content:

Graphs representing all protein 3D-structures (from the PDB). The repository is enriched by a smart search tool allowing the filtering and targeting of a specific population of protein-graphs. See the help icon for more details.

### Visualization:

Each protein is presented solely in a specific web page containing:
• Visualization of the protein graph using three different JavaScript libraries namely D3, Cytoscape, and sigmajs.
• Graph attributes: corresponding values for a set of topological and label based graph measures, z-score for each attribut value : $$(x - mean)/Stdev$$ (where x is the value of the attribute, mean is the mean of all values of the attribute in the dataset, and Stdev is the standard deviation)

### Graph attributes:

The considered graph attributes are:
1. Number of nodes: The total number of nodes in the graph, also called the graph order $$|V|$$.
2. Number of edges: The total number of edges in the graph, also called the graph size $$|E|$$.
3. Average degree: The degree of a node $$u$$, denoted $$deg(u)$$, represents the number of nodes adjacent to $$u$$. The average degree of a graph $$G$$ is the average value of the degrees of all nodes in $$G$$. Formally: $$deg(G) = \frac{1 }{n } \sum^n_{i=1 } deg(u_i )$$ where $$deg(u_i )$$ is the degree of the node $$u_i$$ and $$n$$ is the number of nodes in $$G$$.
4. Density: The density of a graph $$G=(V, E)$$ measures how many edges are in $$E$$ compared to the maximum possible number of edges between the nodes in $$V$$. Formally: $$den(G) = \frac{2 \mid E\mid}{(\mid V\mid\ast (\mid V\mid -1))}$$.
5. Average clustering coefficient: The clustering coefficient of a node $$u$$, denoted by $$c(u)$$, measures how complete the neighborhood of $$u$$ is, $$i.e.$$, $$c(u)= \frac{2 e_u }{k_u (k_u - 1)}$$ where $$k_u$$ is the number of neighbors of $$u$$ and $$e_u$$ is the number of connected pairs of neighbors. If all the neighbor nodes of u are connected, then the neighborhood of $$u$$ is complete and we have a clustering coefficient of 1. If no nodes in the neighborhood of $$u$$ are connected, then the clustering coefficient is 0. The average clustering coefficient of an entire graph $$G$$ having $$n$$ nodes, is given as the average value over all the nodes in $$G$$. Formally: $$C(G)= \dfrac{1 }{n } \sum_{i=1 }^n c(u_i )$$.
6. Average effective eccentricity: For a node $$u$$, the effective eccentricity represents the maximum length of the shortest paths between $$u$$ and every other node $$v$$ in $$G$$, $$i.e.$$, $$e(u) = max\{d(u,v) : v\in V\}$$. If $$u$$ is isolated then $$e(u) = 0$$. The average effective eccentricity is defined as $$Ae(G)= \frac{1 }{n }\sum_{i=1 }^n e(u_i )$$, where $$n$$ is the number of nodes of $$G$$.
7. Effective diameter: The effective diameter represents the maximum value of effective eccentricity over all nodes in the graph $$G$$, $$i.e.$$, $$diam(G) = max\lbrace e(u)\mid u\in V\rbrace$$ where $$e(u)$$ represents the effective eccentricity of $$u$$ as defined above.
8. Effective radius: The effective radius represents the minimum value of effective eccentricity over all nodes in the graph $$G$$, $$i.e.$$, $$rad(G) = min\lbrace e(u)\mid u\in V\rbrace$$ where $$e(u)$$ represents the effective eccentricity of $$u$$.
9. Closeness centrality: The closeness centrality measures how fast information spreads from a given node to other reachable nodes in the graph. For a node $$u$$, it represents the reciprocal of the average shortest path length between $$u$$ and every other reachable node in the graph, $$i.e.$$, $$C_c(u) = \frac{n-1 }{\sum_{v\in \lbrace V\setminus u\rbrace } d(u,v)}$$ where $$d(u,v)$$ is the length of the shortest path between the nodes $$u$$ and $$v$$. For a graph $$G$$, we consider the average value of closeness centrality of all the nodes, $$i.e.$$, $$C_c(G) = \frac{1 }{n } \sum_{i=1 }^n u_i$$.
10. Percentage of central nodes: Here, we compute the ratio of the number of central nodes from the number of nodes in the graph. A node $$u$$ is considered as central point if the value of its eccentricity is equal to the effective radius of the graph, $$i.e.$$, $$e(u) = rad(G)$$.
11. Percentage of end points: It represents the ratio of the number of end points from the total number of nodes of the graph. A node $$u$$ is considered as end point if $$deg(u) = 1$$.
12. Label entropy: It measures the uncertainty of labels. The label entropy of a graph $$G$$ having $$k$$ labels is measured as $$E(G) = -\sum_{i=1 }^k p(l_i)\ \ log\ \ p(l_i)$$, where $$l_i$$ is the $$i^{th }$$ label.
13. Neighborhood impurity: The impurity degree of a node $$u$$ belonging to a graph $$G$$, having a label $$L(u)$$ and a neighborhood (adjacent nodes) $$N(u)$$, is defined as $$ImpurityDeg(u) = \mid L(v): v \in N(u), L(u)\neq L(v)\mid$$. The neighborhood impurity of a graph $$G$$ represents the average impurity degree over all nodes with positive impurity.
14. Link impurity: An edge $$\{u,v \}$$ is considered to be impure if $$L(u)\neq L(v)$$. The link impurity of a graph $$G$$ with $$k$$ edges is defined as: $$\frac{\mid\{u,v \}\in E: L(u)\neq L(v)\mid }{k }$$.

# PG-Similarity

PG-Similarity allows to perform a pairwise comparison of a selected protein against the entire repository in order to detect the most similar proteins. Similarity between proteins is based on the distance between their corresponding graph-based description using the computed attributes. Similar proteins are ranked ascendantly according to their distance to the query protein.

### Distance measures:

1. Euclidean: Computes the distance between $$m$$ points using Euclidean distance (2-norm) as the distance metric between the points. The points are arranged as $$m$$ $$n$$-dimensional row vectors in the matrix X.
2. Standardized Euclidean: Computes the standardized Euclidean distance. The standardized Euclidean distance between two n-vectors u and v is
$\sqrt{\sum {(u_i-v_i)^2 / V[x_i]}}.$
V is the variance vector; V[i] is the variance computed over all the i’th components of the points.
3. Squared Euclidean: Computes the squared Euclidean distance $$||u-v||_2^2$$ between the vectors.
4. Cosine: Computes the cosine distance between vectors u and v,
$1 - \frac{u \cdot v} {{||u ||}_2 {||v ||}_2}$
where $$||*||_2$$ is the 2-norm of its argument *, and $$u \cdot v$$ is the dot product of $$u$$ and $$v$$.
5. Manhattan: Computes the city block or Manhattan distance between the points.
6. Correlation: Computes the correlation distance between vectors u and v. This is
$1 - \frac{(u - \bar{u }) \cdot (v - \bar{v })} {{||(u - \bar{u })||}_2 {||(v - \bar{v })||}_2}$
where $$\bar{v }$$ is the mean of the elements of vector v, and $$x \cdot y$$ is the dot product of $$x$$ and $$y$$.
7. Normalized Hamming: Computes the normalized Hamming distance, or the proportion of those vector elements between two n-vectors u and v which disagree.
8. Jaccard: Computes the Jaccard distance between the points. Given two vectors, u and v, the Jaccard distance is the proportion of those elements u[i] and v[i] that disagree where at least one of them is non-zero.
9. Minkowski: Computes the distances using the Minkowski distance $$||u-v||_p$$ ($$p$$-norm) where $$p \geq 1$$.
10. Chebyshev: Computes the Chebyshev distance between the points. The Chebyshev distance between two n-vectors u and v is the maximum norm-1 distance between their respective elements. More precisely, the distance is given by
$d(u,v) = \max_i {|u_i-v_i |}.$
11. Canberra: Computes the Canberra distance between the points. The Canberra distance between two points u and v is
$d(u,v) = \sum_i \frac{|u_i-v_i |}{|u_i |+|v_i |}.$
12. Bray-Curtis: Computes the Bray-Curtis distance between the points. The Bray-Curtis distance between two points u and v is
$d(u,v) = \frac{\sum_i (u_i-v_i)}{\sum_i (u_i+v_i)}$
13. Mahalanobis: Computes the Mahalanobis distance between the points. The Mahalanobis distance between two points u and v is $$(u-v)(1/V)(u-v)^T$$ where $$(1/V)$$ (the VI variable) is the inverse covariance. If VI is not None, VI will be used as the inverse covariance matrix.

### Statistics and charts:

Results of similarity queries are enriched by statistical values to help analysing and understanding obtained results. Statistics include distance between the query protein and each of the target proteins, min: the distance between the query protein and the most similar target from the entire repository, max: the distance between the query protein and the least similar target from the entire repository. Graphical bar chart for each graph attribute is also available for visualizing the distribution of attributes for the query and target protein.

# PG-Converter

PG-Converter allows the transformation of protein 3D-structures into protein-graphs using chosen graph building method and distance threshold.

### Graph building methods:

1. CAlpha atom: Each amino acid is abstracted into its CAlpha atom such that only distances between CAlpha atoms is considered for building graph edges.
An edge is created between a pair of nodes (accordingly two CAlpha atoms) only if the distance between them is equal or below the specified minimum distance threshold.
2. CBeta atom: Each amino acid is abstracted into its CBeta atom such that only distances between Cbeta atoms is considered for building graph edges.
An edge is created between a pair of nodes (accordingly two CBeta atoms) only if the distance between them is equal or below the specified minimum distance threshold.
3. Amino acid centroid: Each amino acid is abstracted into its centroid which is computed according to all of its atoms cordinates.
An edge is created between a pair of nodes (accordingly two amino acids centroids) only if the distance between them is equal or below the specified minimum distance threshold.
4. Side chain centroid: Each amino acid is abstracted into its side chain centroid which is computed according to its side chain atoms cordinates.
An edge is created between a pair of nodes (accordingly two side chains centroids) only if the distance between them is equal or below the specified minimum distance threshold.
5. Amino acid ray: Each amino acid is abstracted into its ray which is computed according to all of its atoms cordinates.
An edge is created between a pair of nodes (accordingly two amino acids) only if the distance between the extremities of their rays is equal or below the specified minimum distance threshold.
6. Amino acid ray and side chain orientation: Each amino acid is abstracted into its ray which is computed according to all of its atoms cordinates.
An edge is created between a pair of nodes (accordingly two amino acids) only if the distance between the extremities of their rays is equal or below the specified minimum distance threshold. The orientation of the side chain is also considered as a constraint for edge creation.
7. Side chain ray: Each amino acid is abstracted into its side chain ray which is computed according to its side chain atoms cordinates.
An edge is created between a pair of nodes (accordingly two amino acids) only if the distance between the extremities of their side chains rays is equal or below the specified minimum distance threshold.
8. All atoms: All the atoms of each amino acid are considering for creating edges.
An edge is created between a pair of nodes (accordingly two amino acids) only if the distance between any pair of their atoms is equal or below the specified minimum distance threshold. All possible combinations are considered.

### Distance threshold:

The distance threshold is expressed in Aº and it represents the maximal distance between atoms (depending on the graph building method) to be accepted for considering connections between amino acids. In other words, an edge is created between two nodes (amino acids) if the distance between them is less or equal two the given distance threshold.

### Output formats:

Available output formats are:
• .pgr: our proposed format:
#graph_building_method
#vertices
vertex1_label index
...
#edges
vertex1_label index1 vertex2_label index2

...
• .layout: for Biolayout visualization platform.
• .gcl: for GraphClust.
• .nwb: for Network Workbench visualization platform.
• .sds: for Subdue a graph based knowledge discovery tool.
• .lng: Line Graph format, used by many graph analysis tools such as gSpan and GASTON.
• .GraphML: GraphML is an XML-based file format for graphs. Supported by many graph analysis and visualization tools such as NodeXL, GUESS, NetworkX, Gephi, Cytoscape, and many others.
• .gml: Graph Modeling Language (GML)(also named Graph Meta Language) is a hierarchical ASCII-based file format for describing graphs. Supported by many graph analysis and visualization tools such as Gephi, Cytoscape, NetworkX, Graph-tool, igraph, and many others.