Variable neighborhood search for partitioning sparse biological networks into the maximum edge-weighted k-plexes.

07:00 EST 7th February 2019 | BioPortfolio

Summary of "Variable neighborhood search for partitioning sparse biological networks into the maximum edge-weighted k-plexes."

In a network, a k-plex represents a subset of n vertices where the degree of each vertex in the subnetwork induced by this subset is at least n-k. The maximum edge-weight k-plex partitioning problem is to find the k-plex partitioning in edge-weighted network, such that the sum of edge weights is maximal. The Max-EkPP has an important role in discovering new information in large biological networks. We propose a variable neighborhood search (VNS) algorithm for solving Max-EkPP. The VNS implements a local search based on the 1-swap first improvement strategy and the objective function that takes into account the degree of every vertex in each partition. The objective function favors feasible solutions and enables a gradual increase of the function's value, when moving from slightly infeasible to barely feasible solutions. Experimental computation is performed on real metabolic networks and other benchmark instances from the literature. Comparing to the previously proposed integer linear programming (ILP), VNS succeeds to find all known optimal solutions. For all other instances, the VNS either reaches previous best known solution or improves it. The proposed VNS is also tested on a large-scale dataset not considered up to now.


Journal Details

This article was published in the following journal.

Name: IEEE/ACM transactions on computational biology and bioinformatics
ISSN: 1557-9964


DeepDyve research library

PubMed Articles [12403 Associated PubMed Articles listed on BioPortfolio]

Detecting list-colored graph motifs in biological networks using branch-and-bound strategy.

In this work, we study the list-colored graph motif problem, which was introduced to detect functional motifs in biological networks. Given a multi-set M of colors as the query motif and a list-colore...

Computational methods for identifying the critical nodes in biological networks.

A biological network is complex. A group of critical nodes determines the quality and state of such a network. Increasing studies have shown that diseases and biological networks are closely and mutua...

Scale-Free Loopy Structure Is Resistant to Noise in Consensus Dynamics in Complex Networks.

The vast majority of real-world networks are scale-free, loopy, and sparse, with a power-law degree distribution and a constant average degree. In this paper, we study first-order consensus dynamics i...

Neighborhood environment, self-rated health and quality of life in Latin America.

To conduct a systematic review examining the associations between neighborhood environments and self-rated health (SRH) and health-related quality of life (HR-QOL) in the urban context of Latin Americ...

Causal Queries from Observational Data in Biological Systems via Bayesian Networks: An Empirical Study in Small Networks.

Biological networks are a very convenient modeling and visualization tool to discover knowledge from modern high-throughput genomics and post-genomics data sets. Indeed, biological entities are not is...

Clinical Trials [3172 Associated Clinical Trials listed on BioPortfolio]

Neighborhood-Level Influences on All-Cause Mortality

To test the independent and interrelated effects of the neighborhood social environment, the neighborhood physical environment, and individual risk factors in predicting all-cause and card...

Longitudinal Study of Neighborhood Predictors of CVD

To examine how neighborhood-level factors interact with individual characteristics to predict incidence of cardiovascular disease and all-cause mortality.

Health, Environment and Action in Louisville (HEAL) Green Heart Louisville Project

The purpose of this study is to examine how the environment and neighborhood characteristics affects the health of the area residents. The study will help determine how changing neighborho...

Effect of Different Protein Diets on Glucose and Insulin Metabolism and Substrate Partitioning

The purpose of this study is to determine whether different protein diets affects glucose and insulin metabolism and substrate partitioning.

Safety Study of the Ventricular Partitioning Device (VPD) Implant System in Heart Failure Patients

The CardioKinetix Ventricular Partitioning Device (VPD) is intended to isolate the malfunctioning portion of the left ventricle in patients with symptoms of heart failure due to ischemic h...

Medical and Biotech [MESH] Definitions

A computer architecture, implementable in either hardware or software, modeled after biological neural networks. Like the biological system in which the processing capability is a result of the interconnection strengths between arrays of nonlinear processing nodes, computerized neural networks, often called perceptrons or multilayer connectionist models, consist of neuron-like units. A homogeneous group of units makes up a layer. These networks are good at pattern recognition. They are adaptive, performing tasks by example, and thus are better for decision-making than are linear learning machines or cluster analysis. They do not require explicit programming.

A partitioning within cells due to the selectively permeable membranes which enclose each of the separate parts, e.g., mitochondria, lysosomes, etc.

Measurable biological (physiological, biochemical, and anatomical features), behavioral (psychometric pattern) or cognitive markers that are found more often in individuals with a disease than in the general population. Because many endophenotypes are present before the disease onset and in individuals with heritable risk for disease such as unaffected family members, they can be used to help diagnose and search for causative genes.

Procedures for finding the mathematical function which best describes the relationship between a dependent variable and one or more independent variables. In linear regression (see LINEAR MODELS) the relationship is constrained to be a straight line and LEAST-SQUARES ANALYSIS is used to determine the best fit. In logistic regression (see LOGISTIC MODELS) the dependent variable is qualitative rather than continuously variable and LIKELIHOOD FUNCTIONS are used to find the best relationship. In multiple regression, the dependent variable is considered to depend on more than a single independent variable.

Complex pharmaceutical substances, preparations, or agents of organic origin, usually obtained by biological methods or assay. They are used especially in diagnosis and treatment of disease (as vaccines or pollen extracts). Biological products are differentiated from BIOLOGICAL FACTORS in that the latter are compounds with biological or physiological activity made by living organisms. (From Webster's 3d ed)

Quick Search


DeepDyve research library

Relevant Topic

Biological Therapy
Biological therapy involves the use of living organisms, substances derived from living organisms, or laboratory-produced versions of such substances to treat disease. Some biological therapies for cancer use vaccines or bacteria to stimulate the body&rs...

Searches Linking to this Article