NetMODE: Network Motif Detection without Nauty

A motif in a network is a connected graph that occurs significantly more frequently as an induced subgraph than would be expected in a similar randomized network. By virtue of being atypical, it is thought that motifs might play a more important role than arbitrary subgraphs. Recently, a flurry of advances in the study of network motifs has created demand for faster computational means for identifying motifs in increasingly larger networks. Motif detection is typically performed by enumerating subgraphs in an input network and in an ensemble of comparison networks; this poses a significant computational problem. Classifying the subgraphs encountered, for instance, is typically performed using a graph canonical labeling package, such as Nauty, and will typically be called billions of times. In this article, we describe an implementation of a network motif detection package, which we call NetMODE. NetMODE can only perform motif detection for -node subgraphs when , but does so without the use of Nauty. To avoid using Nauty, NetMODE has an initial pretreatment phase, where -node graph data is stored in memory (). For we take a novel approach, which relates to the Reconstruction Conjecture for directed graphs. We find that NetMODE can perform up to around times faster than its predecessors when and up to around times faster when (the exact improvement varies considerably). NetMODE also (a) includes a method for generating comparison graphs uniformly at random, (b) can interface with external packages (e.g. R), and (c) can utilize multi-core architectures. NetMODE is available from netmode.sf.net.     

生态样带边界分析的改进算法与网络计算

确定生态样带的边界,其目的是找出样带中的一系列不连续点,判定生物物种扩散的自然屏障,分析生物分布及其景观多样性．生态样带边界分析对有害生物的扩散、生物物种分布研究以及生物多样性保护具有一定的意义．本文在前人研究的基础上,对生态样带边界分析算法进行了改进,在算法中加入了不同的距离测度,由方差／均值比率确定窗口宽度数,用置信区间及其统计检验来确定样带边界．改进算法减少了主观性,具有较高的灵敏度,可检测出更细致的边界点．研制了改进算法的Java网络软件,可在多种兼容Java的网络洲览器,如Internet Explorer,HotJava,Nescape Navigator上调用和运行．以稻田生态环境的节肢动物样带对算法进行了检验和实例分析．结果显示,低营养级的植食性节肢动物,其分布受可见边界的显著影响．高营养级的捕食性节肢动物和寄生性节肢动物的分布也受到可见边界的一定影响,但不很显著．另外,也检测到植食性节肢动物在样带中的扩散方向．相对于植食性节肢动物,捕食性节肢动物和寄生性节肢动物的扩散无明显规律性．     

变长度Motif识别中的Gibbs抽样算法(英文)

Motif识别是计算生物学中的重要问题.处理缺失数据的方法被大家广泛应用于生物序列中的Motif识别,例如EM算法,Gibbs抽样等等.现在识别Motif的方法都是首先假定Motif的长度是给的,但是,事实上Motif的长度是未知的,在这篇文章中,我们用Gibbs抽样算法在寻找Motif的位置的同时确定Motif的长度.     

Identification of Important Nodes in Directed Biological Networks: A Network Motif Approach

Identification of important nodes in complex networks has attracted an increasing attention over the last decade. Various measures have been proposed to characterize the importance of nodes in complex networks, such as the degree, betweenness and PageRank. Different measures consider different aspects of complex networks. Although there are numerous results reported on undirected complex networks, few results have been reported on directed biological networks. Based on network motifs and principal component analysis (PCA), this paper aims at introducing a new measure to characterize node importance in directed biological networks. Investigations on five real-world biological networks indicate that the proposed method can robustly identify actually important nodes in different networks, such as finding command interneurons, global regulators and non-hub but evolutionary conserved actually important nodes in biological networks. Receiver Operating Characteristic (ROC) curves for the five networks indicate remarkable prediction accuracy of the proposed measure. The proposed index provides an alternative complex network metric. Potential implications of the related investigations include identifying network control and regulation targets, biological networks modeling and analysis, as well as networked medicine.     

The Exact Evaluation of 2-way Cross-classifications Sequel: A Fugal Algorithm

A generalized algorithm is presented for generating the ensemble of unique r × c contingency tables with arbitrary, fixed row and column sums, and of arbitrary, even large, sizes. This further contributes to the operational solution of the exact ensemble distribution of 2-way contingency tables and cross classifications, along with the sampling distribution of the conventional χ²-like test statistic, or of any other test statistic calculated from the tables. The associated enumeration problem of Integer arrays with fixed row and column sums has been operationally solved.     

An Integrated Intrusion Detection Model of Cluster-Based Wireless Sensor Network

Considering wireless sensor network characteristics, this paper combines anomaly and mis-use detection and proposes an integrated detection model of cluster-based wireless sensor network, aiming at enhancing detection rate and reducing false rate. Adaboost algorithm with hierarchical structures is used for anomaly detection of sensor nodes, cluster-head nodes and Sink nodes. Cultural-Algorithm and Artificial-Fish–Swarm-Algorithm optimized Back Propagation is applied to mis-use detection of Sink node. Plenty of simulation demonstrates that this integrated model has a strong performance of intrusion detection.     

Network Intrusion Detection Based on a General Regression Neural Network Optimized by an Improved Artificial Immune Algorithm

To effectively and accurately detect and classify network intrusion data, this paper introduces a general regression neural network (GRNN) based on the artificial immune algorithm with elitist strategies (AIAE). The elitist archive and elitist crossover were combined with the artificial immune algorithm (AIA) to produce the AIAE-GRNN algorithm, with the aim of improving its adaptivity and accuracy. In this paper, the mean square errors (MSEs) were considered the affinity function. The AIAE was used to optimize the smooth factors of the GRNN; then, the optimal smooth factor was solved and substituted into the trained GRNN. Thus, the intrusive data were classified. The paper selected a GRNN that was separately optimized using a genetic algorithm (GA), particle swarm optimization (PSO), and fuzzy C-mean clustering (FCM) to enable a comparison of these approaches. As shown in the results, the AIAE-GRNN achieves a higher classification accuracy than PSO-GRNN, but the running time of AIAE-GRNN is long, which was proved first. FCM and GA-GRNN were eliminated because of their deficiencies in terms of accuracy and convergence. To improve the running speed, the paper adopted principal component analysis (PCA) to reduce the dimensions of the intrusive data. With the reduction in dimensionality, the PCA-AIAE-GRNN decreases in accuracy less and has better convergence than the PCA-PSO-GRNN, and the running speed of the PCA-AIAE-GRNN was relatively improved. The experimental results show that the AIAE-GRNN has a higher robustness and accuracy than the other algorithms considered and can thus be used to classify the intrusive data.     

A Monte Carlo EM Algorithm for De Novo Motif Discovery in Biomolecular Sequences

Motif discovery methods play pivotal roles in deciphering the genetic regulatory codes (i.e., motifs) in genomes as well as in locating conserved domains in protein sequences. The Expectation Maximization (EM) algorithm is one of the most popular methods used in de novo motif discovery. Based on the position weight matrix (PWM) updating technique, this paper presents a Monte Carlo version of the EM motif-finding algorithm that carries out stochastic sampling in local alignment space to overcome the conventional EM's main drawback of being trapped in a local optimum. The newly implemented algorithm is named as Monte Carlo EM Motif Discovery Algorithm (MCEMDA). MCEMDA starts from an initial model, and then it iteratively performs Monte Carlo simulation and parameter update until convergence. A log-likelihood profiling technique together with the top-k strategy is introduced to cope with the phase shifts and multiple modal issues in motif discovery problem. A novel grouping motif alignment (GMA) algorithm is designed to select motifs by clustering a population of candidate local alignments and successfully applied to subtle motif discovery. MCEMDA compares favorably to other popular PWM-based and word enumerative motif algorithms tested using simulated (l, d)-motif cases, documented prokaryotic, and eukaryotic DNA motif sequences. Finally, MCEMDA is applied to detect large blocks of conserved domains using protein benchmarks and exhibits its excellent capacity while compared with other multiple sequence alignment methods.     

The Exact Evaluation of 2-way Cross-classifications: An Algorithmic Solution

An algorithm is presented which permits the exact evaluation of sparse cross-classifications and contingency tables. It may be used to compute the exact point and cumulative probabilities of observed values of the X²-like test statistic, or even of the observed tables themselves. For sparser cases, it may also be used to generate part or all of the exact distributions. As a corollary, an operational solution is presented to the enumeration problem of rectangular integer matrices with arbitrarily fixed row and column sums. Exact results obtained with the algorithm accompany this presentation, giving, further support to the recommendation that the Gamma distribution be preferred to the Chi-square in sparse cases.     

A G-Protein Subunit Translocation Embedded Network Motif Underlies GPCR Regulation of Calcium Oscillations

G-protein βγ subunits translocate reversibly from the plasma membrane to internal membranes on receptor activation. Translocation rates differ depending on the γ subunit type. There is limited understanding of the role of the differential rates of G_βγ translocation in modulating signaling dynamics in a cell. Bifurcation analysis of the calcium oscillatory network structure predicts that the translocation rate of a signaling protein can regulate the damping of system oscillation. Here, we examined whether the G_βγ translocation rate regulates calcium oscillations induced by G-protein-coupled receptor activation. Oscillations in HeLa cells expressing γ subunit types with different translocation rates were imaged and quantitated. The results show that differential G_βγ translocation rates can underlie the diversity in damping characteristics of calcium oscillations among cells. Mathematical modeling shows that a translocation embedded motif regulates damping of G-protein-mediated calcium oscillations consistent with experimental data. The current study indicates that such a motif may act as a tuning mechanism to design oscillations with varying damping patterns by using intracellular translocation of a signaling component.     

A G-Protein Subunit Translocation Embedded Network Motif Underlies GPCR Regulation of Calcium Oscillations

G-protein βγ subunits translocate reversibly from the plasma membrane to internal membranes on receptor activation. Translocation rates differ depending on the γ subunit type. There is limited understanding of the role of the differential rates of G_βγ translocation in modulating signaling dynamics in a cell. Bifurcation analysis of the calcium oscillatory network structure predicts that the translocation rate of a signaling protein can regulate the damping of system oscillation. Here, we examined whether the G_βγ translocation rate regulates calcium oscillations induced by G-protein-coupled receptor activation. Oscillations in HeLa cells expressing γ subunit types with different translocation rates were imaged and quantitated. The results show that differential G_βγ translocation rates can underlie the diversity in damping characteristics of calcium oscillations among cells. Mathematical modeling shows that a translocation embedded motif regulates damping of G-protein-mediated calcium oscillations consistent with experimental data. The current study indicates that such a motif may act as a tuning mechanism to design oscillations with varying damping patterns by using intracellular translocation of a signaling component.     

An Extended Active-site Motif Controls the Reactivity of the Thioredoxin Fold

Proteins belonging to the thioredoxin (Trx) superfamily are abundant in all organisms. They share the same structural features, arranged in a seemingly simple fold, but they perform a multitude of functions in oxidative protein folding and electron transfer pathways. We use the C-terminal domain of the unique transmembrane reductant conductor DsbD as a model for an in-depth analysis of the factors controlling the reactivity of the Trx fold. We employ NMR spectroscopy, x-ray crystallography, mutagenesis, in vivo functional experiments applied to DsbD, and a comparative sequence analysis of Trx-fold proteins to determine the effect of residues in the vicinity of the active site on the ionization of the key nucleophilic cysteine of the -CXXC- motif. We show that the function and reactivity of Trx-fold proteins depend critically on the electrostatic features imposed by an extended active-site motif.     

Dispatching and Conflict-Free Routing of Automated Guided Vehicles: An Exact Approach

This article presents an exact solution approach for the problem of the simultaneous dispatching and conflict-free routing of automated guided vehicles. The vehicles carry out material handling tasks in a flexible manufacturing system (FMS). The objective is to minimize the costs related to the production delays. The approach is based on a set partitioning formulation. The proposed model is solved to optimality by a column generation method, which is embedded in a branch-and-cut exploration tree. The proposed model and solution methodology are tested on several scenarios with up to four vehicles in the manufacturing system. The results show that most of these scenarios can be solved to optimality in less than three minutes of computational time.     

An Exact Constant-Field Solution for a Simple Membrane

We show that the exact steady-state solution to the electrodiffusion equations for a simple membrane is the constant electric field solution when the ion environment is electroneutral on both sides of the membrane and the total numbers of ions of the same valence on both sides are equal.     

An RGD Motif Present in Cadherin 17 Induces Integrin Activation and Tumor Growth

Little is known about the mechanism of integrin activation by cadherin 17 (CDH17). Here we observed the presence of a tri-peptide motif, RGD, in domain 6 of the human CDH17 sequence and other cadherins such as cadherin 5 and cadherin 6. The use of CDH17 RAD mutants demonstrated a considerable decrease of proliferation and adhesion in RKO and KM12SM colon cancer cells. Furthermore, RGD peptides inhibited the adhesion of both cell lines to recombinant CDH17 domain 6. The RGD motif added exogenously to the cells provoked a change in β1 integrin to an active, high-affinity conformation and an increase in focal adhesion kinase and ERK1/2 activation. In vivo experiments with Swiss nude mice demonstrated that cancer cells expressing the CDH17 RAD mutant showed a considerable delay in tumor growth and liver homing. CDH17 RGD effects were also active in pancreatic cancer cells. Our results suggest that α2β1 integrin interacts with two different ligands, collagen IV and CDH17, using two different binding sites. In summary, the RGD binding motif constitutes a switch for integrin pathway activation and shows a novel capacity of CDH17 as an integrin ligand. This motif could be targeted to avoid metastatic dissemination in tumors overexpressing CDH17 and other RGD-containing cadherins.