Search

Consider a set of oligomers listing the subunits involved in subcomplexes of a macromolecular assembly, obtained e.g. using native mass spectrometry or affinity purification. Given these oligomers, connectivity inference (CI) consists of finding the most plausible contacts between these subunits, and minimum connectivity inference (MCI) is the variant consisting of finding a set of contacts of smallest cardinality. MCI problems avoid speculating on the total number of contacts but yield a subset of all contacts and do not allow exploiting a priori information on the likelihood of individual contacts. In this context, we present two novel algorithms, MILP-W and MILP-WB. The former solves the minimum weight connectivity inference (MWCI), an optimization problem whose criterion mixes the number of contacts and their likelihood. The latter uses the former in a bootstrap fashion to improve the sensitivity and the specificity of solution sets.Experiments on three systems (yeast exosome, yeast proteasome lid, human eIF3), for which reference contacts are known (crystal structure, cryo electron microscopy, cross-linking), show that our algorithms predict contacts with high specificity and sensitivity, yielding a very significant improvement over previous work, typically a twofold increase in sensitivity.The software accompanying this paper is made available and should prove of ubiquitous interest whenever connectivity inference from oligomers is faced., (© 2015 by The American Society for Biochemistry and Molecular Biology, Inc.)

The k shortest simple path problem (kSSP) asks to compute a set of top-k shortest simple paths from a source to a sink in a digraph. Yen (1971) proposed an algorithm with the best-known polynomial time complexity for this problem. Since then, the problem has been widely studied from an algorithm engineering perspective. The most noticeable proposals are the node-classification (NC) algorithm (Feng, 2014) and the sidetracks-based (SB) algorithm (Kurz, Mutzel, 2016). The latest offers the best running time at the price of a significant memory consumption. We first show how to speed up the SB algorithm using dynamic updates of shortest path trees resulting in a faster algorithm (SB*) with the same memory consumption. We then propose the parsimonious SB (PSB) algorithm that significantly reduces the memory consumption of SB at the cost of a small increase of the running time. Furthermore, we propose the postponed node-classification (PNC) algorithm that combines the best of the NC and the SB algorithms. It offers a significant speed up compared to the SB algorithm while using the same amount of memory as the NC algorithm. Our experimental results on complex networks show that all the considered algorithms have low memory consumption, and that the PSB algorithm is the fastest. On road networks, the relative performances of the algorithms depend on the number k of requested paths. Indeed, when the number k of requested paths is small (i.e., k ≤ 20 in our experiments), the SB* algorithm is the fastest among the considered algorithms, but it suffers from a large memory consumption and it offers very bad performances on some queries. When the number of requested paths is large (i.e., larger than 20 according to our experiments), the PNC algorithm is the fastest among the considered algorithms on road networks and it has a low memory footprint. The PNC algorithm is therefore a better choice on road networks. [ABSTRACT FROM AUTHOR]

Given a graph, its hyperbolicity is a measure of how close its distance distribution is to the one of a tree. This parameter has gained recent attention in the analysis of some graph algorithms and the classification of complex networks. We study on practical improvements for the computation of hyperbolicity in large graphs. Precisely, we investigate on relations between the hyperbolicity of a graph G and the hyperbolicity of its atoms , that are the subgraphs output by the clique-decomposition invented by Tarjan [51,65] . We prove that the maximum hyperbolicity taken over the atoms is at most one unit off from the hyperbolicity of G and the bound is sharp. We also give an algorithm to slightly modify the atoms, called the “substitution method”, which is at no extra cost than computing the clique-decomposition, and so that the maximum hyperbolicity taken over the resulting graphs is exactly the hyperbolicity of the input graph G . An experimental evaluation of our method for computing the hyperbolicity of a given graph from its atoms is provided for collaboration networks and biological networks. Finally, on a more theoretical side, we deduce from our results the first linear-time algorithm for computing the hyperbolicity of an outerplanar graph. [ABSTRACT FROM AUTHOR]

Path decompositions of graphs are an important ingredient of dynamic programming algorithms for solving efficiently many NP-hard problems. Therefore, computing the pathwidth and associated path decomposition of graphs has both a theoretical and practical interest. In this article, we design a branch-and-bound algorithm that computes the exact pathwidth of graphs and a corresponding path decomposition. Our main contribution consists of several nontrivial techniques to reduce the size of the input graph (preprocessing) and to cut the exploration space during the search phase of the algorithm. We evaluate experimentally our algorithm by comparing it to existing algorithms of the literature. It appears from the simulations that our algorithm offers a significant gain with respect to previous work. In particular, it is able to compute the exact pathwidth of any graph with less than 60 nodes in a reasonable running time (≤ 10min on a standard laptop). Moreover, our algorithm achieves good performance when used as a heuristic (i.e., when returning best result found within bounded time limit). Our algorithm is not restricted to undirected graphs since it actually computes the directed pathwidth that generalizes the notion of pathwidth to digraphs. [ABSTRACT FROM AUTHOR]

The Gromov hyperbolicity is an important parameter for analyzing complex networks which expresses how the metric structure of a network looks like a tree. It is for instance used to provide bounds on the expected stretch of greedy-routing algorithms in Internet-like graphs. However, the best-known theoretical algorithm computing this parameter runs in O(n3.69) time, which is prohibitive for large-scale graphs. In this article, we propose an algorithm for determining the hyperbolicity of graphs with tens of thousands of nodes. Its running time depends on the distribution of distances and on the actual value of the hyperbolicity. Although its worst case runtime is O(n4), it is in practice much faster than previous proposals as observed in our experimentations. Finally, we propose a heuristic algorithm that can be used on graphs with millions of nodes. Our algorithms are all evaluated on benchmark instances. [ABSTRACT FROM AUTHOR]

The Gromov hyperbolicity is an important parameter for analyzing complex networks which expresses how the metric structure of a network looks like a tree. It is for instance used to provide bounds on the expected stretch of greedy-routing algorithms in Internet-like graphs. However, the best-known theoretical algorithm computing this parameter runs in O(n3.69) time, which is prohibitive for large-scale graphs. In this article, we propose an algorithm for determining the hyperbolicity of graphs with tens of thousands of nodes. Its running time depends on the distribution of distances and on the actual value of the hyperbolicity. Although its worst case runtime is O(n4), it is in practice much faster than previous proposals as observed in our experimentations. Finally, we propose a heuristic algorithm that can be used on graphs with millions of nodes. Our algorithms are all evaluated on benchmark instances. [ABSTRACT FROM AUTHOR]

The notion of Shared Risk Link Groups (SRLG) has been introduced to capture survivability issues where some links of a network fail simultaneously. In this context, the k-diverse routing problem is to find a set of k pairwise SRLG-disjoint paths between a given pair of end nodes of the network. This problem has been proven NP-complete in general and some polynomial instances have been characterized. In this paper, we investigate the k -diverse routing problem in networks where the SRLGs are localized and satisfy the star property . This property states that a link may be subject to several SRLGs, but all links subject to a given SRLG are incident to a common node. We first provide counterexamples to the polynomial time algorithm proposed by X. Luo and B. Wang (DRCN'05) for computing a pair of SRLG-disjoint paths in networks with SRLGs satisfying the star property, and then prove that this problem is in fact NP-complete. We then characterize instances that can be solved in polynomial time or are fixed parameter tractable, in particular when the number of SRLGs is constant, the maximum degree of the vertices is at most 4, and when the network is a directed acyclic graph. Finally we consider the problem of finding the maximum number of SRLG-disjoint paths in networks with SRLGs satisfying the star property. We prove that this problem is NP-hard to approximate within O ( | V | 1 − ε ) for any 0 < ε < 1 , where V is the set of nodes in the network. Then, we provide exact and approximation algorithms for relevant subcases. [ABSTRACT FROM AUTHOR]

Abstract: We introduce the process number of a digraph as a tool to study rerouting issues in wdm networks. This parameter is closely related to the vertex separation (or pathwidth). We consider the recognition and the characterization of (di)graphs with small process numbers. In particular, we give a linear time algorithm to recognize (and process) graphs with process number at most 2, along with a characterization in terms of forbidden minors, and a structural description. As for digraphs with process number 2, we exhibit a characterization that allows one to recognize (and process) them in polynomial time. [Copyright &y& Elsevier]