The prediction of protein structures is an important problem in molecular biology.In spite of the large efforts from the research community, and of the recent development of artificial intelligence tools specifically designed for this problem, a complete and definitive solution to the problem has not been found yet.This work is based on the observation that many tools for the prediction of protein conformations rely on both local and non-local geometrical information, even though the non-local information can be very hard to identify within the desired precision in some particular situations.For this reason, we explore in this work the effect of local geometry on methods capable of constructing protein conformations.This initial study has the final aim of devising new alternative methods where the predictions may be guided mainly by the local geometry of proteins.

Given a vector $y \in \mathbb{R}^n$ and a matrix $H \in \mathbb{R}^{n\times m}$, the sparse approximation problem $\mathcal P_{0/p}$ asks for a point $x$ such that $\|y - Hx\|_p \leq \alpha$, for a given scalar $\alpha$, minimizing the size of the support $\|x\|_0 := \#\{j \ |\ x_j \neq 0 \}$. Existing convex mixed-integer programming formulations for $\mathcal P_{0/p}$ are of a kind referred to as “big-$M$”, meaning that they involve the use of a bound $M$ on the values of $x$. When a proper value for $M$ is not known beforehand, these formulations are not exact, in the sense that they may fail to recover the wanted global minimizer. In this work, we study the polytopes arising from these formulations and derive valid inequalities for them. We first use these inequalities to design a branch-and-cut algorithm for these models. Additionally, we prove that these inequalities are sufficient to describe the set of feasible supports for $\mathcal P_{0/p}$. Based on this result, we introduce a new (and the first to our knowledge) $M$-independent integer linear programming formulation for $\mathcal P_{0/p}$, which guarantees the recovery of the global minimizer. We propose a practical approach to tackle this formulation, which has exponentially many constraints. The proposed methods are then compared in computational experimentation to test their potential practical contribution.

Abstract We present a two‐phase methodology to address the problem of optimally deploying indoor wireless local area networks. In the first phase, we use Helmholtz's equation to simulate electromagnetic fields in a typical environment such as an office floor. The linear system which results from the discretization of this partial differential equation is solved with a state‐of‐the‐art library for sparse linear algebra. In the second phase, we formulate the network deployment problem in the setting of binary linear programming. This formulation employs the simulator output as input parameters, and jointly optimizes the number of access points, their locations, and their emission channels. We prove that this optimization problem is NP‐Hard, and use mathematical programming based techniques and heuristics to solve it. We present numerical experiments on medium‐sized buildings.

The use of random projections in mathematical programming allows standard solution algorithms to solve instances of much larger sizes, at least approximately. Approximation results have been derived in the relevant literature for many specific problems, as well as for several mathematical programming subclasses. Despite the theoretical developments, it is not always clear that random projections are actually useful in solving mathematical programs in practice. In this paper we provide a computational assessment of the application of random projections to linear programming.

The Distance Geometry Problem (DGP) consists of finding the coordinates of a given set of points where the distances between some pairs of points are known. The DGP has several applications and one of the most relevant ones arises in the context of structural biology, where NMR experiments are performed to estimate distances between some atom pairs in a given molecule, and the possible conformations for the molecule are calculated through the formulation and the solution of a DGP. We focus our attention on DGP instances for which some special assumptions allow us to discretize the DGP search space and to potentially perform the complete enumeration of the solution set. We refer to the subclass of DGP instances satisfying such discretizability assumptions as the Discretizable DGP (DDGP). In this context, we propose a new procedure for the generation of DDGP instances where real data and simulated data (from known molecular models) can coexist. Our procedure can give rise to peculiar DDGP instances that we use for studying the impact of every distance type, involved in NMR protein structure determination, on the quality of the found solutions. Surprisingly, our experiments suggest that the distance types implying a larger effect on the solution quality are not the ones related to NMR data, but rather the more abundant, but much less informative, van der Waals distance type.

We discuss some properties of generative models for word embeddings. Namely, (Arora & Al., 2016) proposed a latent discourse model implying the concentration of the partition function of the word vectors. This concentration phenomenon led to an asymptotic linear relation between the pointwise mutual information (PMI) of pairs of words and the scalar product of their vectors. Here, we first revisit this concentration phenomenon and prove it under slightly weaker assumptions, for a set of random vectors symmetrically distributed around the origin. Second, we empirically evaluate the relation between PMI and scalar products of word vectors satisfying the concentration property. Our empirical results indicate that, in practice, this relation does not hold with arbitrarily small error. This observation is further supported by two theoretical results: (i) the error cannot be exactly zero because the corresponding shifted PMI matrix cannot be positive semidefinite; (ii) under mild assumptions, there exist pairs of words for which the error cannot be close to zero. We deduce that either natural language does not follow the assumptions of the considered generative model, or the current word vector generation methods do not allow the construction of the hypothesized word embeddings.

With the most recent releases of MD-JEEP, new relevant features have been included to our software tool.MD-JEEP solves instances of the class of Discretizable Distance Geometry Problems (DDGPs), which ask to find possible realizations, in a Euclidean space, of a simple weighted undirected graph for which distance constraints between vertices are given, and for which a discretization of the search space can be supplied.Since its version 0.3.0,MD-JEEP is able to deal with instances containing interval data.We focus in this short paper on the most recent release MD-JEEP 0.3.2:among the new implemented features, we will focus our attention on three features: (i) an improved procedure for the generation and update of the boxes used in the coarse-grained representation (necessary to deal with instances containing interval data); (ii) a new procedure for the selection of the so-called discretization vertices (necessary to perform the discretization of the search space); (iii) the implementation of a general parser which allows the user to easily load DDGP instances in a given specified format.The source code of MD-JEEP 0.3.2 is available on GitHub, where the reader can find all additional details about the implementation of such new features, as well as verify the effectiveness of such features by comparing MD-JEEP 0.3.2 with its previous releases.

Nuclear Magnetic Resonance (NMR) experiments provide distances between nearby atoms of a protein molecule. The corresponding structure determination problem is to determine the 3D protein structure by exploiting such distances. We present a new order on the atoms of the protein, based on information from the chemistry of proteins and NMR experiments, which allows us to formulate the problem as a combinatorial search. Additionally, this order tells us what kind of NMR distance information is crucial to understand the cardinality of the solution set of the problem and its computational complexity.

Abstract Business rules (BR) have the form ⟨if condition then action⟩. A BR program, which can be executed by means of an interpreter, is a sequence of business rules. Motivated by International Business Machines use cases, we look at the problem of setting parameter values in a given BR program so it will achieve a given average goal over all possible instances. We explore the following fundamental question: Is there a general learning algorithm, which addresses this issue? We prove the answer is negative. On the positive side, we derive operational semantics for BR programs. As a proof of concept, we show empirically that these can be used to detect potential nontermination situations.

The fundamental problem of distance geometry consists in finding a realization of a given weighted graph in a Euclidean space of given dimension, in such a way that vertices are realized as points and edges as straight segments having the same lengths as their given weights. This problem arises in structural proteomics, wireless sensor networks, and clock synchronization protocols to name a few applications. The well-known Isomap method is a dimensionality reduction heuristic which projects finite but high dimensional metric spaces into the "most significant" lower dimensional ones, where significance is measured by the magnitude of the corresponding eigenvalues. We start from a simple observation, namely that Isomap can also be used to provide approximate realizations of weighted graphs very efficiently, and then derive and benchmark six new heuristics.

The automated real time control of an electrical network is achieved through the estimation of its state using phasor measurement units. Given an undirected graph representing the network, we study the problem of finding the minimum number of phasor measurement units to place on the edges such that the graph is fully observed. This problem is also known as the Power Edge Set problem, a variant of the Power Dominating Set problem. It is naturally modeled using an iteration‐indexed binary linear program, whose size turns out to be too large for practical purposes. We use a fixed‐point argument to remove the iteration indices and obtain a more compact bilevel formulation. We then reformulate the latter to a single‐level mixed‐integer linear program, which performs better than the natural formulation. Lastly, we provide an algorithm that solves the bilevel program directly and much faster than a commercial solver can solve the previous models. We also discuss robust variants and extensions of the problem. © 2016 Wiley Periodicals, Inc. NETWORKS, Vol. 68(2), 104–120 2016

BACKGROUND: The determination of protein structures satisfying distance constraints is an important problem in structural biology. Whereas the most common method currently employed is simulated annealing, there have been other methods previously proposed in the literature. Most of them, however, are designed to find one solution only. RESULTS: In order to explore exhaustively the feasible conformational space, we propose here an interval Branch-and-Prune algorithm (iBP) to solve the Distance Geometry Problem (DGP) associated to protein structure determination. This algorithm is based on a discretization of the problem obtained by recursively constructing a search space having the structure of a tree, and by verifying whether the generated atomic positions are feasible or not by making use of pruning devices. The pruning devices used here are directly related to features of protein conformations. CONCLUSIONS: We described the new algorithm iBP to generate protein conformations satisfying distance constraints, that would potentially allows a systematic exploration of the conformational space. The algorithm iBP has been applied on three α-helical peptides.

This paper addresses the design of joint source-channel variable-length codes with maximal free distance for given codeword lengths. While previous design methods are mainly based on bounds on the free distance of the code, the proposed algorithm exploits an exact characterization of the free distance. The code optimization is cast in the framework of mixed-integer linear programming and allows to tackle practical alphabet sizes in reasonable computing time.

Abstract The computation of point‐to‐point shortest paths on time‐dependent road networks has a large practical interest, but very few works propose efficient algorithms for this problem. We propose a novel approach, which tackles one of the main complications of route planning in time‐dependent graphs, which is the difficulty of using bidirectional search: because the exact arrival time at the destination is unknown, we start a backward search from the destination node using lower bounds on arc costs to restrict the set of nodes that have to be explored by the forward search. Our algorithm is based onA* with landmarks (ALT); extensive computational results show that it is very effective in practice if we are willing to accept a small approximation factor, resulting in a speed‐up of more than one order of magnitude with respect to Dijkstra's algorithm while finding only slightly suboptimal solutions. The main idea presented here can also be generalized to other types of search algorithms. © 2011 Wiley Periodicals, Inc. NETWORKS, 2012

Shortest paths on road networks can be efficiently calculated using Dijkstra's algorithm (D). In addition to roads, multi-modal transportation networks include public transportation, bicycle lanes, etc. For paths on this type of network, further constraints, e.g., preferences in using certain modes of transportation, may arise. The regular language constrained shortest path problem deals with this kind of problem. It uses a regular language to model the constraints. The problem can be solved efficiently by using a generalization of Dijkstra's algorithm (D_RegLC). In this paper we propose an adaption of the speed-up technique uniALT, in order to accelerate D_RegLC. We call our algorithm SDALT. We provide experimental results on a realistic multi-modal public transportation network including time-dependent cost functions on arcs. The experiments show that our algorithm performs well, with speed-ups of a factor 2 to 20.

We consider the Molecular Distance Geometry Problem (MDGP), which is the problem of finding the conformation of a molecule from some known distances between its atoms. Such distances can be estimated by performing experiments of Nuclear Magnetic Resonance (NMR). Unfortunately, data obtained during these experiments are usually noisy and affected by errors. In particular, some of the estimated distances can be wrong, typically because assigned to the wrong pair of atoms. When particular assumptions are satisfied, the problem can be discretized, and solved by employing an ad-hoc algorithm called Branch & Prune (BP). However, this algorithm has been proved to be less efficient than a meta-heuristic algorithm when the percentage of wrong distances is large. We propose a parallel version of the BP algorithm which is able to handle this kind of instances. The scalability of the proposed algorithm allows for solving very large instances containing wrong distances. Implementation details of the algorithm in C/MPI are discussed, and computational experiments, performed on the nation-wide grid infrastructure Grid5000, are presented.

We consider the Discretizable Molecular Distance Geometry Problem (DMDGP), which consists in a subclass of instances of the distance geometry problem related to molecular conformations for which a combinatorial reformulation can be supplied. We investigate the performances of two different algorithms for solving the DMDGP. The first one is the Branch and Prune (BP) algorithm, an exact algorithm that is strongly based on the structure of the combinatorial problem. The second one is the Monkey Search (MS) algorithm, a meta-heuristic algorithm that is inspired by the behavior of a monkey climbing trees in search for food supplies, and that exploits ideas and strategies from other meta-heuristic searches, such Genetic Algorithms, Differential Evolution, and so on. The comparison between the two algorithms is performed on a set of instances related to protein conformations. The used instances simulate data obtained from the Nuclear Magnetic Resonance (NMR), because the typical distances provided by NMR are considered and a predetermined number of wrong distances are included.