Introduction

Protein-Protein interaction networks have essential position in cell biology to conduct an organism analysis. The protein complex transformation understanding in disease condition is important in modern system biology [ 1 ]. From a biological point of view, protein complexes are the molecular entities to do the cellular functionalities such as DNA transcription, signal transduction, mRNA translation [ 2 ]. Recently, in order to analyze the dynamicity of PPINs, dynamic PPI network is studied [ 3 ]. DPPINs are constructed either by simulated the proteins activities or aggregated the co-regulated proteins at different time points [ 4 ]. Under different conditions and various cellular cycles, the protein activation can be restored by assigning a threshold value for gene expression.

There are structural changes during protein complex formation in different time points and conditions [ 5 ]. Simple models cannot demonstrate these changes; thus, we proposed fuzzy temporal association rule mining to handle these changes. The temporal rules are used to understand and extract knowledge from dynamicity of PPINs and protein complexes. The mining of association rules is applied to discover the interest relations between items of transactions. Association rule mining algorithms can find relations among genes and different biological entities in bioinformatics [ 6 ]. The traditional association rules mining algorithms extract the associations among items within the concurrent transaction named intra-transaction association rules. Moreover, the rules among items from different transactions are called inter-transaction association rules [ 7 , 8 ]. Most of microarray gene expression datasets are dense that have infrequent experiments versus most genes at each experiment with different experiment time points [ 9 ]. There are many long repeated itemsets in dense datasets. The frequent itemset extraction in dense transactions has large computational time complexity [ 10 ]. Moreover, one of the major difficulties in inter-transaction association rules mining is the larger search space, and the larger number of possible generated rules in compare to classical association rules mining algorithms [ 8 ]. Hence, we need an approach to reduce the number of items and cut the search space.

Protein complexes are considered in new drugs design for treating complex diseases. Nacher et al. [ 11 ] presented relation of protein complexes with associated drugs. Ray et al. [ 12 ] developed MODAPROC framework to detect protein complexes with associated human diseases. The number of outward interactions and protein complex associated disease is used as objective functions in a multi-objective optimization problem. Moarefi [ 13 ] presented some examples of relevant protein complexes usage for rational drug discovery. MUTARC, as a new algorithm, is presented to find pairwise unexpected temporal association rules (UTARs) [ 14 ] in adverse drug reactions. Steinway et al. [ 15 ] proposed a discrete dynamic modeling to uncover the relation of disease and drug targets in the proteins network.

Interaction annotation differences are captured by differential association rule mining in protein-protein interactions [ 16 ]. Nam et al. [ 9 ] presented a temporal association rule mining algorithm for continuous microarray data values. After discretization, the temporal transactions are obtained by the combination of different transaction items based on time delay. Gallo et al. [ 17 ] introduced a machine learning approach for mining time-lagged rules from gene expression data to determine interactions among genes.

Chen et al. [ 18 ] introduced a dynamic method to mine association rules called DAR based on the market basket analysis. His proposed method exhibits the relationship between diseases and genes. Besides, traditional methods of association rule mining, the fuzzy and temporal association rule mining has been used to extract efficient rules. Mohammadi et al. [ 19 ] proposed an ensemble-based approach to detect co-behavioral genes in multiple gene expression profiles.

Mega-transactions and extended itemsets have been used by some researchers [ 20 - 23 ] to extract temporal association rules. Tung et al. [ 22 ] used mega-transactions and extended itemsets to implement the FITI algorithm to extract the frequent inter-transaction itemsets [ 20 ]. Baralis et al. [ 24 ] used time delayed matrix to extract temporal association rules from gene regulatory networks. Besemann et al. [ 16 ] described a differential association rule mining algorithm for protein-protein interaction networks.

Material and Methods

In this analytical study, the relation between protein complexes is extracted. The Figure 1 illustrates the proposed method briefly. The proposed method has several well-separated steps that will be described in the next sections.

Figure 1. Algorithmic overview of proposed method

Create dynamic PPI networks

As discussed earlier, systematic analysis of dynamic protein complexes not only optimizes the detection precision of the protein complexes but also improves our understanding of the dynamic process of biological protein formation for organizing cells [ 25 ]. The dynamic PPI network is formed according to G and Ge graphs as transitory interactions and simultaneous activeness of the two related proteins [ 26 ]. The protein absence or presence at time point t is determined by its gene expression value and its corresponding defined threshold value (AT(i)).

Threshold values, according to 3σ method [ 26 ], are defined by following equations 1, 2:

$\mathrm{AT}\left(i\right)=u\left(i\right)+3\sigma \left(i\right)(1-F(i\left)\right)$ (1)

$F\left(i\right)=1/(1+{\sigma }^2(i\left)\right)$ (2)

Where u and σ are the gene expression mean and standard deviation, respectively. In this step, the static PPI network is converted to dynamic network according to the defined threshold values.

Reference protein complexes

Protein complex is a set of proteins Pi. This definition is equivalent to the basic definition of an item used in association rule mining. Gold standard protein complexes are considered as reference complexes. Since, all correspond proteins of each complex are not active at all-time points of dynamic network; the absence or presence of each protein complexes is weighted based on their active proteins.

Extend transactions to Mega-transactions

Bitmap Matrix

The base idea in a bitmap matrix is to define two types of events and to use them as extended items. The first event identifies the items appearing exactly after N steps, and the second event identifies the items disappearing exactly after N steps. To create a bitmap matrix, the weight of items is considered, and only the items with weight greater than specific bound give value 1 and elsewhere the item value will be 0 in the corresponding entry to express the presence or absence of the item in the transaction. Each column indicates the reference protein complexes and each row represents the transactions. PCBM_t,i shows the absence or presence of item i in transaction t. The bitmap matrix of transactions shown in Table 1 are indicated in Table 2.

Extended Item

Maxspan is the maximum number of transactions from reference transaction that must be investigated to produce extended items.

Let RPC is an item in a transaction database. The extended item ERPC in transaction t, with time_span ≤ maxspan, is defined as below.

In formula 3, δ indicates the smallest (n+1)-digit number where n is the digits count of reference protein complexes. For example, if the number of reference protein complexes is 235, δ will be 1000 in equations 3. The ERPC extension is done for all time_span’s from 1 to maxspan. Some examples of extended items have been expressed in Table 3.

$\mathrm{ERPC}=\{\begin{array}{}\mathrm{RPC}\times \delta +{\mathrm{time}}_{\mathrm{span}}\times 10+1\mathrm{if}{\mathrm{PCBM}}_{\mathrm{t+ts}-1,i}=0\forall \mathrm{ts}=1{\mathrm{time}}_{\mathrm{span}}-1\mathrm{and}{\mathrm{PCBM}}_{t+{\mathrm{time}}_{\mathrm{span},i}}=1\\ \mathrm{RPC}\times \delta +{\mathrm{time}}_{\mathrm{span}}\times 10+0\mathrm{if}{\mathrm{PCBM}}_{\mathrm{t+ts}-1,i}=1\forall \mathrm{ts}=1{\mathrm{time}}_{\mathrm{span}}-1\mathrm{and}{\mathrm{PCBM}}_{t+{\mathrm{time}}_{\mathrm{span},i}}=0\\ ø\mathrm{o.w}\end{array}$ (3)

Extended mega-transaction

An extended mega-transaction is the union of extended items with normal transaction items set in that transaction. Table 3 shows the extended mega-transaction with maxspan 3.

In the worst case, for each desired maxspan, the number of items per transaction will be equal to the total number of its items and all available items. For any maxspan, all time intervals from one to maxspan are investigated.

As shown in Table 3, extended items are added to the transactions. The quotient of the extended item after dividing by thousand and the remaining number by deleting three digits to the right of the number specifies the original item related to extended item. The tens digit of extended item specifies the event occurrence step, and the ones digit determines the event type. Events 0 and 1 are equivalent to disappearing and occurrence, respectively. For example, item <4021> expresses that the item 4 emerges after two time steps.

Temporal association rule mining

Apriori algorithm

Apriori [ 27 ] is an algorithm for association rule mining from transactional databases. After pre-processing and determining the mega-transactions, the Apriori algorithm for our data is used. The support measure of items set is defined according to equation 4.

$\mathrm{supp}\left(X\right)=\frac{|t\in \mathrm{EMT};X\subseteq t|}{\left|\mathrm{EMT}\right|}$ (4)

Which X is an item set; |EMT| is the number of extended mega-transactions. The support of association rule, X ⇒ Y in transactions T, is equal to supp (X ∪ Y). Moreover, the confidence coefficient of X ⇒ Y is computed by equation 5.

$\mathrm{conf}(X\Rightarrow Y)=\frac{\mathrm{supp}(X\cup Y)}{\mathrm{supp}\left(X\right)}$ (5)

Datasets

BioGRID is an integrated and continuous dataset updating the physical and general reactions [ 28 ]. This set includes more than 544000 interactions and more than 27 different organisms. Having 55000 non-repetitive interactions of yeast (version 3.1.77), this database is considered as the largest PPI set for this organism.

GEO (Gene Expression Omnibus): gene expression levels at different points are measured and stored in a dataset. For example, GSE3431 has 12 time spots from the GPL90 platform. 6777 levels of gene expression have been measured. The used PPI data in this study are Biogrid, DIP and YeastNet datasets. Furthermore, the information related to gene expression and co-expression has been taken from GEO [ 29 , 30 ].

The proposed method has been analyzed using the yeast Saccharomyces cerevisiae dataset. In used data, the frequently filtered genes [ 31 ] as many as 3552 genes were used. Table 4 gives some details of the gene expressions. The total number of transactions according to aggregate data in Table 4 is 623.

Results

The European Bioinformatics Institute (EMBL-EBI) supports research of bioinformatics through the provision of data, open source software, analytical tools, and technical infrastructure [ 32 ]. This institute has integrated a diverse range of data types to be used by biologists in all disciplines. The amount of data stored has been doubled in less than two years and reached 120 petabytes. One of the proven sources of gene product interpreting is the gene ontology (GO) [ 33 ]. QuickGO is a fast and web-based tool for the GO browsing and all interpreting of the functional information of gene products [ 34 ]. Furthermore, QuickGO is able to provide many features such as the relationship between functional modules, the modules’ children, ancestor charts of modules and co-occurrence expressions. An example of the ancestor chart has been shown in Figure 2.

Figure 2. Ancestor chart of Trapp complex drown with QuickGO (Figure reproduced from Huntley RP, et al. Nucleic Acids Research. 2015;43(D1):D1057-63. [ 34 ])

A dataset, consisting of known complexes, has been collected from QuickGo. In this dataset, the related complexes existing in the ancestor charts and the co-occurrence events have been aggregated to evaluate the extracted association rules. The known gold standard complexes have been considered as reference complexes, and the results have been investigated to better evaluation of the proposed algorithm. In this case, the corresponding subnets to each reference complexes have been determined in the dynamic protein interaction network. The similarity of a subnet to reference complexes as weight has been calculated according to equation 6.

$\mathrm{sim}(C,P^t)=|C\cap P^t|/\left|C\right|$ (6)

P^t are the active proteins at the time point t, and C is the reference complexes. The total number of reference complexes determined from the gold standard complexes is 119.

281 rules have been extracted from the Biogrid dataset with 0.2 minimum support value and The bound (0.5), which matched with ancestor chart of EBI data. After filtering the redundant rules, 193 rules remained so that 152 rules matched with EBI data by mediation and 4 rules matched directly.

The bound (0.5) specifies the minimum overlap between the active proteins of the time point and the proteins of reference complexes. The matching rate has been measured in non-intermediate and intermediate modes. In the non-intermediate (directly) mode, if the consequent section of the rule is present in the ancestor chart of the antecedent, the matching has been made. In the intermediate mode, the consequent and antecedent complexes matching has been measured by the relation of them with intermediate complex in the different ancestor charts.

Also, the co-occurrence of antecedent and consequent of rules in EBI data have been used for evaluation. The antecedent and consequent of rules have 16 co-occurrences without intermediaries, while the number of intermediate co-occurrences is 173. The results show that the extracted rules by the proposed method are informative.

According to direct matching method, four rules coincide with the ancestor chart of EBI. The information of these rules, including the names of the antecedent and the consequent complexes and complexes’ GO_ID, has been listed in Table 5.

A sample ancestor chart of an extracted rule in the EBI database has been expressed in Figure 3.

Figure 3.The ancestor chart of gene ontology (GO):0005671 protein complex (Figure reproduced from Huntley RP, et al. Nucleic Acids Research. 2015;43(D1):D1057-63. [ 34 ])

Discussion

Finding relationships between different intracellular functions is a critical factor in the cell dynamicity recognition and modeling of overall cell function. Data mining and data aggregation techniques provide powerful tools for recognizing these relationships. In this study, temporal association rule mining methods are used to determine the association of protein complexes. The use of gene expression microarray data, collecting under different conditions and times, and linking this data to other available data such as protein interaction networks and protein complexes is one of the strengths of the proposed method. Since the extraction of temporal association rule has not been done in a set of protein complexes before the results and achievements of the proposed method have not been compared with any other methods. There are limited evaluation measures for the analysis of extracted biological knowledge from DPIN. On the other hand, to evaluate the network, the biological interpretation of DPINs is important. Identification of various protein complexes with different functionality and extraction of regular interactions between them is possible through a high-quality DPIN. Therefore, a criterion should be designed to evaluate the quality of DPINs and the quality of the relationships extracted from them. Our analysis shows that the use of EBI data is a good criterion for analyzing the relationship between complexes in a meaningful way. Many of the extracted relationships are without biological analysis due to the lack of an evaluation reference. Some of the extracted relationships and their biological analysis is given below.

Our proposed method has extracted the temporal relationship between the complexes GO:0005671 and GO:0000123. GO:0005671 is a multi-protein complex containing histone acetyltransferase HAT (GO:0000123) and involved in transcription regulation. The budding yeast complex contains Gcn5p, two Ada family proteins, and two TBP-linked proteins (TAFs). Moreover, GO:0019005 is a ubiquitin ligase complex in which a Cullin subfamily of the Cul1 family and a RING domain protein form a catalytic nucleus; substrate properties are provided by an Skp1 adapter and an F-box protocol. SCF complexes are involved in targeting proteins for proteasome degradation. The best identified compounds are yeast and mammals (with nuclear subsets called Cdc53 / Cul1, Rbx1 / Hrt1 / Roc1). GO:0000124 is a complex of SAGA acetone histone acetyltransferase HAT (GO:0000123) containing Spt8 (in yeast). The COMA complex is responsible for the connection between the centromere and the Kinetochore. Kinetochore is a complex of different proteins that bind to the centromere and some of the spindle strands to this protein structure.

Conclusion

As shown in the presented ancestor charts, cellular components such as protein complexes are related to cellular activities. In this paper, a method to discover the dynamic protein-protein interaction networks was proposed to extract temporal association rules based on protein complex relations. Dynamic protein interaction network is constructed from static one by gene expression thresholding. Gold standard protein complexes arranged as reference protein complexes to create temporal transactions. Mega-transactions were created by extended items to extract temporal rules. The results comparison with extracted EBI data showed that the extracted rules were informative and the elements of the rules were bio-related.

Authors’ Contribution

All members of our team have different contributions to the research work. More specifically, Moslem Mohammadi and Majid Iranpour designed and performed the experiments, Hossein Ebrahimpour supervised the work and helped analyzed the experimental results. All the authors read, modified, and approved the final version of the manuscript.

Conflict of Interest

None

References

1. Zaman E. Disease Similarity Using Biological Module Dysregulation Profile. North Dakota State University; 2016. https://library.ndsu.edu/ir/handle/10365/25887.
2. Taheri G, Habibi M, Wong L, Eslahchi C. Disruption of protein complexes. Journal of Bioinformatics and Computational Biology. 2013; 11(3):1341008. DOI | PubMed
3. Shen X, Yi L, Jiang X, He T, Hu X, Yang J. Mining temporal protein complex based on the dynamic pin weighted with connected affinity and gene co-expression. PloS One. 2016; 11(4):e0153967. DOI
4. Zhang Y, Du N, Li K, Feng J, Jia K, Zhang A. Critical protein detection in dynamic PPI networks with multi-source integrated deep belief nets. IEEE International Conference on Bioinformatics and Biomedicine. IEEE: Shanghai, China; 2013. DOI
5. Morra G, Genoni A, Colombo G. Protein dynamics and drug design: The role of molecular simulations. Protein-protein Complexes. 2010;340-85. DOI
6. Mallik S, Mukhopadhyay A, Maulik U. RANWAR: rank-based weighted association rule mining from gene expression and methylation data. IEEE Transactions on Nanobioscience. 2014; 14(1):59-66. DOI
7. Wani G, Joshi M. Quantitative estimation of time interval of 3-sequences. 5th International Conference on Reliability, Infocom Technologies and Optimization (Trends and Future Directions)(ICRITO). IEEE: Noida, India; 2016. DOI
8. Lu H, Han J, Feng L. Stock movement prediction and n-dimensional inter-transaction association rules. ACM SIGMOD Workshop on Research Issues on Data Mining and Knowledge Discovery. ACM: New York, USA; 1998.
9. Nam H, Lee K, Lee D. Identification of temporal association rules from time-series microarray data set: temporal association rules. Proceedings of the 2nd international workshop on Data and text mining in bioinformatics. Association for Computing Machinery: New York, NY, United States; 2008. DOI
10. Zakaria W, Kotb Y, Ghaleb F. MCR-Miner: Maximal confident association rules miner algorithm for up/down-expressed genes. Applied Mathematics & Information Sciences. 2014; 8(2):799-809. DOI
11. Nacher JC, Schwartz JM. Modularity in protein complex and drug interactions reveals new polypharmacological properties. PloS One. 2012; 7(1):e30028. DOI
12. Ray S, Hossain A, Maulik U. Disease associated protein complex detection: a multi-objective evolutionary approach. 2016 International conference on microelectronics, computing and communications (MicroCom). IEEE: Durgapur, India; 2016. DOI
13. Moarefi I. Protein Complex Production from the Drug Discovery Standpoint. Adv Exp Med Biol. 2016; 896:3-13. Publisher Full Text | PubMed
14. Jin H, Chen J, He H, Williams GJ, Kelman C, O’Keefe CM. Mining unexpected temporal associations: applications in detecting adverse drug reactions. IEEE Trans Inf Technol Biomed. 2008; 12(4):488-500. DOI
15. Steinway SN, Wang RS, Albert R. Discrete dynamic modeling: a network approach for systems pharmacology. Springer: Cham; 2016.
16. Besemann C, Denton A, Yekkirala A. Differential association rule mining for the study of protein-protein interaction networks. Proceedings of the 4th International Conference on Data Mining in Bioinformatics. Springer-Verlag: Berlin, Heidelberg; 2004.
17. Gallo CA, Carballido JA, Ponzoni I. Discovering time-lagged rules from microarray data using gene profile classifiers. BMC Bioinformatics. 2011; 12(1):123. DOI
18. Chen SC, Tsai TH, Chung CH, Li WH. Dynamic association rules for gene expression data analysis. BMC Genomics. 2015; 16(1):786. DOI
19. Mohammadi-Jenghara M, Ebrahimpour-Komleh H. Extraction of Co-Behaving Genes by Similarity Ensembles. Journal of Biological Systems. 2017; 25(03):479-94. DOI
20. Zhou A, Zhou S, Jin W, Tian Z. Generalized multidimensional association rules. Journal of Computer Science and Technology. 2000; 15(4):388-92. DOI
21. Lee AJ, Wang CS, Weng WY, Chen YA, Wu HW. An efficient algorithm for mining closed inter-transaction itemsets. Data & Knowledge Engineering. 2008; 66(1):68-91. DOI
22. Tung AK, Lu H, Han J, Feng L. Breaking the barrier of transactions: Mining inter-transaction association rules. Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining. ACM: New York, USA; 1999. DOI
23. Li Q, Feng L, Wong A. From intra-transaction to generalized inter-transaction: Landscaping multidimensional contexts in association rule mining. Information Sciences. 2005; 172(3-4):361-95. DOI
24. Baralis E, Bruno G, Ficarra E. Temporal association rules for gene regulatory networks. 4th International IEEE Conference Intelligent Systems. IEEE: Varna, Bulgaria; 2008. DOI
25. Jenghara MM, Ebrahimpour-Komleh H, Parvin H. Dynamic protein–protein interaction networks construction using firefly algorithm. Pattern Analysis and Applications. 2018; 21(4):1067-81. DOI
26. Wang J, Peng X, Li M, Luo Y, Pan Y. Active protein interaction network and its application on protein complex detection. International Conference on Bioinformatics and Biomedicine. IEEE: Atlanta, USA; 2011. DOI
27. Agrawal R, Srikant R. Fast algorithms for mining association rules. Proceedings of the 20th International Conference on Very Large Data Bases. Morgan Kaufmann Publishers Inc: San Francisco, CA, USA; 1994.
28. Chatr-Aryamontri A, Oughtred R, Boucher L, et al. The BioGRID interaction database: 2017 update. Nucleic Acids Res. 2017; 45(D1):D369-79. Publisher Full Text | DOI | PubMed
29. Edgar R, Domrachev M, Lash AE. Gene Expression Omnibus: NCBI gene expression and hybridization array data repository. Nucleic Acids Research. 2002; 30(1):207-10. DOI
30. Barrett T, Wilhite SE, Ledoux P, Evangelista C, et al. NCBI GEO: archive for functional genomics data sets—update. Nucleic Acids Research. 2012; 41(D1):D991-5. DOI
31. Rustici G, Mata J, Kivinen K, Lió P, Penkett CJ, et al. Periodic gene expression program of the fission yeast cell cycle. Nature Genetics. 2004; 36(8):809-17. DOI
32. Cook CE, Bergman MT, Cochrane G, Apweiler R, Birney E. The European Bioinformatics Institute in 2017: data coordination and integration. Nucleic Acids Research. 2018; 46(D1):D21-9. DOI
33. Dolinski K, Dwight SS, Eppig JT, Harris MA, et al. Gene ontology: tool for the unification of biology. Nat Genet. 2000; 25(1):25-9. Publisher Full Text | DOI | PubMed
34. Huntley RP, Sawford T, Mutowo-Meullenet P, Shypitsyna A, et al. The GOA database: gene ontology annotation updates for 2015. Nucleic Acids Research. 2015; 43(D1):D1057-63. Publisher Full Text | DOI | PubMed