Motivation: Mutual exclusivity is a widely recognized property of many cancer drivers. Knowledge about these relationships can provide important insights into cancer drivers, cancer-driving pathways and cancer subtypes. It can also be used to predict new functional interactions between cancer driving genes and uncover novel cancer drivers. Currently, most of mutual exclusivity analyses are preformed focusing on a limited set of genes in part due to the computational cost required to rigorously compute P -values. Results: To reduce the computing cost and perform less restricted mutual exclusivity analysis, we developed an efficient method to estimate P -values while controlling the mutation rates of individual patients and genes similar to the permutation test. A comprehensive mutual exclusivity analysis allowed us to uncover mutually exclusive pairs, some of which may have relatively low mutation rates. These pairs often included likely cancer drivers that have been missed in previous analyses. More importantly, our results demonstrated that mutual exclusivity can also provide information that goes beyond the interactions between cancer drivers and can, for example, elucidate different mutagenic processes in different cancer groups. In particular, including frequently mutated, long genes such as TTN in our analysis allowed us to observe interesting patterns of APOBEC activity in breast cancer and identify a set of related driver genes that are highly predictive of patient survival. In addition, we utilized our mutual exclusivity analysis in support of a previously proposed model where APOBEC activity is the underlying process that causes TP53 mutations in a subset of breast cancer cases. Availability and Implementation: http://www.ncbi.nlm.nih.gov/CBBresearch/Przytycka/index.cgi#wesme. Contact: [email protected]. Supplementary information: Supplementary data are available at Bioinformatics online.

The analysis of the mutational landscape of cancer, including mutual exclusivity and co-occurrence of mutations, has been instrumental in studying the disease. We hypothesized that exploring the interplay between co-occurrence, mutual exclusivity, and functional interactions between genes will further improve our understanding of the disease and help to uncover new relations between cancer driving genes and pathways. To this end, we designed a general framework, BeWith, for identifying modules with different combinations of mutation and interaction patterns. We focused on three different settings of the BeWith schema: (i) BeME-WithFun, in which the relations between modules are enriched with mutual exclusivity, while genes within each module are functionally related; (ii) BeME-WithCo, which combines mutual exclusivity between modules with co-occurrence within modules; and (iii) BeCo-WithMEFun, which ensures co-occurrence between modules, while the within module relations combine mutual exclusivity and functional interactions. We formulated the BeWith framework using Integer Linear Programming (ILP), enabling us to find optimally scoring sets of modules. Our results demonstrate the utility of BeWith in providing novel information about mutational patterns, driver genes, and pathways. In particular, BeME-WithFun helped identify functionally coherent modules that might be relevant for cancer progression. In addition to finding previously well-known drivers, the identified modules pointed to other novel findings such as the interaction between NCOR2 and NCOA3 in breast cancer. Additionally, an application of the BeME-WithCo setting revealed that gene groups differ with respect to their vulnerability to different mutagenic processes, and helped us to uncover pairs of genes with potentially synergistic effects, including a potential synergy between mutations in TP53 and the metastasis related DCC gene. Overall, BeWith not only helped us uncover relations between potential driver genes and pathways, but also provided additional insights on patterns of the mutational landscape, going beyond cancer driving mutations. Implementation is available at https://www.ncbi.nlm.nih.gov/CBBresearch/Przytycka/software/bewith.html.

Cancer is now increasingly studied from the perspective of dysregulated pathways, rather than as a disease resulting from mutations of individual genes. A pathway-centric view acknowledges the heterogeneity between genomic profiles from different cancer patients while assuming that the mutated genes are likely to belong to the same pathway and cause similar disease phenotypes. Indeed, network-centric approaches have proven to be helpful for finding genotypic causes of diseases, classifying disease subtypes, and identifying drug targets. In this review, we discuss how networks can be used to help understand patient-to-patient variations and how one can leverage this variability to elucidate interactions between cancer drivers.

MOTIVATION: The data gathered by the Pan-Cancer initiative has created an unprecedented opportunity for illuminating common features across different cancer types. However, separating tissue-specific features from across cancer signatures has proven to be challenging. One of the often-observed properties of the mutational landscape of cancer is the mutual exclusivity of cancer driving mutations. Even though studies based on individual cancer types suggested that mutually exclusive pairs often share the same functional pathway, the relationship between across cancer mutual exclusivity and functional connectivity has not been previously investigated. RESULTS: We introduce a classification of mutual exclusivity into three basic classes: within tissue type exclusivity, across tissue type exclusivity and between tissue type exclusivity. We then combined across-cancer mutual exclusivity with interactions data to uncover pan-cancer dysregulated pathways. Our new method, Mutual Exclusivity Module Cover (MEMCover) not only identified previously known Pan-Cancer dysregulated subnetworks but also novel subnetworks whose across cancer role has not been appreciated well before. In addition, we demonstrate the existence of mutual exclusivity hubs, putatively corresponding to cancer drivers with strong growth advantages. Finally, we show that while mutually exclusive pairs within or across cancer types are predominantly functionally interacting, the pairs in between cancer mutual exclusivity class are more often disconnected in functional networks.

Complex diseases are caused by a combination of genetic and environmental factors. Uncovering the molecular pathways through which genetic factors affect a phenotype is always difficult, but in the case of complex diseases this is further complicated since genetic factors in affected individuals might be different. In recent years, systems biology approaches and, more specifically, network based approaches emerged as powerful tools for studying complex diseases. These approaches are often built on the knowledge of physical or functional interactions between molecules which are usually represented as an interaction network. An interaction network not only reports the binary relationships between individual nodes but also encodes hidden higher level organization of cellular communication. Computational biologists were challenged with the task of uncovering this organization and utilizing it for the understanding of disease complexity, which prompted rich and diverse algorithmic approaches to be proposed. We start this chapter with a description of the general characteristics of complex diseases followed by a brief introduction to physical and functional networks. Next we will show how these networks are used to leverage genotype, gene expression, and other types of data to identify dysregulated pathways, infer the relationships between genotype and phenotype, and explain disease heterogeneity. We group the methods by common underlying principles and first provide a high level description of the principles followed by more specific examples. We hope that this chapter will give readers an appreciation for the wealth of algorithmic techniques that have been developed for the purpose of studying complex diseases as well as insight into their strengths and limitations.

Broadcasting is a fundamental operation in wireless networks and plays an important role in the communication protocol design. In multihop wireless networks, however, interference at a node due to simultaneous transmissions from its neighbors makes it nontrivial to design a minimum-latency broadcast algorithm, which is known to be NP-complete. We present a simple 12-approximation algorithm for the one-to-all broadcast problem that improves all previously known guarantees for this problem. We then consider the all-to-all broadcast problem where each node sends its own message to all other nodes. For the all-to-all broadcast problem, we present two algorithms with approximation ratios of 20 and 34, improving the best result available in the literature. Finally, we report experimental evaluation of our algorithms. Our studies indicate that our algorithms perform much better in practice than the worst-case guarantees provided in the theoretical analysis and achieve up to 37 percent performance improvement over existing schemes.

Large-scale storage systems are crucial components in data-intensive applications such as search engine clusters, video-on-demand servers, sensor networks and grid computing. A storage server typically consists of a set of storage devices. In such systems, data layouts may need to be reconfigured over time for load balancing or in the event of system failure/upgrades. It is critical to migrate data to their target locations as quickly as possible to obtain the best performance. Most of the previous results on data migration assume that each storage node can perform only one data transfer at a time. A storage node, however, can typically handle multiple transfers simultaneously and this can reduce the total migration time significantly. Moreover, storage devices tend to have heterogeneous capabilities as devices may be added over time due to storage demand increase. In this paper, we consider the heterogeneous data migration problem, where we assume that each storage node v has different transfer constraint cv, which represents how many simultaneous transfers v can handle. We develop algorithms to minimize the data migration time. We show that it is possible to find an optimal migration schedule when all cvs are even. Furthermore, though the problem is NP-hard in general, we give an efficient algorithm that offers a rigorous (1 + o(1))-approximation guarantee.

In complex diseases, various combinations of genomic perturbations often lead to the same phenotype. On a molecular level, combinations of genomic perturbations are assumed to dys-regulate the same cellular pathways. Such a pathway-centric perspective is fundamental to understanding the mechanisms of complex diseases and the identification of potential drug targets. In order to provide an integrated perspective on complex disease mechanisms, we developed a novel computational method to simultaneously identify causal genes and dys-regulated pathways. First, we identified a representative set of genes that are differentially expressed in cancer compared to non-tumor control cases. Assuming that disease-associated gene expression changes are caused by genomic alterations, we determined potential paths from such genomic causes to target genes through a network of molecular interactions. Applying our method to sets of genomic alterations and gene expression profiles of 158 Glioblastoma multiforme (GBM) patients we uncovered candidate causal genes and causal paths that are potentially responsible for the altered expression of disease genes. We discovered a set of putative causal genes that potentially play a role in the disease. Combining an expression Quantitative Trait Loci (eQTL) analysis with pathway information, our approach allowed us not only to identify potential causal genes but also to find intermediate nodes and pathways mediating the information flow between causal and target genes. Our results indicate that different genomic perturbations indeed dys-regulate the same functional pathways, supporting a pathway-centric perspective of cancer. While copy number alterations and gene expression data of glioblastoma patients provided opportunities to test our approach, our method can be applied to any disease system where genetic variations play a fundamental causal role.

Broadcasting is a fundamental operation in wireless networks and plays an important role in the communication protocol design. In multihop wireless networks, however, interference at a node due to simultaneous transmissions from its neighbors makes it non-trivial to design a minimum-latency broadcast algorithm, which is known to be NP-complete. We present a simple 12-approximation algorithm for the one-to-all broadcast problem that improves all previously known guarantees for this problem. We then consider the all-to-all broadcast problem where each node sends its own message to all other nodes. For the all-to-all broadcast problem, we present two algorithms with approximation ratios of 20 and 34, improving the best result available in the literature. Finally, we report experimental evaluation of our algorithms. Our studies indicate that our algorithms perform much better in practice than the worst-case guarantees provided in the theoretical analysis and achieve up to 37% performance improvement over existing schemes.

Microarray experiments produce expression patterns for thousands of genes at once. On the other hand, biomedical literature contains large amounts of gene regulation relationship information accumulated over the years. One obvious requirement is an automated way of comparing microarray data with the collection of known gene regulation relationships. Such an automated comparison is imperative because it can help biologists rapidly understand the context of a given microarray experiment. In addition, the consistency measure can be used to either validate or refute the hypothesis being tested using the microarray experiment. In this paper we present a systematic way of examining the consistency between a given set of microarray data and known gene regulation relationships. We first introduce a simple gene regulation network model with two separate algorithms designed to isolate a maximally consistent network. Subsequently, we extend the model to take into account multiple regulating factors for a single gene while highlighting both consistencies and inconsistencies. We illustrate the effectiveness of our approach with two practical examples, one that picks the peroxisome proliferator-activated receptor (PPAR) pathway as highly consistent from multiple pathways of Kyoto encyclopedia of genes and genomes (KEGG), and another that isolates key regulatory relationships involving nfkb1 and others known for macrophage's counter response to inflammation.

Using microarray technology for genetic analysis in biological experiments requires computationally intensive tools to interpret results. The main objective here is to develop a ldquometa-analysisrdquo tool that enables researchers to ldquosprayrdquo microarray data over a network of relevant gene regulation relationships, extracted from a database of published gene regulatory pathway models. The consistency of the data from a microarray experiment is evaluated to determine if it agrees or contradicts with previous findings. The database is limited to ldquoactivaterdquo and ldquoinhibitrdquo gene regulatory relationships at this point and a heuristic graph based approach is developed for consistency checking. Predictions are made for the regulation of genes that were not a part of the microarray experiment, but are related to the experiment through regulatory relationships. This meta-analysis will not only highlight consistent findings but also pinpoint genes that were missed in earlier experiments and should be considered in subsequent analysis.

Infrastructure-based overlay networks have been proposed to support the quality of service requirements of a wide range of applications. In this paper, we study using infrastructure-based overlay for delay-sensitive low-bandwidth group communications, such as teleconferencing and chat room. In particular, we study where to place overlay nodes (called proxies) to minimize end-to-end delays. We formulate the problem of optimal proxy placement using integer-linear programming and quantify the benefits from using proxies in six real-world networks. We And that, perhaps surprisingly, only two out of the six networks benefit from using proxies. We furthermore use network characteristics to explain these benefits or lack of benefits. Last, for the two networks which benefit from using proxies, we find that a small number proxies (2 to 3) are sufficient to realize most of the performance gains.

Microarray experiments produce gene expression data at such a high speed and volume that it is imperative to use highly specialized computational tools for their analyses. One group of such computational tools deals with, namely, "meta-analysis" of microarray data. This step attempts to extract biological interpretations from the identified gene expression pattern. One particular aspect of meta-analysis is sorting out which gene regulation pathways are active and/or inhibited. The focus on this paper is to propose a computational framework with which scientists can compare microarray data with known gene regulation networks that are formed by two known binary gene regulation relationships, activate and inhibit. Using this framework scientists can conduct numerous analysis tasks including (i) identify active or inhibited sub-networks out of massively interconnected gene regulation pathways, (ii) find key genes, namely hubs, that are inferred to be widely involved in multiple aspects of gene regulation, (iii) identify regions of the network that contradict the known regulation, and (iv) estimate the direction of expression of genes that were not included in the microarray experiment. One known utility of this meta-analysis is to help scientists to identify a group of genes that they have missed in earlier experiments and should include in their subsequent experiments. Another utility is to enable them to isolate the group of genes that should be followed more closely using higher accuracy gene expression assays. We introduce three separate but inter-related meta-analysis methodologies, namely, FCFS, Hub majority, and SDP-based. We illustrate our proposed framework using microarray data derived from noggin treated osteoblast cells. The example clearly shows finding sub-networks related to B-catenin which should be expected and thus demonstrates the effectiveness of our proposed framework

We consider the channel assignment problem for multihop wireless networks in which nodes have multiple interfaces. Given the number of interfaces at each node and available channels in the system, we find a feasible channel assignment to improve network performance. Even when routing is given, finding a channel assignment for optimal performance is NP-hard. We present the SAFE (skeleton assisted partition FrEe) channel assignment scheme, which uses randomized channel assignment in a distributed manner while maintaining network connectivity. SAFE can utilize all independent channels in the system while attempting to distribute edges sharing a particular channel evenly throughout the network. To handle topology change and incremental deployment better, SAFE decouples the channel assignment problem from routing. Our simulation results show that SAFE significantly improves network performance in terms of throughput and delay and is comparable to the best prior centralized scheme that jointly considers routing and channel assignment

Broadcasting and multicasting are fundamental operations. In this work we develop algorithms for performing broadcast and multicast in clusters of workstations. In this model, sending a message from one machine to another machine in the same cluster takes 1 time unit, and sending a message to a machine in a different cluster takes C time units. Lowekamp and Beguelin proposed heuristics for this model, but their algorithms may produce broadcast times that are arbitrarily worse than optimal. We develop the first constant factor approximation algorithms for this model. Algorithm LCF (Largest Cluster First) for the basic model is simple, efficient and has a worst case approximation guarantee of 2. We then extend these models to more complex models where we remove the assumption that an unbounded amount of simultaneous communication may happen using the global network. The algorithms for these models build on the LCF method developed for the basic problem. Finally, we develop broadcasting algorithms for the postal model where the sending processor does not block for C time units when the message is in transit. Moreover, we assume that the messages are small and so the bottleneck is the latency.

Our work is motivated by the problem of managing data on storage devices, typically a set of disks. Such high-demand storage servers are used as Web servers or as multimedia servers for handling high demand for data. As the system is running, it needs to dynamically respond to changes in demand for different data items. In this work we study the data migration problem, which arises when we need to quickly change one storage configuration into another. We show that this problem is NP-hard. In addition, we develop polynomial-time approximation algorithms for this problem and prove a worst-case bound of 9.5 on the approximation factor achieved by our algorithm.

Our work is motivated by the problem of managing data on storage devices, typically a set of disks. Such high demand storage servers are used as web servers, or multimedia servers for handling high demand for data. As the system is running, it needs to dynamically respond to changes in demand for different data items. In this work we study the data migration problem, which arises when we need to quickly change one storage configuration into another. We show that this problem is NP-hard. In addition, we develop polynomial-time approximation algorithms for this problem and prove a worst case bound of 9.5 on the approximation factor achieved by our algorithm. We also compare the algorithm to several heuristics for this problem.