Section: Highlights of the Year

Highlights of the Year

In 2016, several achievements are worth noticing in three realms, namely in computer science, computational structural biology, and software.

Computer Science

$▸$ Optimal transportation problems with connectivity constraints

Reference: [21]

In a nutshell: Optimal transportation theory provides a rich framework to compare measures, both in the continuous and discrete settings. In this work, we study generalization of discrete transportation problems, when the supply and demand nodes are endowed with a graph structure; due to these constraints, our study focuses on transport plans respecting selected connectivity constrains. Our contributions encompass a formalization of these problems, as well as hardness results and heuristic algorithms.

Assessment: To the best of our knowledge, this work is the first one focusing on transport plans with connectivity constraints. One of the key applications targeted is the comparison of potential energy landscapes (PEL) in biophysics. Our algorithms provide a novel way to compare PEL, a topic overlooked so far.

$▸$ Clustering stability revealed by matchings between clusters of clusters

Reference: [22]

In a nutshell: Clustering is a fundamental problem in data science, yet, the variety of clustering methods and their sensitivity to parameters make clustering hard. This work provides a new tier of methods to compare two clusterings, by computing meta-clusters within each clustering– a meta-cluster is a group of clusters, together with a matching between these.

Assessment: Our methods will help assess the coherence between two clusterings, in two respects: by stressing the (lack of) stability of clustering while varying the parameters of a given algorithm, and by allowing a detailed comparisons of various algorithms.

Computational Structural Biology

$▸$ Novel structural parameters of Ig-Ag complexes yield a quantitative description of interaction specificity and binding affinity

Reference: [23]

In a nutshell: Understanding the specificity of antibodies for the targeted antigens, and predicting the affinity an antibody - antigen complexes is a central question in structural immunology. Using novel parameters acting as proxys for important biophysical quantities, we obtained affinity predictions of unprecedented accuracy, and were able to provide a quantitative explanation for the specific role of so-called complementarity determining regions – in particular CDR3 of heavy chains. See details in section 6.1.2.

Assessment: Our affinity predictions are the most accurate known to date, and show that for certain classes of IG - Ag complexes, the affinity prediction problem may be solved from databases of high resolution crystal structures.

$▸$ Energy landscapes and persistent minima

Reference: [15]

In a nutshell: Potential energy landscapes (PEL) of molecular systems are complex high-dimensional height functions. In this work, we introduced several tools from graph theory, optimization, and computational topology, so as to identify prominent features of PEL – prosaically distinguishing the signal from the noise. See details in section 6.3.1.

Assessment: Our work calls for important developments in two directions. The first one is concerned with the calibration / learning of features of PEL. The second one is the systematic comparison of force fields used in biophysics, as from current knowledge, deciding which force field is best for a given task or system is an open issue.

$▸$ Hybridizing rapidly growing random trees and basin hopping yields an improved exploration of energy landscapes

Reference: [18]

In a nutshell: We developed a novel exploration algorithm for high-dimensional non convex (potential) energy functions used in biophysics. Our algorithm exploits the ability of basin hopping to locate low-lying local minima, and that of rapidly exploring random tree to foster the exploration of yet unexplored regions. See details in section 6.3.2.

Assessment: Our exploration algorithm outperform the two classical algorithms it is derived from. To strike a major impact, though, our exploration strategy needs to be complemented by enhanced thermodynamic sampling algorithms, able to bridge the gap between structures on the one hand, and thermodynamics / dynamics on the other hand.

Software

$▸$ The Structural Bioinformatics Library

Reference: [20]

In a nutshell: The SBL was released in 2015. In 2016, two important milestones were achieved, with the addition of several important packages, notably geared towards the generation and the analysis of conformational ensembles, and the publication of [20]–to appear in Bioinformatics.

Assessment: As outlined by the reviewers of [20], the SBL is to the best of our knowledge the first library proposing a coherent framework, in terms of algorithms, data structures and biophysical models, to tackle the most important problems in structural bioinformatics. Our paper presenting the SBL being in press as of December 2016, statistics on users and downloads will be reported in the 2017 activity report.