A review ofin silicoapproaches for analysis and prediction of HIV-1-human protein–protein interactions <s> Association rule mining-based approach 180 <s> In this paper, we address the problem of finding frequent itemsets in a database. Using the closed itemset lattice framework, we show that this problem can be reduced to the problem of finding frequent closed itemsets. Based on this statement, we can construct efficient data mining algorithms by limiting the search space to the closed itemset lattice rather than the subset lattice. Moreover, we show that the set of all frequent closed itemsets suffices to determine a reduced set of association rules, thus addressing another important data mining problem: limiting the number of rules produced without information loss. We propose a new algorithm, called A-Close, using a closure mechanism to find frequent closed itemsets. We realized experiments to compare our approach to the commonly used frequent itemset search approach. Those experiments showed that our approach is very valuable for dense and/or correlated data that represent an important part of existing databases. <s> BIB001 </s> A review ofin silicoapproaches for analysis and prediction of HIV-1-human protein–protein interactions <s> Association rule mining-based approach 180 <s> The set of frequent closed itemsets uniquely determines the exact frequency of all itemsets, yet it can be orders of magnitude smaller than the set of all frequent itemsets. In this paper, we present CHARM, an efficient algorithm for mining all frequent closed itemsets. It enumerates closed sets using a dual itemset-tidset search tree, using an efficient hybrid search that skips many levels. It also uses a technique called diffsets to reduce the memory footprint of intermediate computations. Finally, it uses a fast hash-based approach to remove any "nonclosed" sets found during computation. We also present CHARM-L, an algorithm that outputs the closed itemset lattice, which is very useful for rule generation and visualization. An extensive experimental evaluation on a number of real and synthetic databases shows that CHARM is a state-of-the-art algorithm that outperforms previous methods. Further, CHARM-L explicitly generates the frequent closed itemset lattice. <s> BIB002 </s> A review ofin silicoapproaches for analysis and prediction of HIV-1-human protein–protein interactions <s> Association rule mining-based approach 180 <s> Motivation: In recent years, there have been various efforts to overcome the limitations of standard clustering approaches for the analysis of gene expression data by grouping genes and samples simultaneously. The underlying concept, which is often referred to as biclustering, allows to identify sets of genes sharing compatible expression patterns across subsets of samples, and its usefulness has been demonstrated for different organisms and datasets. Several biclustering methods have been proposed in the literature; however, it is not clear how the different techniques compare with each other with respect to the biological relevance of the clusters as well as with other characteristics such as robustness and sensitivity to noise. Accordingly, no guidelines concerning the choice of the biclustering method are currently available. ::: ::: Results: First, this paper provides a methodology for comparing and validating biclustering methods that includes a simple binary reference model. Although this model captures the essential features of most biclustering approaches, it is still simple enough to exactly determine all optimal groupings; to this end, we propose a fast divide-and-conquer algorithm (Bimax). Second, we evaluate the performance of five salient biclustering algorithms together with the reference model and a hierarchical clustering method on various synthetic and real datasets for Saccharomyces cerevisiae and Arabidopsis thaliana. The comparison reveals that (1) biclustering in general has advantages over a conventional hierarchical clustering approach, (2) there are considerable performance differences between the tested methods and (3) already the simple reference model delivers relevant patterns within all considered settings. ::: ::: Availability: The datasets used, the outcomes of the biclustering algorithms and the Bimax implementation for the reference model are available at http://www.tik.ee.ethz.ch/sop/bimax ::: ::: Contact: bleuler@tik.ee.ethz.ch ::: ::: Supplementary information: Supplementary data are available at http://www.tik.ee.ethz.ch/sop/bimax <s> BIB003 </s> A review ofin silicoapproaches for analysis and prediction of HIV-1-human protein–protein interactions <s> Association rule mining-based approach 180 <s> Association rule mining and bi-clustering are data mining tasks that have become very popular in many application domains, particularly in bioinformatics. However, to our knowledge, no algorithm was introduced for performing these two tasks in one process. We propose a new approach called FIST for extracting bases of extended association rules and conceptual bi-clusters conjointly. This approach is based on the frequent closed itemsets framework and requires a unique scan of the database. It uses a new suffix tree based data structure to reduce memory usage and improve the extraction efficiency, allowing parallel processing of the tree branches. Experiments conducted to assess its applicability to very large datasets show that FIST memory requirements and execution times are in most cases equivalent to frequent closed itemsets based algorithms and lower than frequent itemsets based algorithms. <s> BIB004 </s> A review ofin silicoapproaches for analysis and prediction of HIV-1-human protein–protein interactions <s> Association rule mining-based approach 180 <s> Identification of potential viral-host protein interactions is a vital and useful approach towards development of new drugs targeting those interactions. In recent days, computational tools are being utilized for predicting viral-host interactions. Recently a database containing records of experimentally validated interactions between a set of HIV-1 proteins and a set of human proteins has been published. The problem of predicting new interactions based on this database is usually posed as a classification problem. However, posing the problem as a classification one suffers from the lack of biologically validated negative interactions. Therefore it will be beneficial to use the existing database for predicting new viral-host interactions without the need of negative samples. Motivated by this, in this article, the HIV-1–human protein interaction database has been analyzed using association rule mining. The main objective is to identify a set of association rules both among the HIV-1 proteins and among the human proteins, and use these rules for predicting new interactions. In this regard, a novel association rule mining technique based on biclustering has been proposed for discovering frequent closed itemsets followed by the association rules from the adjacency matrix of the HIV-1–human interaction network. Novel HIV-1–human interactions have been predicted based on the discovered association rules and tested for biological significance. For validation of the predicted new interactions, gene ontology-based and pathway-based studies have been performed. These studies show that the human proteins which are predicted to interact with a particular viral protein share many common biological activities. Moreover, literature survey has been used for validation purpose to identify some predicted interactions that are already validated experimentally but not present in the database. Comparison with other prediction methods is also discussed. <s> BIB005 </s> A review ofin silicoapproaches for analysis and prediction of HIV-1-human protein–protein interactions <s> Association rule mining-based approach 180 <s> Discovering Protein-Protein Interactions (PPI) is a new interesting challenge in computational biology. Identifying interactions among proteins was shown to be useful for finding new drugs and preventing several kinds of diseases. The identification of interactions between HIV-1 proteins and Human proteins is a particular PPI problem whose study might lead to the discovery of drugs and important interactions responsible for AIDS. We present the FIST algorithm for extracting hierarchical bi-clusters and minimal covers of association rules in one process. This algorithm is based on the frequent closed itemsets framework to efficiently generate a hierarchy of conceptual clusters and non-redundant sets of association rules with supporting object lists. Experiments conducted on a HIV-1 and Human proteins interaction dataset show that the approach efficiently identifies interactions previously predicted in the literature and can be used to predict new interactions based on previous biological knowledge. <s> BIB006 </s> A review ofin silicoapproaches for analysis and prediction of HIV-1-human protein–protein interactions <s> Association rule mining-based approach 180 <s> BackgroundDiscovering novel interactions between HIV-1 and human proteins would greatly contribute to different areas of HIV research. Identification of such interactions leads to a greater insight into drug target prediction. Some recent studies have been conducted for computational prediction of new interactions based on the experimentally validated information stored in a HIV-1-human protein-protein interaction database. However, these techniques do not predict any regulatory mechanism between HIV-1 and human proteins by considering interaction types and direction of regulation of interactions.ResultsHere we present an association rule mining technique based on biclustering for discovering a set of rules among human and HIV-1 proteins using the publicly available HIV-1-human PPI database. These rules are subsequently utilized to predict some novel interactions among HIV-1 and human proteins. For prediction purpose both the interaction types and direction of regulation of interactions, (i.e., virus-to-host or host-to-virus) are considered here to provide important additional information about the regulation pattern of interactions. We have also studied the biclusters and analyzed the significant GO terms and KEGG pathways in which the human proteins of the biclusters participate. Moreover the predicted rules have also been analyzed to discover regulatory relationship between some human proteins in course of HIV-1 infection. Some experimental evidences of our predicted interactions have been found by searching the recent literatures in PUBMED. We have also highlighted some human proteins that are likely to act against the HIV-1 attack.ConclusionsWe pose the problem of identifying new regulatory interactions between HIV-1 and human proteins based on the existing PPI database as an association rule mining problem based on biclustering algorithm. We discover some novel regulatory interactions between HIV-1 and human proteins. Significant number of predicted interactions has been found to be supported by recent literature. <s> BIB007
Mondal et al. (2012) BIB004 An integrated approach called FIST is proposed here for procuring association rules among HIV-1 and human proteins. Here FIST is used to coalesce biclustering and association rule mining technique in one process. Association rule mining-based approach 28 dependent on the availability of the biologically validated negative samples. In BIB005 , the authors have extended their work by using a biclustering technique for discovering association rules between both human and viral proteins. Two binary matrices of human and viral proteins, HV of size 1432 Â 19 and its transpose matrix VH of size 19 Â 1432 are built where an entry of '1' denotes the presence of interaction between the corresponding pair of human and HIV-1 proteins, and an entry of '0' represents the absence of any information regarding the interaction. For each of the matrices, a row is considered as a transaction and a column represents an item. In each transaction, the items for which the corresponding value in the matrix is 1 are considered to be purchased in that transaction. Now, the columns of all-1 biclusters, which are extracted from those matrices using Bimax algorithm, represent frequent closed itemset. The frequent itemsets are then used to generate association rules among human proteins and viral proteins separately. These rules basically guide the prediction task. In another approach BIB007 proposed by Mukhopadhyay et al., regulatory interactions are predicted by using association rule mining technique. Here all the interactions are partitioned based on the interaction type and direction of regulation. After partitioning, three different regulatory networks are formed based on the HIV-1-human interaction information. The interactions are predicted by considering each of the networks separately. As here each interaction has a specific interaction type and direction so, all the predicted interactions also inherit these information. The approach proposed in BIB006 also used the association rule mining technique for extracting frequent closed itemset for predicting PPIs between HIV-1 and human proteins. They proposed an integrated approach called FIST (Frequent Itemset Mining using Suffix Tree) that combines biclustering and association rule mining technique in a single process. The main feature of FIST is that it efficiently mines frequent closed itemsets, generates minimal non-redundant cover of association rules and generates hierarchical conceptual biclusters in one process. It was applied on the HHPID database for predicting some novel interactions. All these three approaches are apparently correlated with respect to the methodology they have used, but different techniques are used to mine the association rules. For example, the first work of Mukhopadhyay et al., the Apriori algorithm, is used for the purpose of finding association rules. But in case of low minimum support, large number of frequent itemsets is generated, which results in large computational complexity. Generation of such a large number of frequent itemsets takes huge time. In this context the concept of frequent closed itemset BIB001 BIB002 is used in BIB005 as an extension of first work. An itemset is called closed itemset if none of its proper supersets have the same support value. Here BiMax BIB003 biclustering algorithm is used to generate all maximal biclusters. As the columns of maximal biclusters represent a closed itemset, so all extracted biclusters satisfying a predefined minimum support condition provide the set of frequent closed itemsets. However, in Mondal et al. BIB006 , a frequent closed itemset framework is proposed for efficiently mining closed itemset. It is also used to find out the relationship between annotations and interactions by extracting association between proteins and features.