A Survey on Personalized PageRank Computation Algorithms <s> E. BIOINFORMATICS <s> BackgroundSeveral studies have demonstrated that synthetic lethal genetic interactions between gene mutations provide an indication of functional redundancy between molecular complexes and pathways. These observations help explain the finding that organisms are able to tolerate single gene deletions for a large majority of genes. For example, system-wide gene knockout/knockdown studies in S. cerevisiae and C. elegans revealed non-viable phenotypes for a mere 18% and 10% of the genome, respectively. It has been postulated that the low percentage of essential genes reflects the extensive amount of genetic buffering that occurs within genomes. Consistent with this hypothesis, systematic double-knockout screens in S. cerevisiae and C. elegans show that, on average, 0.5% of tested gene pairs are synthetic sick or synthetic lethal. While knowledge of synthetic lethal interactions provides valuable insight into molecular functionality, testing all combinations of gene pairs represents a daunting task for molecular biologists, as the combinatorial nature of these relationships imposes a large experimental burden. Still, the task of mapping pairwise interactions between genes is essential to discovering functional relationships between molecular complexes and pathways, as they form the basis of genetic robustness. Towards the goal of alleviating the experimental workload, computational techniques that accurately predict genetic interactions can potentially aid in targeting the most likely candidate interactions. Building on previous studies that analyzed properties of network topology to predict genetic interactions, we apply random walks on biological networks to accurately predict pairwise genetic interactions. Furthermore, we incorporate all published non-interactions into our algorithm for measuring the topological relatedness between two genes. We apply our method to S. cerevisiae and C. elegans datasets and, using a decision tree classifier, integrate diverse biological networks and show that our method outperforms established methods.ResultsBy applying random walks on biological networks, we were able to predict synthetic lethal interactions at a true positive rate of 95 percent against a false positive rate of 10 percent in S. cerevisiae. Similarly, in C. elegans, we achieved a true positive rate of 95 against a false positive rate of 7 percent. Furthermore, we demonstrate that the inclusion of non-interacting gene pairs results in a considerable performance improvement.ConclusionWe presented a method based on random walks that accurately captures aspects of network topology towards the goal of classifying potential genetic interactions as either synthetic lethal or non-interacting. Our method, which is generalizable to all types of biological networks, is likely to perform well with limited information, as estimated by holding out large portions of the synthetic lethal interactions and non-interactions. <s> BIB001 </s> A Survey on Personalized PageRank Computation Algorithms <s> E. BIOINFORMATICS <s> BackgroundWe propose an efficient and biologically sensitive algorithm based on repeated random walks (RRW) for discovering functional modules, e.g., complexes and pathways, within large-scale protein networks. Compared to existing cluster identification techniques, RRW implicitly makes use of network topology, edge weights, and long range interactions between proteins.ResultsWe apply the proposed technique on a functional network of yeast genes and accurately identify statistically significant clusters of proteins. We validate the biological significance of the results using known complexes in the MIPS complex catalogue database and well-characterized biological processes. We find that 90% of the created clusters have the majority of their catalogued proteins belonging to the same MIPS complex, and about 80% have the majority of their proteins involved in the same biological process. We compare our method to various other clustering techniques, such as the Markov Clustering Algorithm (MCL), and find a significant improvement in the RRW clusters' precision and accuracy values.ConclusionRRW, which is a technique that exploits the topology of the network, is more precise and robust in finding local clusters. In addition, it has the added flexibility of being able to find multi-functional proteins by allowing overlapping clusters. <s> BIB002 </s> A Survey on Personalized PageRank Computation Algorithms <s> E. BIOINFORMATICS <s> Motivation: Enormous and constantly increasing quantity of biological information is represented in metabolic and in protein interaction network databases. Most of these data are freely accessible through large public depositories. The robust analysis of these resources needs novel technologies, being developed today. ::: ::: Results: Here we demonstrate a technique, originating from the PageRank computation for the World Wide Web, for analyzing large interaction networks. The method is fast, scalable and robust, and its capabilities are demonstrated on metabolic network data of the tuberculosis bacterium and the proteomics analysis of the blood of melanoma patients. ::: ::: Availability: The Perl script for computing the personalized PageRank in protein networks is available for non-profit research applications (together with sample input files) at the address: http://uratim.com/pp.zip ::: ::: Contact:grolmusz@cs.elte.hu. ::: ::: Supplementary information: Supplementary data are available at Bioinformatics online. <s> BIB003 </s> A Survey on Personalized PageRank Computation Algorithms <s> E. BIOINFORMATICS <s> Despite the considerable progress in disease gene discovery, we are far from uncovering the underlying cellular mechanisms of diseases since complex traits, even many Mendelian diseases, cannot be explained by simple genotype ^ phenotype relationships. More recently, an increasingly accepted view is that human diseases result from perturbations of cellular systems, especially molecular networks. Genes associated with the same or similar diseases commonly reside in the same neighborhood of molecular networks. Such observations have built the basis for a large collection of computational approaches to find previously unknown genes associated with certain diseases. The majority of the methods are based on protein interactome networks, with integration of other large-scale genomic data or disease phenotype information, to infer how likely it is that a gene is associated with a disease. Here, we review recent, state of the art, network-based methods used for prioritizing disease genes as well as unraveling the molecular basis of human diseases. <s> BIB004 </s> A Survey on Personalized PageRank Computation Algorithms <s> E. BIOINFORMATICS <s> Predicting potential drug–target interactions from heterogeneous biological data is critical not only for better understanding of the various interactions and biological processes, but also for the development of novel drugs and the improvement of human medicines. In this paper, the method of Network-based Random Walk with Restart on the Heterogeneous network (NRWRH) is developed to predict potential drug–target interactions on a large scale under the hypothesis that similar drugs often target similar target proteins and the framework of Random Walk. Compared with traditional supervised or semi-supervised methods, NRWRH makes full use of the tool of the network for data integration to predict drug–target associations. It integrates three different networks (protein–protein similarity network, drug–drug similarity network, and known drug–target interaction networks) into a heterogeneous network by known drug–target interactions and implements the random walk on this heterogeneous network. When applied to four classes of important drug–target interactions including enzymes, ion channels, GPCRs and nuclear receptors, NRWRH significantly improves previous methods in terms of cross-validation and potential drug–target interaction prediction. Excellent performance enables us to suggest a number of new potential drug–target interactions for drug development. <s> BIB005 </s> A Survey on Personalized PageRank Computation Algorithms <s> E. BIOINFORMATICS <s> Accumulating evidence demonstrates that long non-coding RNAs (lncRNAs) play important roles in the development and progression of complex human diseases, and predicting novel human lncRNA–disease associations is a challenging and urgently needed task, especially at a time when increasing amounts of lncRNA-related biological data are available. In this study, we proposed a global network-based computational framework, RWRlncD, to infer potential human lncRNA–disease associations by implementing the random walk with restart method on a lncRNA functional similarity network. The performance of RWRlncD was evaluated by experimentally verified lncRNA–disease associations, based on leave-one-out cross-validation. We achieved an area under the ROC curve of 0.822, demonstrating the excellent performance of RWRlncD. Significantly, the performance of RWRlncD is robust to different parameter selections. Predictively highly-ranked lncRNA–disease associations in case studies of prostate cancer and Alzheimer's disease were manually confirmed by literature mining, providing evidence of the good performance and potential value of the RWRlncD method in predicting lncRNA–disease associations. <s> BIB006 </s> A Survey on Personalized PageRank Computation Algorithms <s> E. BIOINFORMATICS <s> // Xing Chen 1 , Zhu-Hong You 2 , Gui-Ying Yan 3, 4 , Dun-Wei Gong 1 1 School of Information and Electrical Engineering, China University of Mining and Technology, Xuzhou, 221116, China 2 School of Computer Science and Technology, China University of Mining and Technology, Xuzhou, 221116, China 3 Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing, 100190, China 4 National Center for Mathematics and Interdisciplinary Sciences, Chinese Academy of Sciences, Beijing, 100190, China Correspondence to: Xing Chen, email: xingchen@amss.ac.cn Zhu-Hong You, email: zhuhongyou@gmail.com Keywords: lncRNAs, disease, cancer, random walk with restart Received: January 20, 2016 Accepted: July 06, 2016 Published: August 09, 2016 ABSTRACT In recent years, accumulating evidences have shown that the dysregulations of lncRNAs are associated with a wide range of human diseases. It is necessary and feasible to analyze known lncRNA-disease associations, predict potential lncRNA-disease associations, and provide the most possible lncRNA-disease pairs for experimental validation. Considering the limitations of traditional Random Walk with Restart (RWR), the model of Improved Random Walk with Restart for LncRNA-Disease Association prediction (IRWRLDA) was developed to predict novel lncRNA-disease associations by integrating known lncRNA-disease associations, disease semantic similarity, and various lncRNA similarity measures. The novelty of IRWRLDA lies in the incorporation of lncRNA expression similarity and disease semantic similarity to set the initial probability vector of the RWR. Therefore, IRWRLDA could be applied to diseases without any known related lncRNAs. IRWRLDA significantly improved previous classical models with reliable AUCs of 0.7242 and 0.7872 in two known lncRNA-disease association datasets downloaded from the lncRNADisease database, respectively. Further case studies of colon cancer and leukemia were implemented for IRWRLDA and 60% of lncRNAs in the top 10 prediction lists have been confirmed by recent experimental reports. <s> BIB007 </s> A Survey on Personalized PageRank Computation Algorithms <s> E. BIOINFORMATICS <s> Motivation: Analysis of co-expressed gene sets typically involves testing for enrichment of different annotations or ‘properties’ such as biological processes, pathways, transcription factor binding sites, etc., one property at a time. This common approach ignores any known relationships among the properties or the genes themselves. It is believed that known biological relationships among genes and their many properties may be exploited to more accurately reveal commonalities of a gene set. Previous work has sought to achieve this by building biological networks that combine multiple types of gene–gene or gene–property relationships, and performing network analysis to identify other genes and properties most relevant to a given gene set. Most existing network-based approaches for recognizing genes or annotations relevant to a given gene set collapse information about different properties to simplify (homogenize) the networks. ::: ::: Results: We present a network-based method for ranking genes or properties related to a given gene set. Such related genes or properties are identified from among the nodes of a large, heterogeneous network of biological information. Our method involves a random walk with restarts, performed on an initial network with multiple node and edge types that preserve more of the original, specific property information than current methods that operate on homogeneous networks. In this first stage of our algorithm, we find the properties that are the most relevant to the given gene set and extract a subnetwork of the original network, comprising only these relevant properties. We then re-rank genes by their similarity to the given gene set, based on a second random walk with restarts, performed on the above subnetwork. We demonstrate the effectiveness of this algorithm for ranking genes related to Drosophila embryonic development and aggressive responses in the brains of social animals. ::: ::: Availability and Implementation: DRaWR was implemented as an R package available at veda.cs.illinois.edu/DRaWR. ::: ::: Contact: ude.sionilli@ittalb ::: ::: Supplementary information: Supplementary data are available at Bioinformatics online. <s> BIB008 </s> A Survey on Personalized PageRank Computation Algorithms <s> E. BIOINFORMATICS <s> Epigenetic regulation has long been recognized as a significant factor in various biological processes, such as development, transcriptional regulation, spermatogenesis, and chromosome stabilization. Epigenetic alterations lead to many human diseases, including cancer, depression, autism, and immune system defects. Although efforts have been made to identify epigenetic regulators, it remains a challenge to systematically uncover all the components of the epigenetic regulation in the genome level using experimental approaches. The advances of constructing protein-protein interaction (PPI) networks provide an excellent opportunity to identify novel epigenetic factors computationally in the genome level. In this study, we identified potential epigenetic factors by using a computational method that applied the random walk with restart (RWR) algorithm on a protein-protein interaction (PPI) network using reported epigenetic factors as seed nodes. False positives were identified by their specific roles in the PPI network or by a low-confidence interaction and a weak functional relationship with epigenetic regulators. After filtering out the false positives, 26 candidate epigenetic factors were finally accessed. According to previous studies, 22 of these are thought to be involved in epigenetic regulation, suggesting the robustness of our method. Our study provides a novel computational approach which successfully identified 26 potential epigenetic factors, paving the way on deepening our understandings on the epigenetic mechanism. <s> BIB009
PPR can also be applied to scientific data analysis BIB003 , BIB002 , BIB004 . Iván et al. analyzed protein interaction networks using PPR BIB003 . They applied PPR to analyze proteinprotein interaction (PPI) networks that connect interacting proteins. Sun et al. BIB006 proposed a global network-based computational framework, which was called RWRlncD, to infer potential human lncRNA-disease associations by implementing the method on an lncRNA functional similarity network. Chen et al. BIB007 proposed an Improved Random Walk with Restart for a lncRNA-Disease Association Prediction (IRWRLDA) model to predict novel lncRNA-disease associations by incorporating lncRNA expression similarity and disease semantic similarity. Chen et al. BIB005 proposed a Network-based Random Walk with Restart on a Heterogeneous network (NRWRH) to predict potential drug-target interactions on a large scale under the hypothesis that similar drugs often target similar target proteins. Li et al. BIB009 identified novel epigenetic factors by using a computational method that applied RWR algorithm on a protein-protein interaction (PPI) network using reported epigenetic factors as seed nodes. Blatti and Sinha BIB008 presented a networkbased method, which involves RWR, for ranking the genes or properties related to a given gene set. Chipman and Singh BIB001 presented a method based on RWR, which captures aspects of the network topology to classify potential genetic interactions and applied it to biological networks.