The Subset Sum Problem (SSP) is one of those combinatorial problems that are very easy to understand (take a bunch of integer numbers and verify whether there exists a subset of these numbers which sums up to a given target integer), but it can be very difficult to solve.The SSP is actually an NPcomplete problem, but it is "weakly" NP-hard, implying that there are instances of SSP that can be solved in polynomial time.For this particular problem, the instance hardness can be measured by evaluating the so-called "density" index, which basically compares the number of involved integer numbers to the number of bits we need for their binary representation.In our preliminary study on the use of adiabatic quantum computing for the SSP, we investigate the actual feasibility in solving hard instances of the problem.In fact, hard SSP instances are those requiring a large number of bits for the representation of the integers, while the analog nature of the quantum computer does not allow us to ensure highly accurate integer representations.Some preliminary computational experiments performed on D-Wave quantum annealer are presented and compared to standard solvers for classical computers.

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.

The de facto standard for storing human motion data on a computer involves a representation based on Euler angles.This representation, while effective, has several shortcomings.Triplets of Euler angles are not unique, and the same posture may be expressed using different combinations of angles.Furthermore, many possible Euler angle triplets correspond to unnatural positions for human joints.This means that, in general, a large part of the representational space remains unused.In this paper, we further investigate a recently proposed representation inspired by molecular representations.It uses only two (instead of three) degrees of freedom per joint: a vector and a torsion angle.Using the two key ingredients of this new representation, we present a complete analysis of the Graphics Lab Motion Capture Database.The data found in this analysis provide us with some powerful insights about natural and unnatural human postures in human motions.These insights can potentially lead to possible constraints on human motions which may be used to more effectively solve open problems in the computer graphics community, most notably the problem of (human) motion adaptation.

We present a GPU implementation in C and CUDA of a matrix-by-vector procedure that is particularly tailored to a special class of distance geometry problems in dimension 1, which we name "paradoxical DGP instances".This matrix-byvector reformulation was proposed in previous studies on an optical processor specialized for this kind of computations.Our computational experiments show that a consistent speed-up is observed when comparing our GPU implementation against a standard algorithm for distance geometry, called the Branchand-Prune algorithm.These results confirm that a suitable implementation of the matrix-by-vector procedure in the context of optic computing is very promising.We also remark, however, that the total number of detected solutions grows with the instance size in our implementations, which appears to be an important limitation to the effective implementation of the optical processor.

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.

Distance-based motion adaptation leads to the formulation of a dynamical Distance Geometry Problem (dynDGP) where the involved distances simultaneously represent the morphology of the animated character, as well as a possible motion.The explicit use of inter-joint distances allows us to easily verify the presence of joint contacts, which one generally wishes to preserve when adapting a given motion to characters having a different morphology.In this work, we focus our attention on suitable representations of human-like animated characters, and study the advantages (and disadvantages) in using some of them.In the initial works on distance-based motion adaptation, a 3ndimensional vector was employed for representing the positions of the n joints of the character at a given frame.Here, we investigate the use of another, very popular in computer graphics, representation that basically replaces every joint position in the three-dimensional space with a set of three sorted Euler angles.We show that the latter can in fact be useful for avoiding some of the artifacts that were observed in previous computational experiments, but we argue that this Euler-angle representation, from a motion adaptation point of view, does not seem to be the optimal one.By paying particular attention to the degrees of freedom of the studied representations, it turns out that a novel character representation, inspired by representations used in structural biology for molecules, may allow us to reduce the character degrees of freedom to their minimal value.As a result, statistical analysis on human motion databases, where the motions are given with this new representation, can potentially provide important insights on human motions.This study is an initial step towards the identification of a full set of constraints capable of ensuring that unnatural postures for humans cannot be created while tackling motion adaptation problems.

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.

The Distance Geometry Problem (DGP) asks whether a simple weighted undirected graph can be realized in a given space (generally Euclidean) so that a given set of distance constraints (associated to the edges of the graph) is satisfied.The Discretizable DGP (DDGP) represents a subclass of instances where the search space can be reduced to a discrete domain having the structure of a tree.In the ideal case where all distances are precise, the tree is binary and one singleton, representing one possible position for a vertex of the graph, is associated to every tree node.When the distance information is however not precise, the uncertainty on the distance values implies that a three-dimensional region of the search space needs to be assigned to some nodes of the tree.By using a recently proposed coarse-grained representation for DDGP solutions, we extend in this work the branch-and-prune (BP) algorithm so that it can efficiently perform an exhaustive search of the search domain, even when the uncertainty on the distances is important.Instead of associating singletons to nodes, we consider a pair consisting of a box and of a most-likely position for the vertex in this box.Initial estimations of the vertex positions in every box can be subsequently refined by using local optimization.The aim of this paper is two-fold: (i) we propose a new simple method for the computation of the three-dimensional boxes to be associated to the nodes of the search tree; (ii) we introduce the resolution parameter ρ, with the aim of controling the similarity between pairs of solutions in the solution set.Some initial computational experiments show that our algorithm extension, differently from previously proposed variants of the BP algorithm, is actually able to terminate the enumeration of the solution set by providing solutions that differ from one another accordingly to the given resolution parameter.

The prior knowledge of real human body shapes and poses is fundamental in computer games and animation (e.g. performance capture). Linear subspaces such as the popular SMPL model have a limited capacity to represent the large geometric variations of human shapes and poses. What is worse is that random sampling from them often produces non-realistic humans because the distribution of real humans is more likely to concentrate on a non-linear manifold instead of the full subspace. Towards this problem, we propose to learn human shape and pose manifolds using a more powerful deep generator network, which is trained to produce samples that cannot be distinguished from real humans by a deep discriminator network. In contrast to previous work that learn both the generator and discriminator in the original geometry spaces, we learn them in the more representative latent spaces discovered by a shape and a pose auto-encoder network respectively. Random sampling from our priors produces higher-quality human shapes and poses. The capacity of our priors is best applied to applications such as virtual human synthesis in games.

The selection of relevant features in large databases is one of the most important and challenging problems in data mining.Samples forming a given database are generally described by a predefined set of features, and the situation where not all such features can be used for classification purposes needs very often to be faced in real applications.This situation is very typical when the database is related to a phenomenon whose characteristics are not well known.In this context, the extraction of relevant features can therefore also provide additional information on the studied phenomena.We tackle the feature selection problem from an optimization point of view, by reducing it to the problem of finding a maximal consistent "clustering" grouping together the samples and the features of the database.In this work, we extend this approach to dynamical databases, where features are not represented by only one real value, but they are rather given as sequences of a predefined number of real values.Our main contribution consists in proposing an alternative representation of the database so that it fits with a tridimensional matrix with no missing entries, from which a consistent triclustering can be obtained.

Retargeting motion from one character to another is a key process in computer animation. It enables to reuse animations designed for a character to animate another one, or to make performance-driven be faithful to what has been performed by the user. Previous work mainly focused on retargeting skeleton animations whereas the contextual meaning of the motion is mainly linked to the relationship between body surfaces, such as the contact of the palm with the belly. In this paper we propose a new context-aware motion retargeting framework, based on deforming a target character to mimic a source character poses using harmonic mapping. We also introduce the idea of Context Graph: modeling local interactions between surfaces of the source character, to be preserved in the target character, in order to ensure fidelity of the pose. In this approach, no rigging is required as we directly manipulate the surfaces, which makes the process totally automatic. Our results demonstrate the relevance of this automatic rigging-less approach on motions with complex contacts and interactions between the character's surface.

Human-like characters can be modeled by suitable skeletal structures, which basically consist in trees where edges represent bones and vertices are joints between two adjacent bones.Motion is then defined as variations of the joints' configuration (i.e., partial rotations) over time, which also influences joint positions.However, this representation does not allow to easily represent the relationship between joints that are not directly connected by a bone.This work is therefore based on the premise that variations of the relative distances between such joints are important to represent complex human motions.While the former representations are currently used in practice for playing and analyzing motions, the latter can help in modeling a new class of problems where the relationships in human motions need to be simulated.Our main interest in this work is in adapting previously captured human postures (one frame of a given motion) with the aim of satisfying a certain number of geometrical constraints, which turn out to be easily definable in terms of distances.We present a novel procedure for approximating the relative inter-joint distances for skeletal structures having arbitrary features and respecting a predefined posture.This set of inter-joint distances defines an instance of the Distance Geometry Problem (DGP), that we tackle with a non-monotone spectral gradient method.

In character animation, it is often the case that motions created or captured on a specific morphology need to be reused on characters having a different morphology while maintaining specific relationships such as body contacts or spatial relationships between body parts. This process, called motion retargeting, requires determining which body part relationships are important in a given animation. This paper presents a novel frame-based approach to motion retargeting which relies on a normalized representation of body joints distances. We propose to abstract postures by computing all the inter-joint distances of each animation frame and store them in Euclidean Distance Matrices (EDMs). They 1) present the benefits of capturing all the subtle relationships between body parts, 2) can be adapted through a normalization process to create a morphology-independent distance-based representation, and 3) can be used to efficiently compute retargeted joint positions best satisfying newly computed distances. We demonstrate that normalized EDMs can be efficiently applied to a different skeletal morphology by using a Distance Geometry Problem (DGP) approach, and present results on a selection of motions and skeletal morphologies. Our approach opens the door to a new formulation of motion retargeting problems, solely based on a normalized distance representation.

Given a set of points in a Euclidean space having dimension K > 0, we are interested in the problem of finding a realization of the same set in a Euclidean space having a lower dimension.In most situations, it is not possible to preserve all available interpoint distances in the new space, so that the best possible realization, which gives the minimal error on the distances, needs to be searched.This problem is known in the scientific literature as the Multidimensional Scaling (MDS).We propose a new methodology to discretize the search space of MDS instances, with the aim of performing an efficient enumeration of their solution sets.Some preliminary computational experiments on a set of artificially generated instances are presented.We conclude our paper with some future research directions.

International audience

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.

The Molecular Distance Geometry Problem (MDGP) is the one of finding molecular conformations that satisfy a set of distance constraints obtained through experimental techniques such as Nuclear Magnetic Resonance (NMR).We consider a subclass of MDGP instances that can be discretized, where the search domain has the structure of a tree, which can be explored by using an interval Branch & Prune (iBP) algorithm.When all available distances are exact, all candidate positions for a given molecular conformation can be enumerated.This is however not possible in presence of interval distances, because a continuous subset of positions can actually be computed for some atoms.The focus of this work is on a new scheme for an adaptive generation of a discrete subset of candidate positions from this continuous subset.Our generated candidate positions do not only satisfy the distances employed in the discretization process, but also additional distances that might be available (the so-called pruning distances).Therefore, this new scheme is able to guide more efficiently the search in the feasible regions of the search domain.In this work, we motivate the development and formally introduce this new adaptive scheme.Presented computational experiments show that iBP, integrated with our new scheme, outperforms the standard iBP on a set of NMR-like instances.

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.