Search

Reliably scoring and ranking candidate models of protein complexes and assigning their oligomeric state from the structure of the crystal lattice represent outstanding challenges. A community-wide effort was launched to tackle these challenges. The latest resources on protein complexes and interfaces were exploited to derive a benchmark dataset consisting of 1677 homodimer protein crystal structures, including a balanced mix of physiological and non-physiological complexes. The non-physiological complexes in the benchmark were selected to bury a similar or larger interface area than their physiological counterparts, making it more difficult for scoring functions to differentiate between them. Next, 252 functions for scoring protein-protein interfaces previously developed by 13 groups were collected and evaluated for their ability to discriminate between physiological and non-physiological complexes. A simple consensus score generated using the best performing score of each of the 13 groups, and a cross-validated Random Forest (RF) classifier were created. Both approaches showed excellent performance, with an area under the Receiver Operating Characteristic (ROC) curve of 0.93 and 0.94 respectively, outperforming individual scores developed by different groups. Additionally, AlphaFold2 engines were shown to recall the physiological dimers with significantly higher accuracy than the non-physiological set, lending support for the pertinence of our benchmark dataset. Optimizing the combined power of interface scoring functions and evaluating it on challenging benchmark datasets appears to be a promising strategy.

Flexible loops are paramount to protein functions, with action modes ranging from localized dynamics contributing to the free energy of the system, to large amplitude conformational changes accounting for the repositioning whole secondary structure elements or protein domains. However, generating diverse and low energy loops remains a difficult problem.This work introduces a novel paradigm to sample loop conformations, in the spirit of the Hit-and- Run (HAR) Markov chain Monte Carlo technique. The algorithm uses a decomposition of the loop into tripeptides, and a novel characterization of necessary conditions for Tripeptide Loop Closure to admit solutions. Denotingmthe number of tripeptides, the algorithm works in an angular space of dimension 12m. In this space, the hyper-surfaces associated with the aforementioned necessary conditions are used to run a HAR-like sampling technique.On classical loop cases up to 15 amino acids, our parameter free method compares favorably to previous work, generating more diverse conformational ensembles. We also report experiments on a 30 amino acids long loop, a size not processed in any previous work.

We introduce Multiple Interface String Alignment (MISA), a visualization tool to display coherently various sequence and structure based statistics at protein-protein interfaces (SSE elements, buried surface area, ΔASA, B factor values, etc). The amino-acids supporting these annotations are obtained from Voronoi interface models. The benefit of MISA is to collate annotated sequences of (homologous) chains found in different biological contexts i.e. bound with different partners or unbound. The aggregated views MISA/SSE, MISA/BSA, MISA/Δ ASAetc make it trivial to identify commonalities and differences between chains, to infer key interface residues, and to understand where conformational changes occur upon binding. As such, they should prove of key relevance for knowledge based annotations of protein databases such as the Protein Data Bank.Illustrations are provided on the receptor binding domain (RBD) of coronaviruses, in complex with their cognate partner or (neutralizing) antibodies. MISA computed with a minimal number of structures complement and enrich findings previously reported.The corresponding package is available from the Structural Bioinformatics Library (http://sbl.inria.fr)

Prioritizing genes for their role in drug sensitivity, is an important step in understanding drugs mechanisms of action and discovering new molecular targets for co-treatment. To formalize this problem, we consider two sets of genes X and P respectively composing the gene signature of cell sensitivity at the drug IC50 and the genes involved in its mechanism of action, as well as a protein interaction network (PPIN) containing the products of X and P as nodes. We introduce Genetrank, a method to prioritize the genes in X for their likelihood to regulate the genes in P. Genetrank uses asymmetric random walks with restarts, absorbing states, and a suitable renormalization scheme. Using novel so-called saturation indices, we show that the conjunction of absorbing states and renormalization yields an exploration of the PPIN which is much more progressive than that afforded by random walks with restarts only. Using MINT as underlying network, we apply Genetrank to a predictive gene signature of cancer cells sensitivity to tumor-necrosis-factor-related apoptosis-inducing ligand (TRAIL), performed in single-cells. Our ranking provides biological insights on drug sensitivity and a gene set considerably enriched in genes regulating TRAIL pharmacodynamics when compared to the most significant differentially expressed genes obtained from a statistical analysis framework alone. We also introduce gene expression radars, a visualization tool embedded in MA plots to assess all pairwise interactions at a glance on graphical representations of transcriptomics data. Genetrank is made available in the Structural Bioinformatics Library (https://sbl.inria.fr/doc/Genetrank-user-manual.html). It should prove useful for mining gene sets in conjunction with a signaling pathway, whenever other approaches yield relatively large sets of genes.

In December 2019, the Chinese Center for Disease Control reported several cases of severe pneumonia that resisted usual treatments inthe city of Wuhan. This announcement marked the beginning of the COVID19 pandemic, which caused more than 80 million infection casesand 1.7 million deaths worldwide in 2020 alone and is still raging. The pandemic has given rise to global public health responses and international research efforts of unprecedented scope and speed. This scientific mobilization has yielded remarkable results, enabling a great deal of knowledge accumulation in just a few months: from the identification of the virus and its main proteins to the analysis of its origin and mechanisms. This basic biological knowledge is mandatory for medical advances.In this document, one year after the beginning of the spread of the disease, we wish to shed particular light on the contribution of bioinformatics in all this work. This discipline, at the crossroads of computer sciences, mathematics, biology, and physics, has taken oninestimable importance in modern biology and medicine. It provides computational models, algorithms, software, and guidelines to help thescientific community handle biological data and accelerate research. The discovery and study of the SARS-CoV-2 coronavirus is an emblematicexample of these contributions. Bioinformatics methods have been at the heart of several essential milestones: sequencing the virus genome, analyzing its origin and evolutionary dynamics, modeling interacting biological entities at the structural and network scales, and studying host genetic susceptibility. For several of these topics, research on SARS-CoV-2 could benefit from a wide range of off-the-shelf software packages that rely on well-established algorithms developed by the bioinformatics community over the years. For other topics, the analysis of SARS-CoV-2 pushes the limits of knowledge and invites the community to develop new computational models and methods. This work, as a whole, has made it possible to elucidate the nature and the functioning of the novel pathogen. It has contributed to the fight against COVID19, even if much remains to be done to fully understand the disease and control the epidemic.

Resistance-nodulation-cell division family proteins are transmembrane proteins identified as large spectrum drug transporters involved in multidrug resistance. A prototypical case in this superfamily, responsible for antibiotic resistance in selected gram-negative bacteria, is AcrB. AcrB forms a trimer using the proton motive force to efflux drugs, implementing a functional rotation mechanism. Unfortunately, the size of the system (1049 amino acid per monomer and membrane) has prevented a systematic dynamical exploration, so that the mild understanding of this coupled transport jeopardizes our ability to counter it. The large number of crystal structures of AcrB prompts studies to further our understanding of the mechanism. To this end, we present a novel strategy based on two key ingredients, which are to study dynamics by exploiting information embodied in the numerous crystal structures obtained to date, and to systematically consider subdomains, their dynamics, and their interactions. Along the way, we identify the subdomains responsible for dynamic events, refine the states (A, B, E) of the functional rotation mechanism, and analyze the evolution of intramonomer and intermonomer interfaces along the functional cycle. Our analysis shows the relevance of AcrB's efflux mechanism as a template within the HAE1 family but not beyond. It also paves the way to targeted simulations exploiting the most relevant degrees of freedom at certain steps, and to a targeting of specific interfaces to block the drug efflux. Our work shows that complex dynamics can be unveiled from static snapshots, a strategy that may be used on a variety of molecular machines of large size.

International audience; The Wang-Landau (WL) algorithm is a recently developed stochastic algorithm computing densities of states of a physical system. Since its inception, it has been used on a variety of (bio-)physical systems, and in selected cases, its convergence has been proved. The convergence speed of the algorithm is tightly tied to the connectivity properties of the underlying random walk. As such, we propose an efficient random walk that uses geometrical information to circumvent the following inherent difficulties: avoiding overstepping strata, toning down concentration phenomena in high-dimensional spaces, and accommodating multidimensional distribution. Experiments on various models stress the importance of these improvements to make WL effective in challenging cases. Altogether, these improvements make it possible to compute density of states for regions of the phase space of small biomolecules.; L’algorithme de Wang-Landau est un algorithme stochastique récemment développé calculant la densité d’états pour des systèmes physiques. Depuis sa création, il a été utilisé sur des systèmes (bio-)physiques. Dans certain cas, sa convergence a été prouvée. La vitesse de convergence de l’algorithme est intimement liée aux propriétés de connectivité de la marche aléatoire sous-jacente. Nous proposons ici une marche aléatoire efficace utilisant des informations géométriques pour prévenir les difficultés suivantes: passer par dessus des strates, atténuer les phénomènes de concentration de la mesure en grande dimension, et gérer les distributions multimodales. Les expériences numériques sur différents modèles démontrent l’importance de ces améliorations pour rendre WL efficace dans des cas complexes. In fine, ces améliorations rendent possible le calcul de densité d’état pour des régions de l’espace des phases de petite bio-molécules.

International audience; Clustering is a fundamental problem in data science, yet, the variety of clusteringmethods and their sensitivity to parameters make clustering hard. To analyze the stability of agiven clustering algorithm while varying its parameters, and to compare clusters yielded by differentalgorithms, several comparison schemes based on matchings, information theory and various indices(Rand, Jaccard) have been developed. We go beyond these by providing a novel class of methodscomputing meta-clusters within each clustering– a meta-cluster is a group of clusters, togetherwith a matching between these.Let the intersection graph of two clusterings be the edge-weighted bipartite graph in which thenodes represent the clusters, the edges represent the non empty intersection between two clus-ters, and the weight of an edge is the number of common items. We introduce the so-calledD-family-matching problem on intersection graphs, withDthe upper-bound on the diameter ofthe graph induced by the clusters of any meta-cluster. First we prove NP-completeness resultsand unbounded approximation ratio of simple strategies. Second, we design exact polynomial timedynamic programming algorithms for some classes of graphs (in particular trees). Then, we provespanning-tree based efficient algorithms for general graphs.Our experiments illustrate the role ofDas a scale parameter providing information on the rela-tionship between clusters within a clustering and in-between two clusterings. They also show theadvantages of our built-in mapping over classical cluster comparison measures such as the variationof information (VI); Le clustering est une tâche essentielle en analyse de données, mais la variété desméthodes disponibles rend celle-ci ardue. Diverses stratégies ont été proposées pour analyserla stabilité d’un clustering en fonction des paramètres de l’algorithme l’ayant généré, ou biencomparer des clusterings produits par des algorithmes différents. Nous allons au delà de celles-ci,en proposant une nouvelle classe de méthodes formant des groupes de clusters (meta-clusters)dans chaque clustering, et établissant une correspondance entre ceux-ci.Plus spécifiquement, définissons le graphe intersection de deux clusterings comme le graphe bi-parti dont les sommets sont les clusters, chaque arête étant pondérée par le nombre de points com-muns à deux clusters. Nous définissons leD-family-matching problème à partir du graphe inter-section,Détant une borne supérieure sur le diamètre du graphe induit par les clusters des meta-clusters. Dans un premier temps, nous établissons des résultats de difficulté et d’inaproximabilité.Dans un second temps, nous développons des algorithmes de programmation dynamique pourcertaines classes de graphes (arbres en particulier). Enfin, nous concevons des algorithmes effi-caces, basés sur des arbres couvrants, pour des graphes généraux.Nos résultats expérimentaux illustrent le rôle deDcomme un paramètre d’échelle fournissantde l’information sur la relation entre les clusters intra ou inter clusterings. Ils montrent aussi lesavantages de notre appariement sur les outils de comparaison de clusterings classiques comme lavariation d’information (VI).

The root mean square deviation (RMSD) and the least RMSD are two widely used similarity measures in structural bioinformatics. Yet, they stem from global comparisons, possibly obliterating locally conserved motifs. We correct these limitations with the so-called combined RMSD, which mixes independent lRMSD measures, each computed with its own rigid motion. The combined RMSD is relevant in two main scenarios, namely to compare (quaternary) structures based on motifs defined from the sequence (domains and SSE) and to compare structures based on structural motifs yielded by local structural alignment methods. We illustrate the benefits of combined RMSD over the usual RMSD on three problems, namely (a) the assignment of quaternary structures for hemoglobin (scenario #1), (b) the calculation of structural phylogenies (case study: class II fusion proteins; scenario #1), and (c) the analysis of conformational changes based on combined RMSD of rigid structural motifs (case study: one class II fusion protein; scenario #2). Based on these illustrations, we argue that the combined RMSD is a tool of choice to perform positive and negative discrimination of degree of freedom, with applications to the design of move sets and collective coordinates. Executables to compute combined RMSD are available within the Structural Bioinformatics Library (http://sbl.inria.fr).

We present a sequence-structure based method characterizing a set of functionally related proteins exhibiting low sequence identity and loose structural conservation. Given a (small) set of structures, our method consists of three main steps. First, pairwise structural alignments are combined with multi-scale geometric analysis to produce structural motifs i.e. regions structurally more conserved than the whole structures. Second, the sub-sequences of the motifs are used to build profile hidden Markov models (HMM) biased towards the structurally conserved regions. Third, these HMM are used to retrieve from UniProtKB proteins harboring signatures compatible with the function studied, in a bootstrap fashion.We apply these hybrid HMM to investigate two questions related to class II fusion proteins, an especially challenging class since known structures exhibit low sequence identity (less than 15%) and loose structural similarity (of the order of 15Å in lRMSD). In a first step, we compare the performances of our hybrid HMM against those of sequence based HMM. Using various learning sets, we show that both classes of HMM retrieve unique species. The number of unique species reported by both classes of methods are comparable, stressing the novelty brought by our hybrid models. In a second step, we use our models to identify 17 plausible HAP2-GSC1 candidate sequences in 10 different drosophila melanogaster species. These models are not identified by the PFÅM family HAP2-GCS1 (PF10699), stressing the ability of our structural motifs to capture signals more subtle than whole Pfam domains.In a more general setting, our method should be of interest for all cases functional families with low sequence identity and loose structural conservation.Our software tools are available from the FunChaT package of the Structural Bioinformatics Library (http://sbl.inria.fr).

The root mean square deviation (RMSD) and the least RMSD are two widely used similarity measures in structural bioinformatics. Yet, they stem from global comparisons, possibly obliterating locally conserved motifs. We correct these limitations with the so-called combined RMSD, which mixes independent lRMSD measures, each computed with its own rigid motion. The combined RMSD can be used to compare (quaternary) structures based on motifs defined from the sequence (domains, SSE), or to compare structures based on structural motifs yielded by local structural alignment methods.We illustrate the benefits of combined RMSD over the usual RMSD on three problems, namely (i) the analysis of conformational changes based on combined RMSD of rigid structural motifs (case study: a class II fusion protein), (ii) the calculation of structural phylogenies (case study: class II fusion proteins), and (iii) the assignment of quaternary structures for hemoglobin. Using these, we argue that the combined RMSD is a tool a choice to perform positive and negative discrimination of degree of freedom, with applications to the design of move sets and collective coordinates.Combined RMSD are available within the Structural Bioinformatics Library (http://sbl.inria.fr).

Given samples from two distributions, a non-parametric two-sample test aims at determining whether the two distributions are equal or not, based on a test statistic. Classically, this statistic is computed on the whole data set, or is computed on a subset of the data set by a function trained on its complement. We consider methods in a third tier, so as to deal with large (possibly infinite) data sets, and to automatically determine the most relevant scales to work at, making two contributions. First, we develop a generic sequential non-parametric testing framework, in which the sample size need not be fixed in advance. This makes our test a truly sequential non-parametric multivariate two-sample test. Under information theoretic conditions qualifying the difference between the tested distributions, consistency of the two-sample test is established. Second, we instantiate our framework using nearest neighbor regressors, and show how the power of the resulting two-sample test can be improved using Bayesian mixtures and switch distributions. This combination of techniques yields automatic scale selection, and experiments performed on challenging data sets show that our sequential tests exhibit comparable performances to those of state-of-the-art non-sequential tests.

Predicting protein binding affinities from structural data has remained elusive, a difficulty owing to the variety of protein binding modes. Using the structure-affinity-benchmark (SAB, 144 cases with bound/unbound crystal structures and experimental affinity measurements), prediction has been undertaken either by fitting a model using a handfull of predefined variables, or by training a complex model from a large pool of parameters (typically hundreds). The former route unnecessarily restricts the model space, while the latter is prone to overfitting. We design models in a third tier, using 12 variables describing enthalpic and entropic variations upon binding, and a model selection procedure identifying the best sparse model built from a subset of these variables. Using these models, we report three main results. First, we present models yielding a marked improvement of affinity predictions. For the whole dataset, we present a model predicting Kd within 1 and 2 orders of magnitude for 48% and 79% of cases, respectively. These statistics jump to 62% and 89% respectively, for the subset of the SAB consisting of high resolution structures. Second, we show that these performances owe to a new parameter encoding interface morphology and packing properties of interface atoms. Third, we argue that interface flexibility and prediction hardness do not correlate, and that for flexible cases, a performance matching that of the whole SAB can be achieved. Overall, our work suggests that the affinity prediction problem could be partly solved using databases of high resolution complexes whose affinity is known.

International audience; Consider a set of oligomers listing the subunits involved in sub-complexes of a macro-molecular 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.

We present novel algorithms and software addressing four core problemsin computational structural biology, namely analyzing a conformationalensemble, comparing two conformational ensembles, analyzing a sampledenergy landscape, and comparing two sampled energy landscapes. Usingrecent developments in computational topology, graph theory, andcombinatorial optimization, we make two notable contributions. First,we a present a generic algorithm analyzing height fields. We then usethis algorithm to perform density based clustering of conformations,and to analyze a sampled energy landscape in terms of basins andtransitions between them. In both cases, topological persistence isused to manage ruggedness. Second, we introduce two algorithms tocompare transition graphs. The first is the classical earth mover distance metric which depends only on local minimum energyconfigurations along with their statistical weights, while the secondincorporates topological constraints inherent to conformationaltransitions.Illustrations are provided on a simplified protein model (BLN69), whosefrustrated potential energy landscape has been thoroughly studied.The software implementing our tools is also made available, and shouldprove valuable wherever conformational ensembles and energy landscapesare used.

This work develops a generic framework to perform a multiscale structural analysis of two structures (homologous proteins, conformations) undergoing conformational changes. Practically, given a seed structural alignment, we identify structural motifs with a hierarchical structure, characterized by three unique properties. First, the hierarchical structure sheds light on the trade-off between size and flexibility. Second, motifs can be combined to perform an overall comparison of the input structures in terms of combined RMSD - an improvement over the classical least RMSD. Third, motifs can be used to seed iterative aligners, and to design hybrid sequence-structure profile HMM characterizing protein families.From the methods standpoint, our framework is reminiscent from the bootstrap and combines concepts from rigidity analysis (distance difference matrices), graph theory, computational geometry (space filling diagrams), and topology (topological persistence).On challenging cases (class II fusion proteins, flexible molecules) we illustrate the ability of our tools to localize conformational changes, shedding light of commonalities of structures which would otherwise appear as radically different.Our tools are available within the Structural Bioinformatics Library (http://sbl.inria.fr). We anticipate that they will be of interest to perform structural comparisons at large, and for remote homology detection.

Rheumatoid arthritis (RA) is associated with abnormal B cell functions implicating antibody-dependent and -independent mechanisms. B cells have emerged as important cytokine-producing cells, and cytokines are well-known drivers of RA pathogenesis. To identify novel cytokine-mediated B cell functions in RA, we comprehensively analysed the capacity of B cells from RA patients with an inadequate response to disease modifying anti-rheumatic drugs to produce cytokines in comparison with healthy donors (HD). RA B cells displayed a constitutively higher production of the pathogenic factors interleukin (IL)-8 and Gro-α, while their production of several cytokines upon activation via the B cell receptor for antigen (BCR) was broadly suppressed, including a loss of the expression of the protective factor TRAIL, compared to HD B cells. These defects were partly erased after treatment with the IL-6-signalling inhibitor tocilizumab, indicating that abnormal IL-6 signalling contributed to these abnormalities. Noteworthy, the clinical response of individual patients to tocilizumab therapy could be predicted using the amounts of MIP-1β and β-NGF produced by these patients’ B cells before treatment. Taken together, our study highlights hitherto unknown abnormal B cell functions in RA patients, which are related to the unbalanced cytokine network, and are potentially relevant for RA pathogenesis and treatment. This article is protected by copyright. All rights reserved

Motivation Software in structural bioinformatics has mainly been application driven. To favor practitioners seeking off-the-shelf applications, but also developers seeking advanced building blocks to develop novel applications, we undertook the design of the Structural Bioinformatics Library (SBL, http://sbl.inria.fr), a generic C ++/python cross-platform software library targeting complex problems in structural bioinformatics. Its tenet is based on a modular design offering a rich and versatile framework allowing the development of novel applications requiring well specified complex operations, without compromising robustness and performances. Results The SBL involves four software components (1–4 thereafter). For end-users, the SBL provides ready to use, state-of-the-art (1) applications to handle molecular models defined by unions of balls, to deal with molecular flexibility, to model macro-molecular assemblies. These applications can also be combined to tackle integrated analysis problems. For developers, the SBL provides a broad C ++ toolbox with modular design, involving core (2) algorithms, (3) biophysical models and (4) modules, the latter being especially suited to develop novel applications. The SBL comes with a thorough documentation consisting of user and reference manuals, and a bugzilla platform to handle community feedback. Availability and Implementation The SBL is available from http://sbl.inria.fr Supplementary information Supplementary data are available at Bioinformatics online.

International audience; The 2015 D3R Grand Challenge provided an opportunity to test our new model for the binding free energy of small molecules, as well as to assess our protocol to predict binding poses for protein-ligand complexes. Our pose predictions were ranked 3-9 for the HSP90 dataset, depending on the assessment metric. For the MAP4K dataset the ranks are very dispersed and equal to 2-35, depending on the assessment metric, which does not provide any insight into the accuracy of the method. The main success of our pose prediction protocol was the re-scoring stage using the recently developed Convex-PL potential. We make a thorough analysis of our docking predictions made with AutoDock Vina and discuss the effect of the choice of rigid receptor templates, the number of flexible residues in the binding pocket, the binding pocket size, and the benefits of re-scoring. However, the main challenge was to predict experimentally determined binding affinities for two blind test sets. Our affinity prediction model consisted of two terms, a pairwise-additive enthalpy, and a non pairwise-additive entropy. We trained the free parameters of the model with a regularized regression using affinity and structural data from the PDBBind database. Our model performed very well on the training set, however, failed on the two test sets. We explain the drawback and pitfalls of our model, in particular in terms of relative coverage of the test set by the training set and missed dynamical properties from crystal structures, and discuss different routes to improve it.

International audience; We consider a coarse-graining of high-dimensional potential energy landscapes basedupon persistences, which correspond to lowest barrier heights to lower-energy min-ima. Persistences can be calculated efficiently for local minima in kinetic transitionnetworks that are based on stationary points of the prevailing energy landscape. Thenetworks studied here represent peptides, proteins, nucleic acids, an atomic cluster,and a glassy system. Minima with high persistence values are likely to representsome form of alternative structural morphology, which, if appreciably populated atthe prevailing temperature, could compete with the global minimum (defined as in-finitely persistent). Threshold values on persistences (and in some cases equilibriumoccupation probabilities) have therefore been used in this work to select subsets ofminima, which were then analysed to see how well they can represent features ofthe full network. Simplified disconnectivity graphs showing only the selected minimacan convey the funnelling (including any multiple-funnel) characteristics of the corre-sponding full graphs. The effect of the choice of persistence threshold on the reduceddisconnectivity graphs was considered for a system with a hierarchical, glassy land-scape. Sets of persistent minima were also found to be useful in comparing networksfor the same system sampled under different conditions, using minimum orientedspanning forests.

The number of local minima of the potential energy landscape (PEL) of molecular systems generally grows exponentially with the number of degrees of freedom, so that a crucial property of PEL exploration algorithms is their ability to identify local minima, which are low lying and diverse. In this work, we present a new exploration algorithm, retaining the ability of basin hopping (BH) to identify local minima, and that of transition based rapidly exploring random trees (T-RRT) to foster the exploration of yet unexplored regions. This ability is obtained by interleaving calls to the extension procedures of BH and T-RRT, and we show tuning the balance between these two types of calls allows the algorithm to focus on low lying regions. Computational efficiency is obtained using state-of-the art data structures, in particular for searching approximate nearest neighbors in metric spaces. We present results for the BLN69, a protein model whose conformational space has dimension 207 and whose PEL has been studied exhaustively. On this system, we show that the propensity of our algorithm to explore low lying regions of the landscape significantly outperforms those of BH and T-RRT.

This thesis introduces the first global parametric model of protein loops amenable to effective sampling strategies a-la Hit-and-Run, making four contributions. Starting with the classical kinematic view of loop closure developed by Coutsias et al, the first one resides in a geometric analysis of the Tripeptide Loop Closure (TLC) problem in terms of 12 angular coordinates describing the tripeptide geometry. Tight necessary conditions in this angular space are derived for TLC to admit solutions. Using an exhaustive database of tripeptides from the Protein Data Bank, the second contribution studies TLC reconstructions. Using Ramachandran statistics, we show that TLC solutions are geometrically more diverse than tripeptide structures, and also exhibit favorable potential energies. To sample protein loop conformations beyond tripeptides, the third contribution develops a loop sampling strategy based on solutions of individual tripeptide reconstructions, conditioned to motions of the peptide bodies connecting them. The aforementioned necessary conditions are used to sample conformations using a randomized algorithm reminiscent from Hit-and-Run. Finally, to go beyond the sole backbone geometry, the last contribution proposes the first robust calculation of the Fréchet mean/center of mass on the at torus, a key requirement to compute statistics on protein side chains.; Cette thèse introduit le premier modèle paramétrique global d'une boucle de protéine, qui soit passible de stratégies d'échantillonnage de type Hit-and-Run. Quatre contributions sont présentées. Partant du problème classique de fermeture cinématique d'une boucle tripeptidique par Coutsias et al (Tripeptide Loop Closure ou TLC), la première présente une analyse géométrique de TLC utilisant un espace angulaire de dimension 12. Des conditions nécessaires assez strictes sont développées, afin que TLC admette des solutions. En utilisant une base de données exhaustive de tripeptides extraite de la Protein Data Bank (PDB), la seconde contribution étudie les reconstructions produites par TLC. En utilisant des statistiques de Ramachandran, il est montré que ces solutions sont géométriquement diverses, et ont par ailleurs des énergies potentielles favorables. Afin d'échantillonner des conformations d'une boucle contenant plus de trois acides aminés, la troisième contribution développe une stratégie d'échantillonnage basée sur les solutions individuelles associées aux tripeptides formant la boucle, tripeptides dont la géométrie est conditionnée par les positions des corps rigides les connectant. Les conditions nécessaires évoquées ci-dessus sont utilisées pour échantillonner des conformations, en utilisant un algorithme randomisé de type Hit-and-Run. Enfin, pour aller au-delà de la seule géométrie du backbone, la dernière contribution présente le premier algorithme robuste du calcul de la moyenne de Fréchet/du centre de masse sur le cercle S¹, une statistique clef pour l'étude des conformations de chaînes latérales.

This document describes some of the research work I have been conducting since the defence of my Ph.D. thesis at Université de Bordeaux, France, back in June 2014. It is more particularly focused on my contribution to distinguishing labellings of graphs, and the so-called 1-2-3 Conjecture that occupies an important place in this field. The general objective in this kind of problems is, given a (connected undirected) graph, to weight its edges in such a way that the adjacent vertices get distinguishable accordingly to some parameter computed from the edge-weighting. For instance, in the 1-2-3 Conjecture, raised by Karoński, Łuczak and Thomason in 2004, the aim is to weight the edges with 1,2,3 so that adjacent vertices get distinguished accordingly to their sums of incident weights. Although the 1-2-3 Conjecture was raised as nothing but a toy problem when it was introduced, several results in the recent years have established its deeper nature. The conjecture, by its very definition, has undoubtedly an algebraic nature. Some results have also established that it has some decompositional flavour. Although the conjecture is rather artificial, it is also related to other classical notions of graph theory, such as proper vertex-colourings of graphs. In this document, we focus on contributions to distinguishing labellings that stand as support to these points. This is done through two main chapters: • In the first chapter, we present results related to several aspects of the 1-2-3 Conjecture. The presented results are both on main aspects of the conjecture, i.e., that stand as evidence towards the main open questions related to it, and on more side aspects, i.e., that are helpful towards understanding better its general behaviour and mechanisms. These side aspects cover natural questions regarding the true importance of all weights 1,2,3 for the 1-2-3 Conjecture, the impact of requiring adjacent vertices to be "even more distinguishable", and generalisations of the conjecture to digraphs. • In the second chapter, we present results on so-called locally irregular decompositions of graphs, which are a kind of decompositions attesting the very decompositional nature of the 1-2-3 Conjecture. The presented results include better decomposition results for graphs in general, as well as a general theory that is the key for relating locally irregular decompositions and the 1-2-3 Conjecture. Each chapter comes up with a concluding section describing consequences of the presented results on the field, as well as perspectives for research we have for the near future.

Resistance to chemotherapy can be studied comparatively to the study of resistance in microorganisms. Among the protein superfamily identified as being responsible for multidrug resistance are RND. Its members are widespread in bacterial organisms, but also in Archaea and Eukaryotes. Ptch1, a transmembrane protein, receptor of morphogen Hedgehog (Hh), a member of the RND, has cholesterol efflux activity, but also of chemotherapeutic drugs which confers resistanceto chemotherapy to cancer cells. In fact, an aberrant activity of the Hh signaling pathway has been observed in nearly 25% of cancers. Among the common features of multidrug resistance in RND is the ability of these transmembrane proteins to efflux a broad spectrum of substrates and drugs using protonmotive force.The goal of this project is the structural study of the drug efflux mechanism of Ptch1.In a first step, since we did not yet have access to a structure of Ptch1, we have performed an analysis of the numerous available structures of its bacterial counterpart AcrB, the RND paradigm model responsible for antibiotic resistance in gram-negative bacteria, in order to better understand the drug efflux mechanism of these proteins. We have implemented a strategy of conformational analysis of all available structures in order to explain the complex mechanism, including the drug efflux mechanism of these proteins, as a function of the structural and dynamic properties of sub-domains. The tools developed have been made available to the community.The structures of Ptch1 published in 2018 and 2019 revealed that the drug efflux mechanism of Ptch1 was probably very different from that of AcrB. In a second step, using these structures, we studied the cholesterol efflux mechanism of Ptch1 by molecular dynamics in order to subsequently study the drug efflux mechanism. We thus identified certain characteristics of the conformational changes that cantake place to allow this efflux. Finally, the docking of chemotherapeutic agents carried by Ptch1 suggests that drugs use the same interaction sites as cholesterol and potentially the same efflux mechanism.; La résistance à la chimiothérapie peut-être étudiée comparativement à l’étude de la résistance chez les microorganismes. Parmi les superfamilles de protéine identifiées comme étant responsables de résistance aux drogues, il y a les RND. Ses membres sont très répandus dans les organismes bactériens, mais aussi les archaea et les eucaryotes. Ptch1, protéine transmembranaire récepteur du morphogène Hedgehog (Hh), membre des RND, a une activité d’efflux de cholestérol, mais aussi de médicaments chimiothérapeutiques qui confère aux cellules cancéreuses une résistance à la chimiothérapie. Or, une activité aberrante de la voie de signalisation Hh a été observée dans près de 25 % des cancers. Parmi les caractéristiques communes à la résistance aux drogues des RND, il y a la capacité de ces protéines transmembranaires à faire de l’efflux d’un large spectre de substrats et de drogues, et ce, en utilisant la force proton motrice.L’objectif de ce projet est l’étude structurale du mécanisme d’efflux de drogues de Ptch1.Dans un premier temps, n’ayant pas encore accès à une structure de Ptch1, nous avons réalisé une analyse des nombreuses structures disponibles de son homologue bactérien AcrB, modèle paradigme des RND responsable de résistance aux antibiotiques chez les bactéries gram négatives, afin de mieux comprendre le mécanisme d’efflux de drogues de ces protéines. Nous avons mis en place une stratégie d’analyse conformationnelle de l’ensemble des structures disponibles de façon à expliquer le mécanisme complexe, notamment ceux d’efflux de drogues de ces protéines, en fonction des propriétés structurales et dynamiques de sous-domaines. Les outils développés ont été mis à disposition de la communauté.Les structures de Ptch1 publiées en 2018 et 2019 ont révélé que le mécanisme d’efflux de drogues de Ptch1 était probablement très différent de celui d’AcrB. Dans un second temps, en utilisant ces structures, nous avons étudié le mécanisme d’efflux de cholestérol de Ptch1 par dynamique moléculaire afin d’étudier par la suite celui des drogues. Nous avons ainsi identifié certaines caractéristiques des changements conformationnels pouvant avoir lieu afin de permettre cet efflux. Enfin, le docking des agents chimiothérapeutiques transportés par Ptch1 suggère que les drogues utilisent les mêmes sites d’interaction que le cholestérol et potentiellement le même mécanisme d’efflux.

This manuscript introduces new random walks for the computation of densities of states, a central problem in statistical physics, and the computation of the volume of polytopes. First, we focus on the Wang-Landau (WL) algorithm, a recently developed stochastic algorithm computing the density of states of a physical system. We propose an efficient random walk that uses geometrical information to circumvent the following inherent difficulties: avoiding overstepping strata, toning down concentration phenomena in high-dimensional spaces, and accommodating multidimensional distribution. Experiments on various models stress the importance of these improvements to make Wang-Landau effective in challenging cases. These improvements make it possible to compute density of states for regions of the phase space of small biomolecules. Second, we study Hamiltonian Monte Carlo (HMC) with reflections on the boundary of a domain, providing an enhanced alternative to Hit-and-run (HAR) to sample a target distribution in a bounded domain. We provide a convergence bound, paving the way to more precise mixing time analysis, and a robust implementation based on multi-precision arithmetic -- a mandatory ingredient. We compare Hamiltonian Monte Carlo with Hit and Run within the polytope volume algorithm by Cousins and Vempala. The tests, conducted up to dimension 50, show that the HMC with reflections random walk outperforms HAR. Finally, using Wang-Landau requires specifying the system handled, providing a suitable random walk to explore the definition domain, and possibly accommodate different variants of Wang-Landau. We present the first generic (C++) implementation providing all such ingredients., Ce manuscrit présente de nouvelles marches aléatoires pour le calcul des densités d'états, un problème central en physique statistique, et le calcul de volume de polytopes. Tout d'abord, nous étudions Wang-Landau (WL), un algorithme stochastique récemment développé pour calculer la densité d'états d'un système physique. Nous proposons une marche aléatoire efficace qui utilise l'information géométrique pour contourner les difficultés suivantes : éviter de sauter des strates, atténuer les phénomènes de concentration en grandes dimensions, et gérer les distributions multimodales. Les expériences montrent que ces améliorations sont critiques dans les cas difficiles, et permettent de calculer la densité des états pour des régions de l'espace des phases de petites biomolécules. Puis nous étudions Hamiltonian Monte Carlo (HMC) avec réflexions sur les limites d'un domaine, offrant une alternative à Hit-and-run (HAR) pour échantillonner une distribution dans un domaine borné. Nous fournissons une borne de convergence, ouvrant la voie à une analyse plus précise du mixing time, et une implémentation robuste basée sur l'arithmétique multiprécision implémentée grâce à iRRAM -- un ingrédient obligatoire. Nous comparons Hamiltonian Monte Carlo à Hit-and-run au sein de l'algorithme de volume polytope de Cousins et Vempala. Les essais, effectués jusqu'à la dimension 50, montrent que Hamiltonian Monte Carlo avec réflexions surpasse Hit and Run. Enfin, l'utilisation de Wang-Landau nécessitant de spécifier le système étudié, de fournir une marche aléatoire, et éventuellement d'incorporer des variantes de Wang-Landau, nous présentons la première implémentation générique (C++) fournissant tous ces ingrédients.

In this thesis, the focus is set on reconciling the realms of structure and sequence for protein analysis. Sequence analysis tools shine when faced with proteins presenting high sequence identity (≤ 30\%), but are lack - luster when it comes to remote homolog detection. Structural analysis tools present an interesting alternative, but solving structures - when at all possible- is a tedious and expensive process. These observations make the need for hybrid methods - which inject information obtained from available structures in a sequence model - quite clear. This thesis makes four main contributions toward this goal. First we present a novel structural measure, the RMSDcomb, based on local structural conservation patterns - the so called structural motifs. Second, we developed a method to identify structural motifs between two structures using a bootstrap method which relies on filtrations. Our approach is not a direct competitor to flexible aligners but can provide useful to perform a multiscale analysis of structural similarities. Third, we build upon the previous methods to design hybrid Hidden Markov Models which are biased towards regions of increased structural conservation between sets of proteins. We test this tool on the class II fusion viral proteins - particularly challenging because of their low sequence identity and mild structural homology. We find that we are able to recover known remote homologs of the viral proteins in the Drosophila and other organisms. Finally, formalizing a sub - problem encountered when comparing filtrations, we present a new theoretical problem - the D-family matching - on which we present various algorithmic results. We show - in a manner that is analogous to comparing parts of two protein conformations - how it is possible to compare two clusterings of the same data set using such a theoretical model., Dans cette thèse, l'emphase est mise sur la réconciliation de l'analyse de structure et de séquence pour les protéines. L'analyse de séquence brille lorsqu'il s'agit de comparer des protéines présentant une forte identité de séquence (≤ 30\%) mais laisse à désirer pour identifier des homologues lointains. L'analyse de structure est une alternative intéressante. Cependant, les méthodes de résolution de structures sont coûteuses et complexes - lorsque toutefois elles produisent des résultats. Ces observations rendent évident la nécessité de développer des méthodes hybrides, exploitant l'information extraite des structures disponibles pour l'injecter dans des modèles de séquence. Cette thèse produit quatre contributions principales dans ce domaine. Premièrement, nous présentons une nouvelle distance structurale, le RMSDcomb, basée sur des patterns de conservation structurale locale, les motifs structuraux. Deuxièmement, nous avons développé une méthode pour identifier des motifs structuraux entre deux structures exploitant un bootstrap dépendant de filtrations. Notre approche n'est pas un compétiteur direct des aligneurs flexibles mais permet plutôt de produire des analyses multi-échelles de similarités structurales. Troisièmement, nous exploitons les méthodes suscitées pour construire des modèles de Markov cachés hybrides biaisés vers des régions mieux conservées structurellement. Nous utilisons un tel modèle pour caractériser les protéines de fusion virales de classe II, une tâche particulièrement ardue du fait de leur faible identité de séquence et leur conservation structurale moyenne. Ce faisant, nous parvenons à trouver un certain nombre d'homologues distants connues des protéines virales, notamment chez la Drosophile. Enfin, en formalisant un sous-problème rencontré lors de la comparaison de filtrations, nous présentons un nouveau problème théorique - le D-family matching - sur lequel nous démontrons des résultats algorithmiques variés. Nous montrons - d'une façon analogue à la comparaison de régions de deux conformations d'une protéine - comment exploiter ce modèle théorique pour comparer deux clusterings d'un même jeu de données.

This thesis investigates three topics at the cross-roads of structural biology,genetics and immunology.First, we develop a pipeline to design and select binding affinity predictors forprotein complexes, yielding state-of-the art results. The first step is the designand computation of 12 different variables accounting for geometric andphysico-chemical properties of the complexes. The second step is thegeneration and evaluation of models using subsets of these variables, followedby the selection of the best performing ones. The corresponding software isdistributed within the Structural Bioinformatics Library.Second, we provide an analysis of the interface properties of Ig-Ag complexes.In particular, we design a classifier using two descriptors, which is able todistinguish ligand types. We also apply the previous binding affinity predictionmodel to Ig-Ag complexes and obtain accurate predictions. We then develop aquantitative model for the contribution of VH CDR3 to the binding affinity andinteraction specificity, and show that it contributes significantly more thanother CDRs.Third, we model the diversity of VH CDR3 repertoires from Ig RNA sequencingdata in a fish vaccination model. We analyze repertoires from three conditions:naive, vaccinated and vaccinated + infected fish. Comparison of the repertoiresof two individuals uses the earth-mover distance (EMD). By exploiting amapping between the clonotypes of the repertoires, we show that EMD revealsinformation beyond classical methods based on diversity indexes. Tocharacterize the notion of public / private immune response, we quantify theoverlap of clonotypes between individuals of the same or different conditions, Cette thèse étudie trois sujets relevant de la biologie structurale, de lagénétique et de l'immunologie.Premièrement, nous développons de nouveaux prédicteurs de l'affinité deliaison de complexes protéiques, produisant des résultats de niveau ``état del'art''. Nous calculons d'abord 12 variables modélisant diverses propriétésstructurales des complexes. Nous générons et évaluons des estimateursutilisant des sous ensembles de ces variables, de façon à identifier les plusperformants. Le logiciel associé est distribué dans la Structural BioinformaticsLibrary.Deuxièmement, nous proposons de nouvelles analyses de complexes Ig-Ag.D'une part nous concevons un classificateur distinguant les types de ligand desIg. D'autre part, nous montrons que le modèle précédent prédit fidèlementl'affinité de complexes Ig-Ag. Enfin, nous quantifions la contribution des CDR3de la chaine lourde à l'affinité de liaison, et montrons qu'il contribuesignificativement plus que les autres CDR.Enfin, nous nous intéressons à la modélisation de la diversité des répertoiresde chaîne lourde des Igs, à partir de données de séquençage de CDR3, dans unmodèle de vaccin chez le poisson. Nous analysons les répertoires dans troisconditions: naifs, vaccinés et vaccinés + infectés. Nous comparons lesrépertoires de deux individus en utilisant la « earth-mover distance », laquelleexploite la correspondance entre clonotypes de deux répertoires, révélant ainsides informations inaccessibles aux méthodes basées sur les indices dediversité.Dépôt de thèseDonnées complémentairesPour caractériser la notion de réponse immunitaire publique / privée, nousquantifions le chevauchement des clonotypes exprimés entre individus de lamême ou de différentes conditions

In this thesis, we study problems related to learning and detecting multivariate statistical dissimilarity, which are of paramount importance for many statistical learning methods nowadays used in an increasingly number of fields. This thesis makes three contributions related to these problems. The first contribution introduces a notion of multivariate nonparametric effect size shedding light on the nature of the dissimilarity detected between two datasets. Our two step method first decomposes a dissimilarity measure (Jensen-Shannon divergence) aiming at localizing the dissimilarity in the data embedding space, and then proceeds by aggregating points of high discrepancy and in spatial proximity into clusters. The second contribution presents the first sequential nonparametric two-sample test. That is, instead of being given two sets of observations of fixed size, observations can be treated one at a time and, when strongly enough evidence has been found, the test can be stopped, yielding a more flexible procedure while keeping guaranteed type I error control. Additionally, under certain conditions, when the number of observations tends to infinity, the test has a vanishing probability of type II error. The third contribution consists in a sequential change detection test based on two sliding windows on which a two-sample test is performed, with type I error guarantees. Our test has controlled memory footprint and, as opposed to state-of-the-art methods that also provide type I error control, has constant time complexity per observation, which makes our test suitable for streaming data.; Cette thèse présente trois contributions en lien avec l'apprentissage et la détection de dissimilarité statistique multivariée, problématique d'importance primordiale pour de nombreuses méthodes d'apprentissage utilisées dans un nombre croissant de domaines. La première contribution introduit la notion de taille d'effet multivariée non-paramétrique, éclairant la nature de la dissimilarité détectée entre deux jeux de données, en deux étapes. La première consiste en une décomposition d'une mesure de dissimilarité (divergence de Jensen-Shannon) visant à la localiser dans l'espace ambiant, tandis que la seconde génère un résultat facilement interprétable en termes de grappes de points de forte discrépance et en proximité spatiale. La seconde contribution présente le premier test non-paramétrique d'homogénéité séquentiel, traitant les données issues de deux jeux une à une--au lieu de considérer ceux-ci- in extenso. Le test peut ainsi être arrêté dès qu'une évidence suffisamment forte est observée, offrant une flexibilité accrue tout en garantissant un contrôle del'erreur de type I. Sous certaines conditions, nous établissons aussi que le test a asymptotiquement une probabilité d'erreur de type II tendant vers zéro. La troisième contribution consiste en un test de détection de changement séquentiel basé sur deux fenêtres glissantes sur lesquelles un test d'homogénéité est effectué, avec des garanties sur l'erreur de type I. Notre test a une empreinte mémoire contrôlée et, contrairement à des méthodes de l'état de l'art qui ont aussi un contrôle sur l'erreur de type I, a une complexité en temps constante par observation, le rendant adapté aux flux de données.