SciCombinator

Discover the most talked about and latest scientific content & concepts.

Concept: Clique problem

171

The maximum clique enumeration (MCE) problem asks that we identify all maximum cliques in a finite, simple graph. MCE is closely related to two other well-known and widely-studied problems: the maximum clique optimization problem, which asks us to determine the size of a largest clique, and the maximal clique enumeration problem, which asks that we compile a listing of all maximal cliques. Naturally, these three problems are NP-hard, given that they subsume the classic version of the NP-complete clique decision problem. MCE can be solved in principle with standard enumeration methods due to Bron, Kerbosch, Kose and others. Unfortunately, these techniques are ill-suited to graphs encountered in our applications. We must solve MCE on instances deeply seeded in data mining and computational biology, where high-throughput data capture often creates graphs of extreme size and density. MCE can also be solved in principle using more modern algorithms based in part on vertex cover and the theory of fixed-parameter tractability (FPT). While FPT is an improvement, these algorithms too can fail to scale sufficiently well as the sizes and densities of our datasets grow.

Concepts: Graph theory, Problem solving, Optimization, Computational complexity theory, NP-complete, Clique problem, Bron–Kerbosch algorithm, Parameterized complexity

0

In recent years, industrial wireless networks (IWNs) have been transformed by the introduction of mobile nodes, and they now offer increased extensibility, mobility, and flexibility. Nevertheless, mobile nodes pose efficiency and reliability challenges. Efficient node deployment and management of channel interference directly affect network system performance, particularly for key node placement in clustered wireless networks. This study analyzes this system model, considering both industrial properties of wireless networks and their mobility. Then, static and mobile node coverage problems are unified and simplified to target coverage problems. We propose a novel strategy for the deployment of clustered heads in grouped industrial mobile wireless networks (IMWNs) based on the improved maximal clique model and the iterative computation of new candidate cluster head positions. The maximal cliques are obtained via a double-layer Tabu search. Each cluster head updates its new position via an improved virtual force while moving with full coverage to find the minimal inter-cluster interference. Finally, we develop a simulation environment. The simulation results, based on a performance comparison, show the efficacy of the proposed strategies and their superiority over current approaches.

Concepts: Wavelength, Computer network, Proposal, Head, Tabu search, Clique problem, Bron–Kerbosch algorithm, Clique

0

Characterization of the chemical components of complex mixtures in solution is important in many areas of biochemistry and chemical biology, including metabolomics. The use of 2D NMR total correlation spectroscopy (TOCSY) experiments has proven very useful for the identification of known metabolites as well as for the characterization of metabolites that are unknown by taking advantage of the good resolution and high sensitivity of this homonuclear experiment. Due to the complexity of the resulting spectra, automation is critical to facilitate and speed-up their analysis and enable high-throughput applications. To better meet these emerging needs, an automated spin-system identification algorithm of TOCSY spectra is introduced that represents the cross-peaks and their connectivities as a mathematical graph, for which all subgraphs are determined that are maximal cliques. Each maximal clique can be assigned to an individual spin system thereby providing a robust deconvolution of the original spectrum for the easy extraction of critical spin system information. The approach is demonstrated for a complex metabolite mixture consisting of 20 compounds and for E. coli cell lysate.

Concepts: Metabolism, Chemistry, Chemical substance, Mixture, Chemical compound, Metabolite, Metabolomics, Clique problem

0

Kernel-based nonlinear mixing models have been applied to unmix spectral information of hyperspectral images when the type of mixing occurring in the scene is too complex or unknown. Such methods, however, usually require the inversion of matrices of sizes equal to the number of spectral bands. Reducing the computational load of these methods remains a challenge in large scale applications. This paper proposes a centralized band selection (BS) method for supervised unmixing in the reproducing kernel Hilbert space (RKHS). It is based upon the coherence criterion, which sets the largest value allowed for correlations between the basis kernel functions characterizing the selected bands in the unmixing model. We show that the proposed BS approach is equivalent to solving a maximum clique problem (MCP), i.e., searching for the biggest complete subgraph in a graph. Furthermore, we devise a strategy for selecting the coherence threshold and the Gaussian kernel bandwidth using coherence bounds for linearly independent bases. Simulation results illustrate the efficiency of the proposed method.

Concepts: Mathematics, Hilbert space, Vector space, Linear algebra, Selection, Reproducing kernel Hilbert space, Clique problem, Bron–Kerbosch algorithm

0

We present a novel approach for feature correspondence and multiple structure discovery in computer vision. In contrast to existing methods, we exploit the fact that point-sets on the same structure usually lie close to each other, thus forming clusters in the image. Given a pair of input images, we initially extract points of interest and extract hierarchical representations by agglomerative clustering. We use the maximum weighted clique problem to find the set of corresponding clusters with maximum number of inliers representing the multiple structures at the correct scales. Our method is parameter-free and only needs two sets of points along with their tentative correspondences, thus being extremely easy to use. We demonstrate the effectiveness of our method in multiple-structure fitting experiments in both publicly available and in-house datasets. As shown in the experiments, our approach finds a higher number of structures containing fewer outliers compared to state-of-the-art methods.

Concepts: Mathematics, Structure, Hierarchy, Science, Java, Musical form, Maslow's hierarchy of needs, Clique problem

0

Sub-networks can expose complex patterns in an entire bio-molecular network by extracting interactions that depend on temporal or condition-specific contexts. When genes interact with each other during cellular processes, they may form differential co-expression patterns with other genes across different cell states. The identification of condition-specific sub-networks is of great importance in investigating how a living cell adapts to environmental changes. In this work, we propose the weighted MAXimum clique (WMAXC) method to identify a condition-specific sub-network. WMAXC first proposes scoring functions that jointly measure condition-specific changes to both individual genes and gene-gene co-expressions. It then employs a weaker formula of a general maximum clique problem and relates the maximum scored clique of a weighted graph to the optimization of a quadratic objective function under sparsity constraints. We combine a continuous genetic algorithm and a projection procedure to obtain a single optimal sub-network that maximizes the objective function (scoring function) over the standard simplex (sparsity constraints). We applied the WMAXC method to both simulated data and real data sets of ovarian and prostate cancer. Compared with previous methods, WMAXC selected a large fraction of cancer-related genes, which were enriched in cancer-related pathways. The results demonstrated that our method efficiently captured a subset of genes relevant under the investigated condition.

Concepts: Genetics, Cell, Mathematics, Operations research, Identification, Optimization, Polytope, Clique problem