skip to main content

Title: Mathematical aspects of molecular replacement. IV. Measure-theoretic decompositions of motion spaces
In molecular-replacement (MR) searches, spaces of motions are explored for determining the appropriate placement of rigid-body models of macromolecules in crystallographic asymmetric units. The properties of the space of non-redundant motions in an MR search, called a `motion space', are the subject of this series of papers. This paper, the fourth in the series, builds on the others by showing that when the space group of a macromolecular crystal can be decomposed into a product of two space subgroups that share only the lattice translation group, the decomposition of the group provides different decompositions of the corresponding motion spaces. Then an MR search can be implemented by trading off between regions of the translation and rotation subspaces. The results of this paper constrain the allowable shapes and sizes of these subspaces. Special choices result when the space group is decomposed into a product of a normal Bieberbach subgroup and a symmorphic subgroup (which is a common occurrence in the space groups encountered in protein crystallography). Examples of Sohncke space groups are used to illustrate the general theory in the three-dimensional case (which is the relevant case for MR), but the general theory in this paper applies to any dimension.
Authors:
; ; ;
Award ID(s):
1640970
Publication Date:
NSF-PAR ID:
10060063
Journal Name:
Acta Crystallographica Section A Foundations and Advances
Volume:
73
Issue:
5
Page Range or eLocation-ID:
387 to 402
ISSN:
2053-2733
Sponsoring Org:
National Science Foundation
More Like this
  1. This paper mathematically characterizes the tiny feasible regions within the vast 6D rotation–translation space in a full molecular replacement (MR) search. The capability to a priori isolate such regions is potentially important for enhancing robustness and efficiency in computational phasing in macromolecular crystallography (MX). The previous four papers in this series have concentrated on the properties of the full configuration space of rigid bodies that move relative to each other with crystallographic symmetry constraints. In particular, it was shown that the configuration space of interest in this problem is the right-coset space Γ\ G , where Γ is the space group of the chiral macromolecular crystal and G is the group of rigid-body motions, and that fundamental domains F Γ\ G can be realized in many ways that have interesting algebraic and geometric properties. The cost function in MR methods can be viewed as a function on these fundamental domains. This, the fifth and final paper in this series, articulates the constraints that bodies packed with crystallographic symmetry must obey. It is shown that these constraints define a thin feasible set inside a motion space and that they fall into two categories: (i) the bodies must not interpenetrate, thereby excludingmore »so-called `collision zones' from consideration in MR searches; (ii) the bodies must be in contact with a sufficient number of neighbors so as to form a rigid network leading to a physically realizable crystal. In this paper, these constraints are applied using ellipsoidal proxies for proteins to bound the feasible regions. It is shown that the volume of these feasible regions is small relative to the total volume of the motion space, which justifies the use of ellipsoids as proxies for complex proteins in MR searches, and this is demonstrated with P 1 (the simplest space group) and with P 2 1 2 1 2 1 (the most common space group in MX).« less
  2. We consider two manifestations of non-positive curvature: acylindrical actions (on hyperbolic spaces) and quasigeodesic stability. We study these properties for the class of hierarchically hyperbolic groups, which is a general framework for simultaneously studying many important families of groups, including mapping class groups, right-angled Coxeter groups, most 3 3 –manifold groups, right-angled Artin groups, and many others. A group that admits an acylindrical action on a hyperbolic space may admit many such actions on different hyperbolic spaces. It is natural to try to develop an understanding of all such actions and to search for a “best” one. The set of all cobounded acylindrical actions on hyperbolic spaces admits a natural poset structure, and in this paper we prove that all hierarchically hyperbolic groups admit a unique action which is the largest in this poset. The action we construct is also universal in the sense that every element which acts loxodromically in some acylindrical action on a hyperbolic space does so in this one. Special cases of this result are themselves new and interesting. For instance, this is the first proof that right-angled Coxeter groups admit universal acylindrical actions. The notion of quasigeodesic stability of subgroups provides a natural analogue ofmore »quasiconvexity which can be considered outside the context of hyperbolic groups. In this paper, we provide a complete classification of stable subgroups of hierarchically hyperbolic groups, generalizing and extending results that are known in the context of mapping class groups and right-angled Artin groups. Along the way, we provide a characterization of contracting quasigeodesics; interestingly, in this generality the proof is much simpler than in the special cases where it was already known. In the appendix, it is verified that any space satisfying the a priori weaker property of being an “almost hierarchically hyperbolic space” is actually a hierarchically hyperbolic space. The results of the appendix are used to streamline the proofs in the main text.« less
  3. We consider two manifestations of non-positive curvature: acylindrical actions (on hyperbolic spaces) and quasigeodesic stability. We study these properties for the class of hierarchically hyperbolic groups, which is a general framework for simultaneously studying many important families of groups, including mapping class groups, right-angled Coxeter groups, most 3–manifold groups, right-angled Artin groups, and many others. A group that admits an acylindrical action on a hyperbolic space may admit many such actions on different hyperbolic spaces. It is natural to try to develop an understanding of all such actions and to search for a “best” one. The set of all cobounded acylindrical actions on hyperbolic spaces admits a natural poset structure, and in this paper we prove that all hierarchically hyperbolic groups admit a unique action which is the largest in this poset. The action we construct is also universal in the sense that every element which acts loxodromically in some acylindrical action on a hyperbolic space does so in this one. Special cases of this result are themselves new and interesting. For instance, this is the first proof that right-angled Coxeter groups admit universal acylindrical actions. The notion of quasigeodesic stability of subgroups provides a natural analogue of quasi- convexitymore »which can be considered outside the context of hyperbolic groups. In this paper, we provide a complete classification of stable subgroups of hierarchically hyperbolic groups, generalizing and extending results that are known in the context of mapping class groups and right-angled Artin groups. Along the way, we provide a characterization of contracting quasigeodesics; interestingly, in this generality the proof is much simpler than in the special cases where it was already known.« less
  4. At the heart of both lossy compression and clustering is a trade-off between the fidelity and size of the learned representation. Our goal is to map out and study the Pareto frontier that quantifies this trade-off. We focus on the optimization of the Deterministic Information Bottleneck (DIB) objective over the space of hard clusterings. To this end, we introduce the primal DIB problem, which we show results in a much richer frontier than its previously studied Lagrangian relaxation when optimized over discrete search spaces. We present an algorithm for mapping out the Pareto frontier of the primal DIB trade-off that is also applicable to other two-objective clustering problems. We study general properties of the Pareto frontier, and we give both analytic and numerical evidence for logarithmic sparsity of the frontier in general. We provide evidence that our algorithm has polynomial scaling despite the super-exponential search space, and additionally, we propose a modification to the algorithm that can be used where sampling noise is expected to be significant. Finally, we use our algorithm to map the DIB frontier of three different tasks: compressing the English alphabet, extracting informative color classes from natural images, and compressing a group theory-inspired dataset, revealing interestingmore »features of frontier, and demonstrating how the structure of the frontier can be used for model selection with a focus on points previously hidden by the cloak of the convex hull.« less
  5. We investigate the approximability of the following optimization problem. The input is an n× n matrix A=(Aij) with real entries and an origin-symmetric convex body K⊂ ℝn that is given by a membership oracle. The task is to compute (or approximate) the maximum of the quadratic form ∑i=1n∑j=1n Aij xixj=⟨ x,Ax⟩ as x ranges over K. This is a rich and expressive family of optimization problems; for different choices of matrices A and convex bodies K it includes a diverse range of optimization problems like max-cut, Grothendieck/non-commutative Grothendieck inequalities, small set expansion and more. While the literature studied these special cases using case-specific reasoning, here we develop a general methodology for treatment of the approximability and inapproximability aspects of these questions. The underlying geometry of K plays a critical role; we show under commonly used complexity assumptions that polytime constant-approximability necessitates that K has type-2 constant that grows slowly with n. However, we show that even when the type-2 constant is bounded, this problem sometimes exhibits strong hardness of approximation. Thus, even within the realm of type-2 bodies, the approximability landscape is nuanced and subtle. However, the link that we establish between optimization and geometry of Banach spaces allows usmore »to devise a generic algorithmic approach to the above problem. We associate to each convex body a new (higher dimensional) auxiliary set that is not convex, but is approximately convex when K has a bounded type-2 constant. If our auxiliary set has an approximate separation oracle, then we design an approximation algorithm for the original quadratic optimization problem, using an approximate version of the ellipsoid method. Even though our hardness result implies that such an oracle does not exist in general, this new question can be solved in specific cases of interest by implementing a range of classical tools from functional analysis, most notably the deep factorization theory of linear operators. Beyond encompassing the scenarios in the literature for which constant-factor approximation algorithms were found, our generic framework implies that that for convex sets with bounded type-2 constant, constant factor approximability is preserved under the following basic operations: (a) Subspaces, (b) Quotients, (c) Minkowski Sums, (d) Complex Interpolation. This yields a rich family of new examples where constant factor approximations are possible, which were beyond the reach of previous methods. We also show (under commonly used complexity assumptions) that for symmetric norms and unitarily invariant matrix norms the type-2 constant nearly characterizes the approximability of quadratic maximization.« less