MOTIVATION: Microbiota-derived metabolites significantly impact host biology, prompting extensive research on metabolic shifts linked to the microbiota. Recent studies have explored both direct metabolite analyses and computational tools for inferring metabolic functions from microbial shotgun metagenome data. However, no existing tool specifically focuses on predicting changes in individual metabolite levels, as opposed to metabolic pathway activities, based on shotgun metagenome data. Understanding these changes is crucial for directly estimating the metabolic potential associated with microbial genomic content. RESULTS: We introduce Predicting Changes in Microbial metaBolites (PredCMB), a novel method designed to predict alterations in individual metabolites between conditions using shotgun metagenome data and enzymatic gene-metabolite networks. PredCMB evaluates differential enzymatic gene abundance between conditions and estimates its influence on metabolite changes. To validate this approach, we applied it to two publicly available datasets comprising paired shotgun metagenomics and metabolomics data from inflammatory bowel disease cohorts and the cohort of gastrectomy for gastric cancer. Benchmark evaluations revealed that PredCMB outperformed a previous method by demonstrating higher correlations between predicted metabolite changes and experimentally measured changes. Notably, it identified metabolite classes exhibiting major alterations between conditions. By enabling the prediction of metabolite changes directly from shotgun metagenome data, PredCMB provides deeper insights into microbial metabolic dynamics than existing methods focused on pathway activity evaluation. Its potential applications include refining target metabolite selection in microbial metabolomic studies and assessing the contributions of microbial metabolites to disease pathogenesis. AVAILABILITY AND IMPLEMENTATION: Freely available to non-commercial users at https://www.sysbiolab.org/predcmb.

Many existing clustering methods usually compute clusters from the reduced data sets obtained by summarizing the original very large data sets. BIRCH is a popular summary-based clustering method that first builds a CF tree, and then performs a global clustering using the leaf entries of the tree. However, to the best of our knowledge, no prior studies have proposed a global clustering method that uses the structure of a CF tree. Therefore, we propose a novel global clustering method ERC (effective multiple range queries-based clustering), which takes advantage of the structure of a CF tree. We further propose a CF+tree, which optimizes the node split scheme used in the CF tree. As a result, the CF+-ERC (CF+tree-based ERC) method effectively computes clusters over large data sets. Furthermore, it does not require a predefined number of clusters to compute the clusters. We present in-depth theoretical and experimental analyses of our method. Experimental results on very large synthetic data sets demonstrate that the proposed approach is effective in terms of cluster quality and robustness and is significantly faster than existing clustering methods. In addition, we apply our clustering method to real data sets and achieve promising results.

MOTIVATION: Identifying differential patterns between conditions is a popular approach to understanding the discrepancy between different biological contexts. Although many statistical tests were proposed for identifying gene sets with differential patterns based on different definitions of differentiality, few methods were suggested to identify gene sets with differential functional protein networks due to computational complexity. RESULTS: We propose a method of Knowledge-based Evaluation of Dependency DifferentialitY (KEDDY), which is a statistical test for differential functional protein networks of a set of genes between two conditions with utilizing known functional protein-protein interaction information. Unlike other approaches focused on differential expressions of individual genes or differentiality of individual interactions, KEDDY compares two conditions by evaluating the probability distributions of functional protein networks based on known functional protein-protein interactions. The method has been evaluated and compared with previous methods through simulation studies, where KEDDY achieves significantly improved performance in accuracy and speed than the previous method that does not use prior knowledge and better performance in identifying gene sets with differential interactions than other methods evaluating changes in gene expressions. Applications to cancer data sets show that KEDDY identifies alternative cancer subtype-related differential gene sets compared to other differential expression-based methods, and the results also provide detailed gene regulatory information that drives the differentiality of the gene sets. AVAILABILITY AND IMPLEMENTATION: The Java implementation of KEDDY is freely available to non-commercial users at https://sites.google.com/site/sjunggsm/keddy. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

Existing methods of scheduling data items over multiple wireless broadcast channels focus on the assignment of a data item to a channel. However, data items are not allocated more than once per broadcast cycle to a single channel. Our scheme considers the numbers of copies of a data item that should be allocated in the context of the channel assignment problem and aims to reduce the average data access time by allocating a popular data item more than once per cycle to the channel to which it is assigned. The number of times that each data item is allocated reflects its access probability. Simulation results show that our scheme reduces the average expected delay, especially when there are few channels.

Abstract In a wireless client‐server environment, data broadcasting is an efficient data dissemination method and some of the broadcast data are often cached at each mobile client's cache. Data broadcasting and caching save communication bandwidth, resource usage, and data access time. A server also broadcasts invalidation reports (IRs) to maintain the consistency between server data and clients' cached data. Most existing cache invalidation policies simply purge the entire cache after a client has been disconnected long enough to miss a certain number (window size) of IRs. We present a cache invalidation scheme to increase the reusability of the data in mobile clients' caches after long disconnection. Instead of clearing the entire cache regardless of its consistency after long disconnection, a client estimates the relative cost of purging all data and the cost of a selective purge. If a selective purge is cheaper, the client sends server an uplink message to ask the validity of data whose update rate is low to salvage as many valid data as possible. Simulation results show that our scheme effectively increases cache reusability since our cost functions respect update rates at a server, broadcast intervals, the communication bandwidth, and data sizes as well as disconnection time. Copyright © 2007 John Wiley & Sons, Ltd.

Broadcast has often been used to disseminate frequently requested data efficiently to a large volume of mobile units over single or multiple channels. Since mobile units have limited battery power, the minimization of the access and tuning times for the broadcast data is an important problem. There have been many research efforts that focus on minimizing access and tuning times by providing indexes on the broadcast data. We have studied an efficient index allocation method for broadcast data with skewed access frequencies over multiple physical channels which cannot be coalesced into a single high bandwidth channel. Previously proposed index allocation techniques have one of two problems. The first problem is that they require equal size for both index and data. The second problem is that their performance degrades when the number of given physical channels is not enough. These two problems result in an increased average access time for the broadcast data. To cope with these problems, we propose a tree-structured index allocation method. Our method minimizes the average access time by broadcasting the hot data and their indices more frequently than the less hot data and their indexes over the dedicated index and data channels. We present an in-depth experimental and theoretical analysis of our method by comparing it with other similar techniques. Our performance analysis shows that it significantly decreases the average access and tuning times for the broadcast data over existing methods.

In this paper, we have developed a HiTi (Hierarchical MulTi) graph model for structuring large topographical road maps to speed up the minimum cost route computation. The HiTi graph model provides a novel approach to abstracting and structuring a topographical road map in a hierarchical fashion. We propose a new shortest path algorithm named SPAH, which utilizes HiTi graph model of a topographical road map for its computation. We give the proof for the optimality of SPAH. Our performance analysis of SPAH on grid graphs showed that it significantly reduces the search space over existing methods. We also present an in-depth experimental analysis of HiTi graph method by comparing it with other similar works on grid graphs. Within the HiTi graph framework, we also propose a parallel shortest path algorithm named ISPAH. Experimental results show that inter query shortest path problem provides more opportunity for scalable parallelism than the intra query shortest path problem.

In navigation systems, a primary task is to compute the minimum cost route from the current location to the destination. One of the major problems for navigation systems is that a significant amount of computation time is required to find a minimum cost path when the topographical road map is large. Since navigation systems are real time systems, it is critical that the path be computed while satisfying a time constraint. We propose a new graph model named HiTi (hierarchical multi graph model), for efficiently computing an optimal minimum cost path. Based on HiTi graph model, we propose a new single pair minimum cost path algorithm. We empirically show that our proposed algorithm performs far better than the traditional A* algorithm. Further, we empirically analyze our algorithm by varying both edge cost distribution and hierarchical level number of HiTi graphs.

In a distributed environment, it is advantageous to fragment a relation and store the fragments at various sites. Based on the concept of lattice structures, we develop a framework to study the fragmentation problems of distributed recursive relations. Two of the fragmentation problems are how to describe and identify fragments. Description and identification methods previously suggested are more suitable in parallel environments than in distributed databases. We propose a method to describe and identify fragments based on lattice structures. Finding lattice descriptions of fragments is shown to be an NP complete problem. We analyze the performance of the lattice approach both theoretically and experimentally. This is done by creating a database of recursive relations. The empirical analysis shows that our proposed algorithms give near optimal solutions.

In the domain of biological classification, classifications are performed hierarchically. There are no standard classifications which are unanimously accepted by the community of each domain; many different interacting views of classification exist about the same data, and the discovery of new data results in changes to the existing classification. Even a single individual may change his or her own classification of a particular group. Since multiple classification views interact, they are semantically related. It is difficult to model this kind of dynamically evolving and semantically interacting classification system using traditional data models, which lack the structural flexibility necessary to support dynamic views of hierarchic classifications, and cannot properly capture the history of these complex interactions. We have developed a new data model which is suitable for supporting semantically interacting dynamic views of hierarchic biological classifications. On the basis of our new data model we have developed a prototype database system called HICLAS (HIerarchical CLAssification System); its domain is plant taxonomy. HICLAS is available through the Internet and an X-window interface has been implemented to support queries to classification data.