Abstract

We present and develop the theory of 3-way networks, a type of hypergraph in which each edge models relationships between triplets of objects as opposed to pairs of objects as done by standard network models. We explore approaches of how to prune these 3-way networks, illustrate their utility in comparative genomics and demonstrate how they find relationships which would be missed by standard 2—way network models using a phylogenomic dataset of 211 bacterial genomes.

Author Summary

One way to compare the entire genomes of different organisms is to compare their gene-family content profiles which is effectively a comparison of their functional potential. Standard networks, when used to model phylogenomic similarities, are not capable of capturing some of the underlying complexity of the relationships between genomes. In order to address this, we have developed a new three-way similarity metric and constructed three-way networks modelling the relationships between 211 bacterial genomes. We find that such three-way networks find cross-species genomic similarities that would have been otherwise missed by simpler models such as standard networks.

Introduction

Networks involve representing a collection of objects as nodes, and representing relationships between those objects as edges. Thus networks model a system in a pairwise manner, breaking a system down into individual parts (nodes), modelling relationships between pairs of these individual parts (edges) and then reconstructing the system as a network [1]. However, modelling a system based on only pairwise relationships biases the model against more complex relationships that may exist in the system. To this end, we introduce a new ternary network definition, namely 3-way networks based on the concept of hypergraphs. A Hypergraph is a generalized network, in which an edge can model the relationship between an arbitrary number of objects [2, 3]. Clustering algorithms for hypergraphs, also known as Hypergraph Partitioning algorithms, have been developed in which nodes of a graph are assigned to k partitions. This can be performed by minimising the net cut, which is defined as the number of hyperedges which connect nodes in different partitions [3]. Software packages such as hMetis [4] are available to perform this k-way clustering.

The concept of calculating the similarity between objects three at a time is not a novel concept [5—7] and general hypergraphs [2] have previously been used in certain areas of biology, including metabolic modelling, gene eXpression and RNA interaction studies [8—12]. However, to our knowledge, this is the first time that the concept of 3-way networks has been applied in the field of comparative genomics.

We develop a new 3-way metric for the weighting of 3-way edges. We then apply a 3-way network model to a set of 211 bacterial genomes, modelling the similarities between the bacteria on a whole genome scale, (based on gene family content), and compare the resulting 3-way networks to those obtained using standard 2-way network models.

Results/Discussion Definition of 3-way Networks

A network, or graph, G is an ordered pair, defined as where V: {111, v2, . . ., vn} is a set ofn nodes and E 2 {e1, e2, . . ., em} is a set ofm edges [13]. In this case, nodes represent a certain set of objects of interest and edges can be interpreted as relationships between these objects. In particular, edges represent pairwise relationships and thus are defined (for an undirected network) as pairs of nodes. For clarity, we refer to these networks as 2-way networks because of the pairwise nature of the edges. With the aim of modelling higher order relationships than simply pairwise relationships, we define 3-way networks as network models of ternary relationships, i.e. relationships between triplets of objects. 3-way networks are defined by replacing the preVious definition of an edge as a set of 2 nodes by a set of 3 nodes. Thus a 3-way network is a type of hypergraph [2]. This can be formalized with the following definition:

Weighted 3-way Networks

In a 2-way network, each edge can be assigned a weight indicating the strength of the relationship between the two nodes the edge is connecting. This concept can easily be extended to a 3-way network, in which an edge weight will indicate the strength of the relationship between the 3 nodes the edge is connecting. For a 3-way network, this requires a similarity metric which quantifies the similarity between 3 objects at a time. Assuming that each object is represented by a vector, a similarity metric which quantifies the similarity between 3 vectors is needed. The Sorensen Index [14] is a similarity metric which quantifies the overlap between the features of pairs of objects. Let A and B be two objects and let each object be viewed as a set of features. The Sorensen Index 82(A, B) is defined as: Where a is the number of features of object A, b is the number of features of object B and ab is interpreted as the number of features shared by object A and object B [15]. If objects are represented by vectors, the Sorensen Index between two vectors X and Y can be expressed as: Where X B and YB are binary vectors defined as:

This metric was originally developed for quantifying the similarity between the species content of different biological samples [5]. Generally, for each triplet of objects A, B, and C, each represented by a vector, the three-way Sorensen index can be defined as:

These variables can be Visualized on a venn diagram (Fig. 1b). The 3-way Sorensen Index can also be eXpressed in vector format as follows: 3-way Czekanowski Index. A quantitative version of the Serensen Index is called the Cze-kanowski Index [16]. For two vectors X and Y, the Czekanowski Index is defined as:

The Czekanowski Index thus considers the size of the overlaps between features of an object and not simply the presence or absence of features. Using the same structure as the 3-way Sorensen Index, we extended the Czekanowski Index to a 3-way form. For 3 vectors X, Yand Z, we have defined the 3-way Cze-kanowski Index between the three vectors as:

Pruning 3-way Networks

Many approaches used to prune edges from a network such as Maximum Spanning Tree (MST) algorithms and clustering algorithms are designed for 2-way networks and are not directly applicable to 3-way networks. However, certain approaches are easily transferable to 3-way networks, namely thresholding and best-edge selection.

Thresholding can easily be transferred from a 2-way network to a 3-way network. Thresholding is one of the simplest ways to prune any network. A threshold is set and edges with a weight below the chosen threshold are removed. In order to determine a justifiable threshold for a 3-way Sorensen network we have developed the following theorem:

If the intersection of three objects abc is zero (i.e. there is no feature present in where [1, b, and E are defined in Fig. 1b. There are two cases to consider. Case 1: If El, (3 and E are all equal to 0, then Case 2: If El, (3 and E are all greater than zero 0 (they cannot be less than zero, since there canThus if abc = 0 and a, E and E are all equal to 0 then SABC = not be a negative number of features associated With an object), then Thus if abc = 0 and a, E and E are all greater than zero 0, 83 (ABC) < Combining these two cases, we can conclude that if abc = 0, 83 (ABC) 3 This implies that, for a given 3 species, there are no gene families present in only one of the 3 species, then the 3-way Sorensen Index between the 3 species will be greater than 0.75. A similar thresholding strategy can be adopted for the 3-way Czekanowski Index. We need the following: Lemma 1. Given integers a, b and c, the following relation holds: We now prove a theorem similar to Theorem 1, but relating to the 3-way Czekanowski Index. Using Lemma 1, this can be expanded as: Thus the minimum justifiable threshold for 3-way Sorensen and 3-way Czekanowski networks is 0.75.

Another simple way to prune a network is to select for each node, the best x edges connected to that node, i.e. select the x edges with the highest weight for each node. This is easily done by taking a list of all edges connected to a given node, ranking them by weight from highest to lowest, and then selecting the top x edges. This approach does not depend on the definition of the edge. It is directly transferable from the concept of a 2-way network to the concept of a 3-way network.

Phylogenomic Networks of Bacterial Genomes

Various phylogenomic 2-way similarity, 3-way similarity and gene family enrichment networks were then constructed in order to investigate the relationships between the bacterial species based on gene family content and to compare the effect of 3-way networks as opposed to 2-way networks. These networks are described below. In each network, nodes represent bacterial species and edges represent similarities between species based on 2-way or 3-way similarity between their gene family content profiles, or represent connections between species based on shared gene family enrichment.

The concept of 3-way networks was developed in order to attempt to model more complex relationships that would otherwise be missed by pairwise relationships. To this end, the definition of an edge was extended to represent a ternary relationship, i.e. a relationship between 3 nodes. In order to quantify these ternary relationships, a 3-way similarity metric was chosen, namely the Sorensen Index. This allowed “high order similarities” or similarities between more than two species to contribute to our interpretation. The 3-way Sorensen Index was used to quantify the similarity between all triplets of bacterial species, based on their gene family content. Applying a threshold of 0.76 allowed us to select for edges which we were sure had a contributing factor of the 3-way intersection and not simply a high intersection between pairs of species (See Theorem 1). This thresholded network can be seen in S1 Fig. Large coloured nodes represent bacterial species and the combination of the small white nodes and the grey 2-way edges represent 3-way edges. Certain genera were selected and those bacterial species nodes coloured according to genus. (The default node colour was grey, thus grey nodes are not all in the same genus). The 3-way network was also pruned by selecting only the best and second best edge for each node. This best-edge 3-way Sorensen network can be seen in Fig. 2.

For the best edge approach, the best and second best edges were selected for each node. The resulting network is shown in Fig. 3a.

The Sorensen MST can be seen in Fig. 3b.

In each network, nodes of the same colour group together, indicating that the genera group together well. The network shown in Fig. 2 especially seems to show an interesting middle ground between connectedness and modularity. There are generally many connections within genera, but also some connections between genera. In contrast to this is the 2-way Sorensen MST shown in Fig. 3b. MSTs, by there very nature, have no modularity. This is clear in Fig. 3b where the genera do seem to group together, but there are no connections within the genera. MSTs thus give limited information, and should be used in combination with other types of networks and pruning methods. The 2-way Sorensen best edge network (Fig. 3a) was constructed by selecting only the best and second best edges for each node from the standard 2-way Sorensen network. It would appear that this 2-way best edge network is overly sparse, and does not give much information about the connectedness between genera. It would seem that the genera are also not as well grouped as in the 3-way best-edge network.

A new 3-way metric was developed called the 3-way Czekanowski Index. It is an extension of the standard 2-way Czekanowski Index [16] in the same way that the 3-way Sorensen Index [5] is an extension of the original 2-way Sorensen Index [15]. A 3-way network was constructed using the 3-way Czekanowski Index and pruned in the same way described above for the 3-way Sorensen network. The thresholded 3-way Cze-kanowski network and the best-edge 3-way Czekanowski network can be seen in S3 and 4 Figs. respectively. Networks were also constructed using the standard 2-way Czekanowski Index and can be seen in Figs. 5a and 5b.

In order to get another perspective on the relationships between the bacteria species based on gene families, a gene family enrichment network was constructed (Fig. 6). In this network, large, coloured nodes represent bacterial species and small white nodes represent gene families which are enriched in more than one species as determined using Fisher’s Exact Test [18] Each gene family node is connected to the species in which the gene family is enriched. It can clearly be seen that the genera group together well in this network. Shared enriched families thus seem to be a competent measure of species similarity. This network also allows us to target gene families which seem to be distinguishing characteristics of small groups of species.

The 3-way Sorensen networks often support the interpretations of the 2-way networks. However, in some cases, the 3-way networks give new information which differs from that of the 2-way networks. A selection of examples have been selected in order to illustrate situations where the 3-way networks differ from 2-way networks, as well as examples where there is agreement between 2-way and 3-way networks. A procedure was implemented to calculate a “measure of disagreement” between the local topologies of genera between 2-way and 3-way networks. The number of edges within and between genera were quantified for each genera in 2-way and 3-way networks by counting the number of inbound edges (edges connecting species within genera) and outbound edges (edges connecting species across genera). A ratio of inbound over outbound edges was then calculated for each genera in 2-way networks and in 3-way networks, as well as the reciprocal ratio. These values were ranked for each network, and the differences between the rank of a genera’s ratio between the two types of networks were calculated. This was performed for both orientations of the ratio. These scores (see Supplementary S1 Table) give an indication of how different the modularity of a genus is between 2-way and 3-way networks, with larger values indicating a larger difference. The examples chosen to illustrate differences between the two types of networks did indeed have high scores.

The cluster of red and light blue nodes in the 3-way Sorensen network (Fig. 2) and the 3-way Czekanowski network (Fig. 4) consist of Clostridium species (light blue nodes) and Bacillus species (red nodes). Fig. 7a and 7b show subnetworks containing these two clusters, and it is clear that, in both the Sorensen 3-way network and the Czekanowski 3-way network, there are a number of 3-way edges connecting species within and between those two genera. When looking at the same two genera in the 2-way Sorensen and 2-way Czekanowski networks (Figs. 3a, 3b, 5a and 5b) there is no evidence of any particular link between these 2 genera. In the 2-way Sorensen MST (Fig. 3b) the two genera are close together, but there are no edges between them. In the 2-way best edge Sorensen network (Fig. 3a) these two genera are in two completely separate modules, giving no indication whatsoever that they are connected or similar. Similar patterns are seen in the 2-way Czekanowski MST (Fig. 5b) and the 2-way best edge Czekanowski network (Fig. 5a). When looking at the shared enriched gene family network (Fig. 6) the Clostridium and Bacillus species are topologically close together. The Clostridium and Bacillus species as well as their neighbouring gene families were selected as a subnetwork from the family enrichment network and can be seen in Fig. 7c. It is apparent that the Clostridium and Bacillus species share several enriched gene families. The 3-way Sorensen and 3-way Czekanowski networks seem to be picking up a relationship between the two genera which is not seen in the 2-way networks, which is further supported by the gene family enrichment data.

The genes in these gene families were then compared against all Clostridium and Bacillus proteins in NCBI using BLAST [19, 20]. Many of the genes identified were related to sporulation. Clostridium and Bacillus species are known to sporulate and there is literature evidence for the conservation of various sporulation genes across these two genera [21]. Sporulation is a process which involves the production of a endospores, which are dormant and highly resistent to environmental stresses [21]. Examples of genes in these gene families enriched in both Bacillus and Clostridium species were Aer and GerKA, which are known to be involved in sporulation in Bacillus species [22].

There is literature evidence for the requirement of polysaccharide deacetylases for sporulation in Bacillus subtilis, in which pdaB mutants were unable to properly maintain their spores in the later stages of sporulation [23]. The pdaA gene has also been found to be neccesary for spore germination in B. subtilis [24]. The enrichment of this family in both Clostridium and Bacillus species along with the other sporulation families could suggest a similar role of deacetylases in the sporulation of Clostridium species.

Chemo-taxis and sporulation are oppositely regulated processes and are both regulated by the major sporulation regulating protein SpoOA [25]. Thus, it would appear that even though Bacillus and Clostridium are quite distant phylogenetically, they share a set of sporulation related families which appear to be detected by 3-way networks, and are missed by simpler 2-way networks quantifying only 2-way relationships.

Species in the genus Brucella can be found as light orange nodes. In the Sorensen MST and the Czekanowski MST (Figs. 3b add 5b respectively), this genus is split into two groups, one group containing B. canis, B. abortis and B. ovis (Group 1), and the other group containing B. melitensis and B. suis (Group 2). These same separate groupings are also seen in the best-edge 3-way Sorensen network (Fig. 2) and best-edge 3-way Czekanowski network (Fig. 4). Thus using different 2-way and 3-way similarity metrics, the Brucella species partition in the same way. Fig. 8a and b show the neighbourhoods within one 3-way edge of the Brucella species in the best edge Sorensen network and the best edge Czekanowski network respectively. Fig. 8c is a subnetwork of the enrichment network (Fig. 6) showing all nodes within a radius of 2 of the Brucella nodes. From Fig. 8 the same groupings of the genus can be observed, thus this separation of the genus can be seen on a whole gene family profile scale, as well as on a gene family enrichment level. These groupings are different to the divergence previously found in the Brucella genus, in which B. abortus clustered nearer to B. melitensis and B. suis clustered nearer to B. canis [26].

This is supported by the gene family enrichment view in Fig. 8c. Fig. 8a and b also suggests a relationship between Group 2 Brucella species and Ochrobactrum anthropi. This is also seen in the gene family enrichment view. Of the 3-way networks, only the Czekanowski network suggests that Group 2 of Brucella species, namely Brucella suis and Brucella melitensis group together with members of the Bordetella genus. This is also seen in the gene family enrichment view in Fig. 8c. None of the 2-way networks suggested this connection. The 2-way MSTs (Figs. 3b and 5b) show the proximity of Group 1 to the Bartonella species and the proximity of Group 2 to O. anthropi, however they do not suggest the link between Group 2 Brucella species and Bordetella species. The 2-way best edge networks (Figs. 3a and 5a) only show the connection between Group 2 and O. anthropi. They show none of the relationships suggested by 3-way networks between Group 1 and Bartonella species, and Group 2 and Bordetella species.

Consider the genus Rhodobacter in the above networks (two medium blue nodes). In the Sorensen MST (Fig. 3b) these two nodes are neighbours. This is also seen in the best edge Sorensen network (Fig. 3a). However, in both Czekanowski 2-way networks (Figs. 5b and 5a), these two Rhodobacter species are not neighbours. The 3-way Sorensen and 3-way Czekanowski networks (Figs. 2 and 4) place these nodes quite far apart. Fig. 9a and b show the neighbourhoods within one 3-way edge of Rhodobacter species in the 3-way Sorensen network and 3-way Czekanowski network respectively. From this figure, it can be seen that the nodes are in separate neighbourhoods. This is also seen in the enriched family view in Fig. 9c. This figure shows the species which share at least one enriched family with Rho-dobacter species. Both Sorensen and Czekanowski best edge 3-way networks thus pick up a separation between the two Rhodobacter species which is supported by the gene family enrichment data and not found by the 2-way Sorensen networks.

A further examination of Figs. 8 and 9 shows that there seem to be overlaps between the Brucella groupings in Fig. 8 and the Rhodobacter groupings in Fig. 9. Fig. 10 shows the neighbourhood around Brucella species and Rhodobacter species in (a) the 3-way best edge Czekanowski network and (b) the gene family enrichment network. Group 1 Brucella species cluster with Bartonella species and Rhodobacter capsulatus and Group 2 Brucella species cluster witth Bordetella species, Ochrobactrum athropi and Rhodobacter sphaeroides. This amount of detail in groupings of species was not found in any of the 2-way networks.

Merging the 3-way best edge Sorensen network (Fig. 2) and the 2-way Sorensen MST (Fig. 3b) results in an interesting network which is shown in S4 Fig. This network combines the modularity of the 3-way network showing the connections within genera and a few cross-genera connections with the MST which shows the overall connections across genera. This combined 2-way and 3-way Czekanowkski network (SS Fig.) was also constructed by merging the 3-way best edge Czekanowski network (Fig. 4) and the 2-way Czekanowski MST (Fig. 5b). These combination networks provide an interesting, “best of both worlds” view. They combine the connectedness and simplicity of an MST, which allows for no modularity, but forces all nodes to connected to the network, and the modularity and compleX relationships provided by the 3-way networks which show a mixture of within-mod-ule connection and intermodule connections, and show relationships missed by standard 2-way networks.

Conclusions

These networks, when used to model the phylogenomic relationships between 211 bacterial species revealed relationships between the species which were not found when using standard 2-way network models. These networks will be a useful tool for comparative genomics in order to model and reveal compleX relationships.

Materials and Methods

Bacterial Gene Family Construction

An all-vs-all protein BLAST [19] was performed on the translated genomes of 211 bacterial species to calculate the sequence similarity between all pairs of proteins across the 211 bacterial genomes. An E-Value cutoff of 10—5 was used. The Perl script 0 rthomc 1B 1 a s t Par 5 e r from the OrthoMCL package [27] was then used to parse the Blast results in order to select only the best Blast match per gene pair. For each gene pair ab, a score Sal, was calculated as [17]:

This resulted in a network in which each node represented a gene and each edge ab represented the similarity between the two nodes (a and b) which it connects, weighted by the similarity score Sab. MCL was then applied using an inflation value of 2 to cluster the network into gene families [28]. From the resulting gene families, a matriX was constructed called the Species-Family (SF) matrix, in which the rows represented bacterial gene families constructed using TribeMCL, and columns represented bacterial species, and each entry ij represented the number of genes in gene family 1' present in species j. 3-way Network Construction

Let X,- and Y,- and Z,- represent the ith element in columns X, Y and Z of the SF-matrix (i.e. the number of members of gene family i in species X species Y and species Z respectively. Let X B, YB and Z 3 be the binary vectors associated with vectors X, Y and Z respectively. For each triplet of species (X, Y, Z) the Sorensen Index was calculated using Equation 7 and the Czekanowski Index was calculated using Equation 9. This resulted in a Sorensen 3-way network and a Czekanowski 3-way network. Using Theorem 1, any threshold set above 0.75 will exclude any 3-way relationships with no 3-way intersection contribution. Thus, a threshold of 0.76 was applied to each network and visualized in Cytoscape [29] using an Allegro layout. These networks can be seen in SI and S2 Figs. Cytoscape can only visualize 2-way networks in the sense that it can only handle edges connecting 2 nodes. To our knowledge, no visualization software exists for 3-way networks. Thus, the 3-way network had to be transformed such that it could be visualized in Cytoscape. To do so, each 3-way-edge was represented by a node with degree 3, connected to the bacterial species nodes which the 3-way-edge connected. In the transformed network, each node thus either represented a bacterial species or a 3-way edge (referred to as an ‘edge-node’). A closeup of these Sway-edges can be seen in 53 Fig. A best-edge approach was also used to prune the 3-way networks. For each bacterial species node, the best and second best edges (edges with the highest and second highest weight) were selected. A network was constructed and transformed into a format which can be visualized in Cytoscape as described above. The resulting networks can be seen in Figs. 2 and 4. 2-way Network Construction

Let X,- and Y,- represent the ith element in column X and column Yin the SF-matriX (i.e. the number of members of gene family i in species X and species Y respectively. Let X B be the binary vector associated with vector X and YB be the binary vector associated with vector Y. For each pair of species (X, Y) the Sorensen Index was calculated using Equation 3 and the Czekanowski Index was calculated using Equation 8. These networks were pruned using two approaches, namely a Maximum Spanning Tree and best edge selection. The Maximum Spanning Tree was calculated by converting the network from a similarity network into a distance network by inverting the edge weights i.e. for each edge weight w the inverted edge weight w’ was calculated as

For best edge selection, the best and second best edge for each node was selected based on edge weight. These pruned networks were Visualized in Cytoscape [29] using an Allegro layout, and can be seen in Figs. 3a, 3b, 5a and 5b.

Combined 2-way and 3-way Network Construction

For both the Sorensen Index and the Czekanowski Index, the union of the 3-way best-edge network and the 2-way MST was calculated, resulting in a combined network model. These can be seen in S4 and SS Figs.

Gene Family Enrichment

A p-Value cutoff of 0.05 was used. Gene families which were enriched in more than one species (so-called shared-enriched families) were selected and a new network was constructed in which each node represented either a bacterial species or a gene family, and each edge connected a gene family to bacterial species in which it was enriched. The species were coloured according to their genera. The network was Visualized in Cytoscape [29] using an Allegro layout (Fig. 6).

Supporting Information

NCBI IDs. NCBI IDs for each of the 211 bacterial genomes. (PDF)

Measure of disagreement. Difference between the ratios of inbound over outbound edges (0;), as well as the difference between the reciprocal ratios (D?) for each genus in the 2-way and 3-way best edge networks. (PDF)

Network constructed by setting a 0.76 threshold for the 3-way Sorensen Network, and removing all 3-way edges below this threshold. threshold for the 3-way Czekanowski Network, and removing all 3-way edges below this threshold. (TIFF)

Closeup of a section of the thresholded 3-way network showing the 3-way edges. Large, coloured nodes represent bacterial species, Whereas small White nodes and their respective 3 edges represent 3-way edges connecting the bacterial nodes.

Network constructed by taking the union of the Sorensen 3-way Best Edge Network (Fig. 2) and the Sorensen MST

Network constructed by taking the union of the Czekanowski 3-way Best Edge Network (Fig. 4) and the Czekanowski MST (Fig. 5b).

Distributions of the 2-way and 3-way similarity metrics. (TIFF)

Acknowledgments

The authors would like to acknowledge The Centre for High Performance Computing and the Stellenbosch High Performance Computing Cluster for computing resources.

Author Contributions

Performed the experiments: DAW. Analyzed the data: DAW DA]. Contributed reagents/materials/ analysis tools: DAW DA]. Wrote the paper: DAW DA].