Search

Solving combinatorial problems on complex networks represents a primary issue which, on a large scale, requires the use of heuristics and approximate algorithms. Recently, neural methods have been proposed in this context to find feasible solutions for relevant computational problems over graphs. However, such methods have some drawbacks: (1) they use the same neural architecture for different combinatorial problems without introducing customizations that reflects the specificity of each problem; (2) they only use a nodes local information to compute the solution; (3) they do not take advantage of common heuristics or exact algorithms. Following this interest, in this research we address these three main points by designing a customized attention-based mechanism that uses both local and global information from the adjacency matrix to find approximate solutions for the Minimum Vertex Cover Problem. We evaluate our proposal with respect to a fast two-factor approximation algorithm and a widely adopted state-of-the-art heuristic both on synthetically generated instances and on benchmark graphs with different scales. Experimental results demonstrate that, on the one hand, the proposed methodology is able to outperform both the two-factor approximation algorithm and the heuristic on the test datasets, scaling even better than the heuristic with harder instances and, on the other hand, is able to provide a representation of the nodes which reflects the combinatorial structure of the problem.

Abstract The use of networks for modelling and analysing relations among data is currently growing. Recently, the use of a single networks for capturing all the aspects of some complex scenarios has shown some limitations. Consequently, it has been proposed to use Dual Networks (DN), a pair of related networks, to analyse complex systems. The two graphs in a DN have the same set of vertices and different edge sets. Common subgraphs among these networks may convey some insights about the modelled scenarios. For instance, the detection of the Top-k Densest Connected subgraphs, i.e. a set k subgraphs having the largest density in the conceptual network which are also connected in the physical network, may reveal set of highly related nodes. After proposing a formalisation of the approach, we propose a heuristic to find a solution, since the problem is computationally hard. A set of experiments on synthetic and real networks is also presented to support our approach.

Abstract Reconciling gene trees with a species tree is a fundamental problem to understand the evolution of gene families. Many existing approaches reconcile each gene tree independently. However, it is well-known that the evolution of gene families is interconnected. In this paper, we extend a previous approach to reconcile a set of gene trees with a species tree based on segmental macro-evolutionary events, where segmental duplication events and losses are associated with cost $$\delta $$ δ and $$\lambda $$ λ , respectively. We show that the problem is polynomial-time solvable when $$\delta \le \lambda $$ δ≤λ (via LCA-mapping), while if $$\delta > \lambda $$ δ>λ the problem is NP-hard, even when $$\lambda = 0$$ λ=0 and a single gene tree is given, solving a long standing open problem on the complexity of multi-gene reconciliation. On the positive side, we give a fixed-parameter algorithm for the problem, where the parameters are $$\delta /\lambda $$ δ/λ and the number d of segmental duplications, of time complexity $$O\left(\lceil \frac{\delta }{\lambda } \rceil ^{d} \cdot n \cdot \frac{\delta }{\lambda }\right)$$ O⌈δλ⌉d·n·δλ . Finally, we demonstrate the usefulness of this algorithm on two previously studied real datasets: we first show that our method can be used to confirm or raise doubt on hypothetical segmental duplications on a set of 16 eukaryotes, then show how we can detect whole genome duplications in yeast genomes.

Patients who survive brain injuries may develop Disorders of Consciousness (DOC) such as Coma, Vegetative State (VS) or Minimally Conscious State (MCS). Unfortunately, the rate of misdiagnosis between VS and MCS due to clinical judgment is high. Therefore, diagnostic decision support systems aiming to correct any differentiation between VS and MCS are essential for the characterization of an adequate treatment and an effective prognosis. In recent decades, there has been a growing interest in the new EEG computational techniques. We have reviewed how resting-state EEG is computationally analyzed to support differential diagnosis between VS and MCS in view of applicability of these methods in clinical practice. The studies available so far have used different techniques and analyses; it is therefore hard to draw general conclusions. Studies using a discriminant analysis with a combination of various factors and reporting a cut-off are among the most interesting ones for a future clinical application.

The problem of finding the maximum number of vertex-disjoint uni-color paths in an edge-colored graph has been recently introduced in literature, motivated by applications in social network analysis. In this paper we investigate the approximation and parameterized complexity of the problem. First, we show that, for any constant ε > 0, the problem is not approximable within factor c1-ε, where c is the number of colors, and that the corresponding decision problem is W[1]-hard when parametrized by the number of disjoint paths. Then, we present a fixed-parameter algorithm for the problem parameterized by the number and the length of the disjoint paths.

In this special issue, we present two of the papers presented at the 10th Workshop on Biomedical and Bioinformatics Challenges for Computer Science—BBC2017, held in Zurich, 12–14 June 2017.