Parameterized Algorithms for Partial Vertex Covers in Bipartite Graphs
Ontology highlight
ABSTRACT:
SUBMITTER: Gasieniec L
PROVIDER: S-EPMC7254907 | biostudies-literature | 2020 Apr
REPOSITORIES: biostudies-literature
Similar Datasets
Project description:A simple graph G = (V, E) is said to be r-regular if each vertex of G is of degree r. The vertex covering transversal domination number γ vct(G) is the minimum cardinality among all vertex covering transversal dominating sets of G. In this paper, we analyse this parameter on different kinds of regular graphs especially for Q n and H 3,n. Also we provide an upper bound for γ vct of a connected cubic graph of order n ≥ 8. Then we try to provide a more stronger relationship between γ and γ vct.
| S-EPMC4828551 | biostudies-other
Project description:While Boolean logic has been the backbone of digital information processing, there exist classes of computationally hard problems wherein this paradigm is fundamentally inefficient. Vertex coloring of graphs, belonging to the class of combinatorial optimization, represents one such problem. It is well studied for its applications in data sciences, life sciences, social sciences and technology, and hence, motivates alternate, more efficient non-Boolean pathways towards its solution. Here we demonstrate a coupled relaxation oscillator based dynamical system that exploits insulator-metal transition in Vanadium Dioxide (VO2) to efficiently solve vertex coloring of graphs. Pairwise coupled VO2 oscillator circuits have been analyzed before for basic computing operations, but using complex networks of VO2 oscillators, or any other oscillators, for more complex tasks have been challenging in theory as well as in experiments. The proposed VO2 oscillator network harnesses the natural analogue between optimization problems and energy minimization processes in highly parallel, interconnected dynamical systems to approximate optimal coloring of graphs. We further indicate a fundamental connection between spectral properties of linear dynamical systems and spectral algorithms for graph coloring. Our work not only elucidates a physics-based computing approach but also presents tantalizing opportunities for building customized analog co-processors for solving hard problems efficiently.
| S-EPMC5430425 | biostudies-literature
Project description:BACKGROUND:In order to find correlated pairs of positions between proteins, which are useful in predicting interactions, it is necessary to concatenate two large multiple sequence alignments such that the sequences that are joined together belong to those that interact in their species of origin. When each protein is unique then the species name is sufficient to guide this match, however, when there are multiple related sequences (paralogs) in each species then the pairing is more difficult. In bacteria a good guide can be gained from genome co-location as interacting proteins tend to be in a common operon but in eukaryotes this simple principle is not sufficient. RESULTS:The methods developed in this paper take sets of paralogs for different proteins found in the same species and make a pairing based on their evolutionary distance relative to a set of other proteins that are unique and so have a known relationship (singletons). The former constitute a set of unlabelled nodes in a graph while the latter are labelled. Two variants were tested, one based on a phylogenetic tree of the sequences (the topology-based method) and a simpler, faster variant based only on the inter-sequence distances (the distance-based method). Over a set of test proteins, both gave good results, with the topology method performing slightly better. CONCLUSIONS:The methods develop here still need refinement and augmentation from constraints other than the sequence data alone, such as known interactions from annotation and databases, or non-trivial relationships in genome location. With the ever growing numbers of eukaryotic genomes, it is hoped that the methods described here will open a route to the use of these data equal to the current success attained with bacterial sequences.
| S-EPMC5613400 | biostudies-literature
Project description:By combining evolutionary game theory and graph theory, "games on graphs" study the evolutionary dynamics of frequency-dependent selection in population structures modeled as geographical or social networks. Networks are usually represented by means of unipartite graphs, and social interactions by two-person games such as the famous prisoner's dilemma. Unipartite graphs have also been used for modeling interactions going beyond pairwise interactions. In this paper, we argue that bipartite graphs are a better alternative to unipartite graphs for describing population structures in evolutionary multiplayer games. To illustrate this point, we make use of bipartite graphs to investigate, by means of computer simulations, the evolution of cooperation under the conventional and the distributed N-person prisoner's dilemma. We show that several implicit assumptions arising from the standard approach based on unipartite graphs (such as the definition of replacement neighborhoods, the intertwining of individual and group diversity, and the large overlap of interaction neighborhoods) can have a large impact on the resulting evolutionary dynamics. Our work provides a clear example of the importance of construction procedures in games on graphs, of the suitability of bigraphs and hypergraphs for computational modeling, and of the importance of concepts from social network analysis such as centrality, centralization and bipartite clustering for the understanding of dynamical processes occurring on networked population structures.
| S-EPMC3438187 | biostudies-other
Project description:The latest advances in high-throughput techniques during the past decade allowed the systems biology field to expand significantly. Today, the focus of biologists has shifted from the study of individual biological components to the study of complex biological systems and their dynamics at a larger scale. Through the discovery of novel bioentity relationships, researchers reveal new information about biological functions and processes. Graphs are widely used to represent bioentities such as proteins, genes, small molecules, ligands, and others such as nodes and their connections as edges within a network. In this review, special focus is given to the usability of bipartite graphs and their impact on the field of network biology and medicine. Furthermore, their topological properties and how these can be applied to certain biological case studies are discussed. Finally, available methodologies and software are presented, and useful insights on how bipartite graphs can shape the path toward the solution of challenging biological problems are provided.
| S-EPMC6333914 | biostudies-literature
Project description:ODE simulations of chemical systems perform poorly when some of the species have extremely low concentrations. Stochastic simulation methods, which can handle this case, have been impractical for large systems due to computational complexity. We observe, however, that when modeling complex biological systems: (1) a small number of reactions tend to occur a disproportionately large percentage of the time, and (2) a small number of species tend to participate in a disproportionately large percentage of reactions. We exploit these properties in LOLCAT Method, a new implementation of the Gillespie Algorithm. First, factoring reaction propensities allows many propensities dependent on a single species to be updated in a single operation. Second, representing dependencies between reactions with a bipartite graph of reactions and species requires only storage for reactions, rather than the required for a graph that includes only reactions. Together, these improvements allow our implementation of LOLCAT Method to execute orders of magnitude faster than currently existing Gillespie Algorithm variants when simulating several yeast MAPK cascade models.
| S-EPMC2798956 | biostudies-literature
Project description:We have developed a new set of algorithms, collectively called "Velvet," to manipulate de Bruijn graphs for genomic sequence assembly. A de Bruijn graph is a compact representation based on short words (k-mers) that is ideal for high coverage, very short read (25-50 bp) data sets. Applying Velvet to very short reads and paired-ends information only, one can produce contigs of significant length, up to 50-kb N50 length in simulations of prokaryotic data and 3-kb N50 on simulated mammalian BACs. When applied to real Solexa data sets without read pairs, Velvet generated contigs of approximately 8 kb in a prokaryote and 2 kb in a mammalian BAC, in close agreement with our simulated results without read-pair information. Velvet represents a new approach to assembly that can leverage very short reads in combination with read pairs to produce useful assemblies.
| S-EPMC2336801 | biostudies-literature
Project description:It is well known that numerous long noncoding RNAs (lncRNAs) closely relate to the physiological and pathological processes of human diseases and can serves as potential biomarkers. Therefore, lncRNA-disease associations that are identified by computational methods as the targeted candidates reduce the cost of biological experiments focusing on deep study furtherly. However, inaccurate construction of similarity networks and inadequate numbers of observed known lncRNA-disease associations, such inherent problems make many mature computational methods that have been developed for many years still exit some limitations. It motivates us to explore a new computational method that was fused with KATZ measure and space projection to fast probing potential lncRNA-disease associations (namely KATZSP). KATZSP is comprised of following key steps: combining all the global information with which to change Boolean network of known lncRNA-disease associations into the weighted networks; changing the similarities calculation into counting the number of walks that connect lncRNA nodes and disease nodes in bipartite graphs; obtaining the space projection scores to refine the primary prediction scores. The process to fuse KATZ measure and space projection was simplified and uncomplicated with needing only one attenuation factor. The leave-one-out cross validation (LOOCV) experimental results showed that, compared with other state-of-the-art methods (NCPLDA, LDAI-ISPS and IIRWR), KATZSP had a higher predictive accuracy shown with area-under-the-curve (AUC) value on the three datasets built, while KATZSP well worked on inferring potential associations related to new lncRNAs (or isolated diseases). The results from real cases study (such as pancreas cancer, lung cancer and colorectal cancer) further confirmed that KATZSP is capable of superior predictive ability to be applied as a guide for traditional biological experiments.
| S-EPMC8608294 | biostudies-literature
Project description:In this paper, we propose online algorithms for multiclass classification using partial labels. We propose two variants of Perceptron called Avg Perceptron and Max Perceptron to deal with the partially labeled data. We also propose Avg Pegasos and Max Pegasos, which are extensions of the Pegasos algorithm. We also provide mistake bounds for Avg Perceptron and regret bound for Avg Pegasos. We show the effectiveness of the proposed approaches by experimenting on various datasets and comparing them with the standard Perceptron and Pegasos. Electronic supplementary material The online version of this chapter (10.1007/978-3-030-47426-3_20) contains supplementary material, which is available to authorized users.
| S-EPMC7206293 | biostudies-literature
Project description:Normal development of the patella typically involves fusion of secondary ossification centers into a single bone during adolescence, with failure of fusion resulting in bipartite and tripartite patellae. In such variants, injury to incomplete ossification center fusion, though uncommon, has been reported to occur in the setting of traumatic quadriceps tendon rupture. The authors present a rare and complex case of traumatic bipartite fragment separation, patellar avulsion, and a complex partial quadriceps tendon tear confirmed surgically in a 36-year-old male. In this case, a tear in the lateral aspect of the quadriceps tendon attached to the nonfused patellar ossification center resulted in retraction of the band containing the bipartite fragment and separation of the patellar fragments, with superior displacement of the smaller bony avulsion likely due to complex attachments from the medial aspect of the quadriceps tendon. Knowledge of the classical locations of a bipartite and tripartite patella can aid in the differentiation of the anatomic variant versus patellar avulsion. Additionally, knowledge of the variable and complex nature of the quadriceps tendon aids in understanding the process of patellar avulsions and various tears, leading to the appropriate orthopedic management.
| S-EPMC6412164 | biostudies-literature