Search

Network motifs are topological subgraph patterns that recur with statistical significance in a network. Network motifs have been widely utilized to represent important topological features for analyzing the functional properties of complex networks. While recent studies have shown the importance of network motifs, existing network models are not capable of reproducing real-world topological properties of network motifs, such as the frequency of network motifs and relative graphlet frequency distances. Here, we propose a new network measure and a new network model to reconstruct real-world network topologies, by incorporating our Grouped Attachment algorithm to generate networks in which closely related nodes have similar edge connections. We applied the proposed model to real-world complex networks, and the resulting constructed networks more closely reflected real-world network motif properties than did the existing models that we tested: the Erdös-Rényi, small-world, scale-free, popularity-similarity-optimization, and nonuniform popularity-similarity-optimization models. Furthermore, we adapted the preferential attachment algorithm to our model to gain scale-free properties while preserving motif properties. Our findings show that grouped attachment is one possible mechanism to reproduce network motif recurrence in real-world complex networks.

Identifying the health benefits of phytochemicals is an essential step in drug and functional food development. While many in vitro screening methods have been developed to identify the health effects of phytochemicals, there is still room for improvement because of high cost and low productivity. Therefore, researchers have alternatively proposed in silico methods, primarily based on three types of approaches; utilizing molecular, chemical or ethnopharmacological information. Although each approach has its own strength in analyzing the characteristics of phytochemicals, previous studies have not considered them all together. Here, we apply an integrated in silico analysis to identify the potential health benefits of phytochemicals based on molecular analysis and chemical properties as well as ethnopharmacological evidence. From the molecular analysis, we found an average of 415.6 health effects for 591 phytochemicals. We further investigated ethnopharmacological evidence of phytochemicals and found that on average 129.1 (31%) of the predicted health effects had ethnopharmacological evidence. Lastly, we investigated chemical properties to confirm whether they are orally bio-available, drug available or effective on certain tissues. The evaluation results indicate that the health effects can be predicted more accurately by cooperatively considering the molecular analysis, chemical properties and ethnopharmacological evidence.

In silico network-based methods have shown promising results in the field of drug development. Yet, most of networks used in the previous research have not included context information even though biological associations actually do appear in the specific contexts. Here, we reconstruct an anatomical context-specific network by assigning contexts to biological associations using protein expression data and scientific literature. Furthermore, we employ the context-specific network for the analysis of drug effects with a proximity measure between drug targets and diseases. Distinct from previous context-specific networks, intercellular associations and phenomic level entities such as biological processes are included in our network to represent the human body. It is observed that performances in inferring drug-disease associations are increased by adding context information and phenomic level entities. In particular, hypertension, a disease related to multiple organs and associated with several phenomic level entities, is analyzed in detail to investigate how our network facilitates the inference of drug-disease associations. Our results indicate that the inclusion of context information, intercellular associations, and phenomic level entities can contribute towards a better prediction of drug-disease associations and provide detailed insight into understanding of how drugs affect diseases in the human body.

As pharmacodynamic drug-drug interactions (PD DDIs) could lead to severe adverse effects in patients, it is important to identify potential PD DDIs in drug development. The signaling starting from drug targets is propagated through protein-protein interaction (PPI) networks. PD DDIs could occur by close interference on the same targets or within the same pathways as well as distant interference through cross-talking pathways. However, most of the previous approaches have considered only close interference by measuring distances between drug targets or comparing target neighbors. We have applied a random walk with restart algorithm to simulate signaling propagation from drug targets in order to capture the possibility of their distant interference. Cross validation with DrugBank and Kyoto Encyclopedia of Genes and Genomes DRUG shows that the proposed method outperforms the previous methods significantly. We also provide a web service with which PD DDIs for drug pairs can be analyzed at http://biosoft.kaist.ac.kr/targetrw.

Background: Biological systems are robust and complex to maintain stable phenotypes under various conditions. In these systems, drugs reported the limited efficacy and unexpected side-effects. To remedy this situation, many pharmaceutical laboratories have begun to research combination drugs and some of them have shown successful clinical results. Complementary action of multiple compounds could increase efficacy as well as reduce side-effects through pharmacological interactions. However, experimental approach requires vast cost of preclinical experiments and tests as the number of possible combinations of compound dosages increases exponentially. Computer model-based experiments have been emerging as one of the most promising solutions to cope with such complexity. Though there have been many efforts to model specific molecular pathways using qualitative and quantitative formalisms, they suffer from unexpected results caused by distant interactions beyond their localized models., Results: In this work, we propose a rule-based multi-scale modelling platform. We have tested this platform with Type 2 diabetes (T2D) model, which involves the malfunction of numerous organs such as pancreas, circulation system, liver, and adipocyte. We have extracted T2D-related 190 rules by manual curation from literature, pathway databases and converting from different types of existing models. We have simulated twenty-two T2D drugs. The results of our simulation show drug effect pathways of T2D drugs and whether combination drugs have efficacy or not and how combination drugs work on the multi-scale model., Conclusions: We believe that our simulation would help to understand drug mechanism for the drug development and provide a new way to effectively apply existing drugs for new target. It also would give insight for identifying effective combination drugs.

Background: As the amount of publicly available biomedical data increases, discovering hidden knowledge from biomedical data (i.e., Undiscovered Public Knowledge (UPK) proposed by Swanson) became an important research topic in the biological literature mining field. Drug indication inference, or drug repositioning, is one of famous UPK tasks, which infers alternative indications for approved drugs. Many previous studies tried to find novel candidate indications of existing drugs, but these works have following limitations: 1) models are not fully automated which required manual modulations to desired tasks, 2) are not able to cover various biomedical entities, and 3) have inference limitations that those works could infer only pre-defined cases using limited patterns. To overcome these problems, we suggest a new drug indication inference model., Methods: In this paper, we adopted the Typed Network Motif Comparison Algorithm (TNMCA) to infer novel drug indications using topology of given network. Typed Network Motifs (TNM) are network motifs, which store types of data, instead of values of data. TNMCA is a powerful inference algorithm for multi-level biomedical interaction data as TNMs depend on the different types of entities and relations. We utilized a new normalized scoring function as well as network exclusion to improve the inference results. To validate our method, we applied TNMCA to a public database, Comparative Toxicogenomics Database (CTD)., Results: The results show that enhanced TNMCA was able to infer meaningful indications with high performance (AUC = 0.801, 0.829) compared to the ABC model (AUC = 0.7050) and previous TNMCA model (AUC = 0.5679, 0.7469). The literature analysis also shows that TNMCA inferred meaningful results., Conclusions: We proposed and enhanced a novel drug indication inference model by incorporating topological patterns of given network. By utilizing inference models from the topological patterns, we were able to improve inference power in drug indication inferences.

Phenotypes of diseases, including prognosis, are likely to have complex etiologies and be derived from interactive mechanisms, including genetic and protein interactions. Many computational methods have been used to predict survival outcomes without explicitly identifying interactive effects, such as the genetic basis for transcriptional variations. We have therefore proposed a classification method based on the interaction between genotype and transcriptional expression features (CORE-F). This method considers the overall "genetic architecture," referring to genetically based transcriptional alterations that influence prognosis. In comparing the performance of CORE-F with the ensemble tree, the best-performing method predicting patient survival, we found that CORE-F outperformed the ensemble tree (mean AUC, 0.85 vs. 0.72). Moreover, the trained associations in the CORE-F successfully identified the genetic mechanisms underlying survival outcomes at the interaction-network level., (Copyright © 2011 Elsevier Inc. All rights reserved.)

Motivation: Gene set analysis has become an important tool for the functional interpretation of high-throughput gene expression datasets. Moreover, pattern analyses based on inferred gene set activities of individual samples have shown the ability to identify more robust disease signatures than individual gene-based pattern analyses. Although a number of approaches have been proposed for gene set-based pattern analysis, the combinatorial influence of deregulated gene sets on disease phenotype classification has not been studied sufficiently., Results: We propose a new approach for inferring combinatorial Boolean rules of gene sets for a better understanding of cancer transcriptome and cancer classification. To reduce the search space of the possible Boolean rules, we identify small groups of gene sets that synergistically contribute to the classification of samples into their corresponding phenotypic groups (such as normal and cancer). We then measure the significance of the candidate Boolean rules derived from each group of gene sets; the level of significance is based on the class entropy of the samples selected in accordance with the rules. By applying the present approach to publicly available prostate cancer datasets, we identified 72 significant Boolean rules. Finally, we discuss several identified Boolean rules, such as the rule of glutathione metabolism (down) and prostaglandin synthesis regulation (down), which are consistent with known prostate cancer biology., Availability: Scripts written in Python and R are available at http://biosoft.kaist.ac.kr/~ihpark/. The refined gene sets and the full list of the identified Boolean rules are provided in the Supplementary Material., Supplementary Information: Supplementary data are available at Bioinformatics online.

We propose a speed estimation method with human body accelerations measured on the chest by a tri-axial accelerometer. To estimate the speed we segmented the acceleration signal into strides measuring stride time, and applied two neural networks into the patterns parameterized from each stride calculating stride length. The first neural network determines whether the subject walks or runs, and the second neural network with different node interactions according to the subject's status estimates stride length. Walking or running speed is calculated with the estimated stride length divided by the measured stride time. The neural networks were trained by patterns obtained from 15 subjects and then validated by 2 untrained subjects' patterns. The result shows good agreement between actual and estimated speeds presenting the linear correlation coefficient r=0.9874. We also applied the method to the real field and track data.

Motivation: Inferring the genetic interaction mechanism using Bayesian networks has recently drawn increasing attention due to its well-established theoretical foundation and statistical robustness. However, the relative insufficiency of experiments with respect to the number of genes leads to many false positive inferences., Results: We propose a novel method to infer genetic networks by alleviating the shortage of available mRNA expression data with prior knowledge. We call the proposed method 'modularized network learning' (MONET). Firstly, the proposed method divides a whole gene set to overlapped modules considering biological annotations and expression data together. Secondly, it infers a Bayesian network for each module, and integrates the learned subnetworks to a global network. An algorithm that measures a similarity between genes based on hierarchy, specificity and multiplicity of biological annotations is presented. The proposed method draws a global picture of inter-module relationships as well as a detailed look of intra-module interactions. We applied the proposed method to analyze Saccharomyces cerevisiae stress data, and found several hypotheses to suggest putative functions of unclassified genes. We also compared the proposed method with a whole-set-based approach and two expression-based clustering approaches.

Motivation: Clustering has been used as a popular technique for finding groups of genes that show similar expression patterns under multiple experimental conditions. Many clustering methods have been proposed for clustering gene-expression data, including the hierarchical clustering, k-means clustering and self-organizing map (SOM). However, the conventional methods are limited to identify different shapes of clusters because they use a fixed distance norm when calculating the distance between genes. The fixed distance norm imposes a fixed geometrical shape on the clusters regardless of the actual data distribution. Thus, different distance norms are required for handling the different shapes of clusters., Results: We present the Gustafson-Kessel (GK) clustering method for microarray gene-expression data. To detect clusters of different shapes in a dataset, we use an adaptive distance norm that is calculated by a fuzzy covariance matrix (F) of each cluster in which the eigenstructure of F is used as an indicator of the shape of the cluster. Moreover, the GK method is less prone to falling into local minima than the k-means and SOM because it makes decisions through the use of membership degrees of a gene to clusters. The algorithmic procedure is accomplished by the alternating optimization technique, which iteratively improves a sequence of sets of clusters until no further improvement is possible. To test the performance of the GK method, we applied the GK method and well-known conventional methods to three recently published yeast datasets, and compared the performance of each method using the Saccharomyces Genome Database annotations. The clustering results of the GK method are more significantly relevant to the biological annotations than those of the other methods, demonstrating its effectiveness and potential for clustering gene-expression data., Availability: The software was developed using Java language, and can be executed on the platforms that JVM (Java Virtual Machine) is running. It is available from the authors upon request., Supplementary Information: Supplementary data are available at http://dragon.kaist.ac.kr/gk.

Motivation: The transcription of a gene is largely determined by short sequence motifs that serve as binding sites for transcription factors. Recent findings suggest direct relationships between the motifs and gene expression levels. In this work, we present a method for identifying regulatory motifs. Our method makes use of tree-based techniques for recovering the relationships between motifs and gene expression levels., Results: We treat regulatory motifs and gene expression levels as predictor variables and responses, respectively, and use a regression tree model to identify the structural relationships between them. The regression tree methodology is extended to handle responses from multiple experiments by modifying the split function. The significance of regulatory elements is determined by analyzing tree structures and using a variable importance measure. When applied to two data sets of the yeast Saccharomyces cerevisiae, the method successfully identifies most of the regulatory motifs that are known to control gene transcription under the given experimental conditions, and suggests several new putative motifs. Analysis of the tree structures also reconfirms several pairs of motifs that are known to regulate gene transcription in combination., Availability: http://if.kaist.ac.kr/~phuong/RegTree

Motivation: Complex physiological relationships exist among human diseases. Thus, the identification of disease associations could provide new methods of disease care and diagnosis. To this end, numerous studies have investigated disease associations. However, combinatorial effect of physiological factors, which is the main characteristic of biological systems, has not been considered in most previous studies.Results: In this study, we inferred disease associations with a novel approach that considered disease-related clinical factors in combinatorial ways by using the National Health and Nutrition Examination Survey data, and the results have been shown as disease networks. Here, the FP-growth algorithm, an association rule mining algorithm, was used to generate a clinical attribute combination profile of each disease. In addition, we characterized the 22 clinical risk attribute combinations frequently discovered from the 26 diseases in this study. Furthermore, we validated that the results of this study have great potential for drug repositioning and outperform other existing disease networks in this regard. Finally, we suggest a few disease pairs as new candidates for drug repositioning and provide the evidence of their associations from the literature.Contact: dhlee@kaist.ac.kr or jmjung.kr@gmail.comSupplementary information: Supplementary data are available at the Bioinformatics online. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, the conventional k-modes-type algorithms for clustering categorical data are extended by representing the clusters of categorical data with k-populations instead of the hard-type centroids used in the conventional algorithms. Use of a population-based centroid representation makes it possible to preserve the uncertainty inherent in data sets as long as possible before actual decisions are made. The k-populations algorithm was found to give markedly better clustering results through various experiments. [Copyright &y& Elsevier]

Abstract: By using a kernel function, data that are not easily separable in the original space can be clustered into homogeneous groups in the implicitly transformed high-dimensional feature space. Kernel k-means algorithms have recently been shown to perform better than conventional k-means algorithms in unsupervised classification. However, few reports have examined the benefits of using a kernel function and the relative merits of the various kernel clustering algorithms with regard to the data distribution. In this study, we reformulated four representative clustering algorithms based on a kernel function and evaluated their performances for various data sets. The results indicate that each kernel clustering algorithm gives markedly better performance than its conventional counterpart for almost all data sets. Of the kernel clustering algorithms studied in the present work, the kernel average linkage algorithm gives the most accurate clustering results. [Copyright &y& Elsevier]

A new cluster validity index is proposed that determines the optimal partition and optimal number of clusters for fuzzy partitions obtained from the fuzzy c-means algorithm. The proposed validity index exploits an overlap measure and a separation measure between clusters. The overlap measure, which indicates the degree of overlap between fuzzy clusters, is obtained by computing an inter-cluster overlap. The separation measure, which indicates the isolation distance between fuzzy clusters, is obtained by computing a distance between fuzzy clusters. A good fuzzy partition is expected to have a low degree of overlap and a larger separation distance. Testing of the proposed index and nine previously formulated indexes on well-known data sets showed the superior effectiveness and reliability of the proposed index in comparison to other indexes. [Copyright &y& Elsevier]

In this paper the conventional fuzzy k-modes algorithm for clustering categorical data is extended by representing the clusters of categorical data with fuzzy centroids instead of the hard-type centroids used in the original algorithm. Use of fuzzy centroids makes it possible to fully exploit the power of fuzzy sets in representing the uncertainty in the classification of categorical data. To test the proposed approach, the proposed algorithm and two conventional algorithms (the k-modes and fuzzy k-modes algorithms) were used to cluster three categorical data sets. The proposed method was found to give markedly better clustering results. [Copyright &y& Elsevier]

A novel initialization scheme for the fuzzy c-means (FCM) algorithm is proposed for the color clustering problem. Given a set of color points, the proposed initialization scheme extracts the most vivid and distinguishable colors, referred to here as the dominant colors. The color points closest to these dominant colors are selected as the initial centroids in the FCM calculations. To obtain the dominant colors and their closest color points, we introduce reference colors and define a fuzzy membership model between a color point and a reference color. The effectiveness and reliability of the proposed method is demonstrated through various color clustering examples. [Copyright &y& Elsevier]