{'fraction_non_alphanumeric': 0.030456610088453264, 'fraction_numerical': 0.008893138895529524, 'mean_word_length': 4.482568807339449, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Discovering large network motifs from a complex biological network

Graph structures representing relationships between entries have been studied in statistical analysis, and the results of these studies have been applied to biological networks, whose nodes and edges represent proteins and the relationships between them, respectively. Most of the studies have focused on only graph structures such as scale-free properties and cliques, but the relationships between nodes are also important features since most of the proteins perform their functions by connecting to other proteins. In order to determine such relationships, the problem of network motif discovery has been addressed; network motifs are frequently appearing graph structures in a given graph. However, the methods for network motif discovery are highly restrictive for the application to biological network because they can only be used to find small network motifs or they do not consider noise and uncertainty in observations. In this study, we introduce a new index to measure network motifs called AR index and develop a novel algorithm called ARIANA for finding large motifs even when the network has noise. Experiments using a synthetic network verify that our method can find better network motifs than an existing algorithm. By applying ARIANA to a real complex biological network, we find network motifs associated with regulations of start time of cell functions and generation of cell energies and discover that the cell cycle proteins can be categorized into two different groups.

shows an example of a small network motif in a molecular biological system. The squares and lines indicate proteins and the relationships between two proteins, respectively. The upper sequence starting from the protein EGF is one of the well-known signal transduction pathways called the EGF pathway, which is closely related to cell growth. The lower sequence starting from the Wnt is the other well-known pathway associated with cancer. In this study, we have determined the network motifs by finding frequently appearing structures in these networks. The frequently appearing structures are shown at the bottom of Figure 1. The beginning of both pathways is marked by signal transduction proteins, that are connected to membrane proteins. The membrane proteins are linked to signal transduction proteins within cells, and finally, the signal transduction proteins are connected to DNA binding proteins. From this network motif structure, we can establish the general pathway of information flow within cells. Figure 2(A) shows a motivating example. The vertices represent proteins, and the edges represent the relationships between two vertices connected to the edge. Each number indicates their ID number. Each letter in the vertex indicates an attribute, i.e., the function, of the vertex. This example shows five types of attributes: A-E. Two vertices having the attribute "A" have the same function.
Here, we find the network motifs from Figure 2(A). Figure 2(B) shows a network motif of the example shown in Figure 2(A). In the figure, the squares with dotted lines represent groups of vertices (G1, G2, G3, and G4). Vertices 2 and 6 belong to G2, and the members of this group connect to the members of G1 and G3 because both vertices 2 and 6 connect to 1, 3, and 7. Therefore, G2 connects to G1 and G3 in the network motif. Further, vertices in G2 do not connect to vertices in G4, and hence, there are no edges between G2 and G4. Vertices in G3 also connect to vertices in G2 and G4 but do not connect to G1, and hence, in the network motif, G3 connects to G2 and G4 and does not connect to G1.
In this example, we can determine a network motif with no ambiguity. However, most graph structures representing real biological networks are subject to noise and uncertainty, and hence network motif cannot represent whose given network. In this study, we introduce a novel index to measure the network motifs even when the network includes noise and develop an algorithm to find network motifs by maximizing this index.

Related work
In recent years, graph mining has received increased attention from researchers. The frequent subgraph discovery methods [10,11,12,13] can be used to enumerate all frequently occurring common-structured subgraphs in a graph database. These algorithms cannot be used to find large frequently occurring subgraphs because of the noise present in biological networks. Our approach can enumerate large motifs networks from the entire protein-protein network.
Finding cliques is one of the research topics in network analysis. In the motivating example, nodes 2, 3, 6, and 7 form a clique. It is better to divide them into two groups -nodes 2 and 6 and nodes 3 and 7 -where the former two nodes connect to node 1 and the latter two connect to nodes 4 and 8. Because the two groups connect differently to the other groups, the method cannot apply to find network motifs.
Network motif discovery algorithms have been studied in the fields of both biology [8] and data mining [7,9]. In the field of biology, only some genes or proteins have been investigate at once [8]. Chen et al. [7] studied networks containing less than 25 genes, and their analysis was limited to graphs whose vertices did not have labels. k-SNAP [9] can handle large networks, but it cannot find motifs from networks having a large number of labels on the vertices. In contrast, our method can handle a large number of labels.

Attributes and relationships compatible grouping
In this section, we define a network motif model and introduce an optimization model that we attempted to maximize in this study. For finding network motifs, we define the grouping of vertices.

Definition 1 (Definition of a Graph) Let G = (V (G), E(G), A(G)) be an undirected and unweighted graph. Let V (G) and E(G) be vertices and edges on G, respectively. Let A(G)
be the attributes on vertices in graph G. Each vertex v has an attribute a(v) ∈ L(G). Edges do not have labels and weights. We refer to this graph as a labeled graph.
On this labeled graph, we define non-overlapping groups of vertices.
Next, we define a special kind of grouping on the basis of attributes.  Various A-compatible groupings can be generated from a graph. Here, we define a partial order relation on the set of all groupings of a graph and find an A-compatible grouping that has the minimum number of groups. Among all the A-compatible groupings of a graph, there exists a unique global maximum grouping with respect to the dominance relation [9].
A-compatible grouping only accounts for the vertex attributes. Vertices have not only attributes but also relationships with other nodes that are represented by edges. Next, we define groupings compatible with both attributes and relationships.

Definition 5 (Attributes and Relationships Compatible Grouping) Let
indicates a set of groups to which the neighbors of v belong. Let C be a group of vertices. When the grouping satisfies (A,R)-compatible grouping is that in which the nodes of each group are homogeneous in terms of attributes and relationships. Unfortunately, in practice, homogeneity is often highly restrictive because most graph representing real biological networks are subject to noise and uncertainty. (A,R)-compatible groupings with noise may increase the number of small groups. These small groups do not represent network motifs, because the network structure appears only few times in a given graph. To generate frequently appearing network structures, we introduce a novel index that relaxes the homogeneity requirement for both attributes and relationships and can be used to control the size of groups by means of a regularization term.

Network motif index
Here, we discuss the relaxation of homogeneity in attributes and relationships. First, we relax the attribute homogeneity using a relative entropy measure.

Definition 6 (Relaxing Attribute Homogeneity Requirement) Let p A (a) and p
This index can be used to measure the similarity between a grouping and an A-compatible grouping. When a grouping is A-compatible, C i ∈C Ent(C i ) is largest under the condition that |C| is fixed. As vertices in a group C i consist of different attributes, Ent(C i ) becomes small.
Next, we relax the homogeneity requirement for the relationships. We define a set of nodes in group C i that participate in a group relationship (C i , C j ) as V R (C i , C j ) and denote the participation ratio of the group relationship as r(C i , C j ).
As r(C i , C j ) increases, the strength of the group relationship increases. Note that in the case of an (A,R)-compatible grouping, the participation ratios between any two groups are either 0 or 1.
From the participation ratio, we measure the connectivity between two groups. When r(C i , C j ) is close to 0 or 1, the relationship between C i and C j is close to (A,R)-compatible grouping, and hence the grouping seems to include network motifs. On the other hand, when r(C i , C j ) is not close to 0 or 1, since the edges between groups are generated almost randomly, the grouping is undesirable. For considering this grouping, we define connectivity measure between the pair of groups.

Definition 8
Let c(C i , C j ) be the number of vertices relating the connection between C i and C j .
By treating the connectivity measure between groups as the weight of edges, we introduce an index to assess the grouping of vertices. The index is maximized when both the relative entropy of attributes and the connectivity measure between groups are large.

Definition 9 (Definition of Attribute Relationship Index) Let C be a grouping of vertices. Let w(C) be
We call w(C) an attribute relationship index, or in short, an AR index.
The last term of the AR index is a penalty term, which accounts for the increase in the index as the number of groups increases. We can regulate the cluster size by using λ. When λ is small, the group size reduces.
We use this AR index and define our optimization problem, which is to find the grouping that maximizes the index. We call this problem Attribute Relationship Index ANAlysis (ARIANA). Then, we find network motifs by using the pair of groups having a high participation ratio.
However, it is difficult to find the grouping that maximizes the AR index, and hence, we introduce a simple method to find the better grouping of a graph in the next section.

Method
Here, we introduce an algorithm to solve the ARIANA problem. Since it is difficult to find a grouping that maximizes w(C), we introduce a new two-step algorithm. Then, we apply the algorithm to a real biological dataset.
Our algorithm includes an aggregation step and a division step. We start with the maximum A-compatible grouping in terms of dominance relation between groups (Definition 4). In the Compute cos(C i , C j ) for all pairs of C i , C j ∈ C.

5:
Find a pair of groups that minimizes cos(C i , C j ).

6:
Remove C i and C j from C and add a new group consisting of C i ∪ C j to C. 7: end for 8: // Division step. 9: for while |C| ≤ K do 10: max w ← 0 11: for each pair of C i , C j ∈ C do 12: C ← C where C is the grouping associated with max w. 17: end for 18: return C.
aggregation step, we merge the groups into J groups by using the following cosine distance measure: This measure gives the similarity between two groups in terms of distribution of connectivity to other groups. We merge the groups with the largest pair of cosine distance, i.e., we perform complete linkage clustering until the number of clusters is J using cos(C i , C j ). In this step, we can generate groups whose members do not have attribute homogeneity but have relationship homogeneity. Next, we maximize the AR index by dividing the groups. In this step, we divide groups whose members have attribute homogeneity but do not have relationship homogeneity into some groups to satisfy relationship as homogeneous as possible. When we divide an attribute homogeneous group into two groups, both of them keep attribute homogeneity. Therefore, we only consider relationship homogeneity to divide a group into two groups.
Let us consider the division of group C i into two groups C and C i − C . To maintain the relationship as homogeneous as possible, we select members of C to connect it to the other group. When we divide C i into C and C i − C using C j , we select C as For all pairs of C i and C j ∈ C, we find the best division having the maximum AR index.
Algorithm 1 shows the pseudo-code of ARIANA. In the first line, we make the maximum Acompatible groups in terms of dominance relations, and |C| is the number of types of attributes. In lines 2 to 7, groups are merged until the number of groups is J. In line 8 to 17, the groups are divided by the grouping that maximize the AR index until the number of groups is K.
Although ARIANA requires parameters J and K, both of which are associated with the number of clusters, we can change these two values, and find the best division that maximizes the AR index on the real biological dataset.

Results for a synthetic dataset
Here, we test our algorithm using a synthetic dataset. First, we generate a synthetic dataset consisting of 400 vertices, 1200 edges and 20 attributes. This procedure generate relationship compatible network consists of 20 groups. Within the groups, 10 groups consist of a single attribute; that is, attribute homogeneous. However, the other 10 groups consists of two different attributes.
Then, we add noise to the network.
(i) Let r be user-specified noise ratio.
(ii) Select 400 × r nodes randomly and change their attributes randomly.
(iii) Select 1200 × (r/5) edges randomly and remove the edges from the existing graph.
(iv) Add 1200 × (r/5) edges between randomly selected two vertices to the existing graph.
We compare AR indexes computed by ARIANA to that by k-SNAP [9], which first make A-compatible grouping and then divide the groups until the number of groups is k. In this experiments, we set the number of groups as 20 on both algorithms. To calculate AR index, we set λ as 0. Figure 3 shows AR index values by changes of noise. ARIANA and k-SNAP indicate AR index values calculated by the algorithms. Initial grouping indicates AR index value just after the noise is added to graph and before we do ARIANA or k-SNAP.
According to the increase of noise, AR indexes of any groupings become gradually low. In all noise levels, AR indexes computed by ARIANA are larger than those by k-SNAP, and hence, ARIANA find the better grouping than k-SNAP. When noise level is low, AR indexes of k-SNAP are lower than those of the initial groupings because attribute homogeneity in k-SNAP is too restrictive to find relationship homogeneous grouping. On the other hand, ARIANA can find the better grouping than initial grouping in terms of AR index. When noise level is high, the k-SNAP grouping is better than initial grouping. In this case, grouping of ARIANA is still better than that of k-SNAP. From these result, ARIANA is shown to be able to correct the attribute and relationship noise. Figure 4 shows the number of clusters on the aggregation step when the best AR indexes are computed. For example, when r = 1, we can understand that ARIANA merge groups until the number of cluster is 14 and then divide the groups until the number of cluster is 20 when the maximum AR index is found. In all cases except r = 0 (no noise), ARIANA merge some groups then dividing the groups. This observation verifies the effectiveness of both merge step and division step in ARIANA.

Results for a real biological network
We apply our algorithm to real biological dataset. We use iRefIndex [14] as the target network, which is a protein network aggregated from several sources, and the attributes on vertices are pathways to which genes belong. The nodes and edges indicate proteins and the relationships between them, respectively. In this dataset, the numbers of nodes, number of edges, and number of attributes are 1,184, 9,807, and 221, respectively. We calculate the maximum w(C) using ARIANA as described in Section 4. ARIANA uses user-specified values: the number of clusters in the aggregation step, J; the number of final clusters, G; and coefficient of normalization term, λ. Here, we only fix the value of λ, and determine J and G by using various values of w(C). We change the values of J and G from 10 to 300, independently. Figure 5 shows the number of clusters and its max w(C) with a change in λ. This figure shows that the number of clusters is large when λ is small, an vice versa. Therefore, by setting the value of λ, we can control the size of clusters. Because of the limitation that k-SNAP can find the clusters only when the number of clusters is more than the number of attributes, k-SNAP cannot find the clusters we found when λ > 20. Figure 6 shows the network motif when λ = 40. For this value of λ, we generate 30 groups in the aggregation step, and finally generate 65 groups. The nodes and edges in the figure indicate groups and relationships with a high participation ratio, respectively. The figure shows only the nodes containing a minimum of five proteins and the edges for which the relationship has r(C i , C j ) ≥ 0.80. The number of edges in the figure is 22. The group size indicates the number of proteins in the group; the larger nodes contain a larger number of proteins. The numbers in the nodes represent its node ID.
Here, we check the biological functions of this network. Detail of associated pathways with the groups are described in http://lab.se-se.jp/~sesejun/large net motif.html. The figure shows a large connected component. The component contains basic biological processes: cell cycles (regulation of time of cells), ribosomes (protein generation) and purine and pyrimidine metabolisms (nucleotide metabolisms). On the other hand, single nodes include pathways working only on the specific case such as DNA replication (Replication of DNA damages) and glycan biosynthesis. From this result, we confirm that basic biological processes are highly related to each other.
Node 1 at the upper-left of the left most connected component has a hub node, which is associated with cell cycle. Cell cycle proteins are known to regulate the start time of cell functions. Moreover, the proteins are significantly associated with GO term "DNA-dependent DNA replication" (Binomial test P -value = 2.8e-6, two-sided), which means that the genes assocate with start time of cell division and connect to various cellular processes. Hence, results of this study are in agreement with common biological knowledge. Proteins in Node 51 connected to Node 1 are also associated with cell cycle but the node is only connected with Node 1 and 31. The process is associated with GO term "metabolic process" (Binomial test 5.26e-5, two-sided). This result indicates that the role of cell cycle related proteins can be categorized into more than two groups by our method: one related to DNA replication showing association with various functions and other related to metabolic process showing little association.
Node 54 is associated with both purine metabolism and pyrimidine metabolism. Both the metabolisms are known to have a similar function about metabolism of different nucleotides. Our method classified the two different but having similar function metabolisms into the same groups. The above observations are consistent with the known facts about the involved pathways.
Thus, our method can be successfully used to extract biologically significant network motifs.

Concluding remarks and future work
Network motif discovery is gaining importance in the field of both statistical analysis and biology.
The problem with the existing methods is that they cannot handle noise and uncertainty in a given graph. In this study, we developed a novel algorithm called ARIANA to find large network motifs even when the network has noise and uncertainty. By applying ARIANA to a real biological network, we found network motifs associated with regulation of cell time and discovered that the role of ribosomes can be categorized into two different groups. Although our result showed that our method practically succeeded in the analysis biological network, our index is no ground theory on statistics and information theory. In a future study, we intend to curry out a theoretical analysis of the AR index. In addition, we intend to develop on algorithm to find the best grouping. We introduced a simple two step algorithm, but the result may not maximize AR index. By the improvements of the algorithm, we compute the better graph in terms of AR index.
This network motif discovery problem can be applied not only to biological network but also to the Web and economic networks. Application of this study will show the new visualization and understanding of large complex networks.