In this work, we investigate the parallel-beam projection and reconstruction of band-limited Hermite expansions. Using a recently developed coordinate conversion technique, we show how the Fourier slice theorem can be directly applied. In our new approach, we do not introduce a non-integrable filter that appears in the filtered backprojection method. Since a projection of a 2D band-limited Hermite expansion is a 1D band-limited Hermite expansion and the coordinate conversion technique is lossless with this special expansion, we can avoid a series of approximations that the classical tomography techniques make.
Parallel-beam tomography; Hermite expansion; polar-Cartesian interpolation
Search spaces in the method of molecular replacement are shown to be coset spaces of the Lie group of rigid-body motions by the chiral space group of a crystal. The resulting ‘motion space’ can be endowed with a quasigroup operation that has interesting properties which are explored here.
Molecular replacement (MR) is a well established method for phasing of X-ray diffraction patterns for crystals composed of biological macromolecules of known chemical structure but unknown conformation. In MR, the starting point is known structural domains that are presumed to be similar in shape to those in the macromolecular structure which is to be determined. A search is then performed over positions and orientations of the known domains within a model of the crystallographic asymmetric unit so as to best match a computed diffraction pattern with experimental data. Unlike continuous rigid-body motions in Euclidean space and the discrete crystallographic space groups, the set of motions over which molecular replacement searches are performed does not form a group under the operation of composition, which is shown here to lack the associative property. However, the set of rigid-body motions in the asymmetric unit forms another mathematical structure called a quasigroup, which can be identified with right-coset spaces of the full group of rigid-body motions with respect to the chiral space group of the macromolecular crystal. The algebraic properties of this space of motions are articulated here.
rigid-body motion; coset space; quasigroup; fundamental domain; molecular replacement
Single-particle electron microscopy is an experimental technique that is used to determine the 3D structure of biological macromolecules and the complexes that they form. In general, image processing techniques and reconstruction algorithms are applied to micrographs, which are two-dimensional (2D) images taken by electron microscopes. Each of these planar images can be thought of as a projection of the macromolecular structure of interest from an a priori unknown direction. A class is defined as a collection of projection images with a high degree of similarity, presumably resulting from taking projections along similar directions. In practice, micrographs are very noisy and those in each class are aligned and averaged in order to reduce the background noise. Errors in the alignment process are inevitable due to noise in the electron micrographs. This error results in blurry averaged images. In this paper, we investigate how blurring parameters are related to the properties of the background noise in the case when the alignment is achieved by matching the mass centers and the principal axes of the experimental images. We observe that the background noise in micrographs can be treated as Gaussian. Using the mean and variance of the background Gaussian noise, we derive equations for the mean and variance of translational and rotational misalignments in the class averaging process. This defines a Gaussian probability density on the Euclidean motion group of the plane. Our formulation is validated by convolving the derived blurring function representing the stochasticity of the image alignments with the underlying noiseless projection and comparing with the original blurry image.
Single-particle electron microscopy; class average; image alignment; convolution
Flexible needles with bevel tips are being developed as useful tools for minimally invasive surgery and percutaneous therapy. When such a needle is inserted into soft tissue, it bends due to the asymmetric geometry of the bevel tip. This insertion with bending is not completely repeatable. We characterize the deviations in needle tip pose (position and orientation) by performing repeated needle insertions into artificial tissue. The base of the needle is pushed at a constant speed without rotating, and the covariance of the distribution of the needle tip pose is computed from experimental data. We develop the closed-form equations to describe how the covariance varies with different model parameters. We estimate the model parameters by matching the closed-form covariance and the experimentally obtained covariance. In this work, we use a needle model modified from a previously developed model with two noise parameters. The modified needle model uses three noise parameters to better capture the stochastic behavior of the needle insertion. The modified needle model provides an improvement of the covariance error from 26.1% to 6.55%.
In this paper we develop a new framework for path planning of flexible needles with bevel tips. Based on a stochastic model of needle steering, the probability density function for the needle tip pose is approximated as a Gaussian. The means and covariances are estimated using an error propagation algorithm which has second order accuracy. Then we adapt the path-of-probability (POP) algorithm to path planning of flexible needles with bevel tips. We demonstrate how our planning algorithm can be used for feedback control of flexible needles. We also derive a closed-form solution for the port placement problem for finding good insertion locations for flexible needles in the case when there are no obstacles. Furthermore, we propose a new method using reference splines with the POP algorithm to solve the path planning problem for flexible needles in more general cases that include obstacles.
flexible needles; path planning; stochastic model; path-of-probability algorithm; error propagation; port placement; feedback control
Proteins fold from a highly disordered state into a highly ordered one. Traditionally, the folding problem has been stated as one of predicting ‘the’ tertiary structure from sequential information. However, new evidence suggests that the ensemble of unfolded forms may not be as disordered as once believed, and that the native form of many proteins may not be described by a single conformation, but rather an ensemble of its own. Quantifying the relative disorder in the folded and unfolded ensembles as an entropy difference may therefore shed light on the folding process. One issue that clouds discussions of ‘entropy’ is that many different kinds of entropy can be defined: entropy associated with overall translational and rotational Brownian motion, configurational entropy, vibrational entropy, conformational entropy computed in internal or Cartesian coordinates (which can even be different from each other), conformational entropy computed on a lattice; each of the above with different solvation and solvent models; thermodynamic entropy measured experimentally, etc. The focus of this work is the conformational entropy of coil/loop regions in proteins. New mathematical modeling tools for the approximation of changes in conformational entropy during transition from unfolded to folded ensembles are introduced. In particular, models for computing lower and upper bounds on entropy for polymer models of polypeptide coils both with and without end constraints are presented. The methods reviewed here include kinematics (the mathematics of rigid-body motions), classical statistical mechanics and information theory.
Protein folding; Entropy; Conformation; Ensemble; Convolution; Rigid-body Motion; Probability Density Function; Polymer; Information Theory
Fluctuations in the bending angles at internal irregularities of DNA and RNA (such as symmetric loops, bulges, and nicks/gaps) have been observed from various experiments. However, little effort has been made to computationally predict and explain the statistical behavior of semi-flexible chains with internal defects. In this paper, we describe the general structure of these macromolecular chains as inextensible elastic chains with one or more internal joints which have limited ranges of rotation, and propose a method to compute the probability density functions of the end-to-end pose of these macromolecular chains. Our method takes advantage of the operational properties of the non-commutative Fourier transform for the group of rigid-body motions in three-dimensional space, SE(3). Two representative types of joints, the hinge for planar rotation and the ball joint for spatial rotation, are discussed in detail. The proposed method applies to various stiffness models of semi-flexible chain-like macromolecules. Examples are calculated using the Kratky-Porod model with specified stiffness, angular fluctuation, and joint locations. Entropic effects associated with internal angular fluctuations of semi-flexible macromolecular chains with internal joints can be computed using this formulation. Our method also provides a potential tool to detect the existence of internal irregularities.
Classical inequalities used in information theory such as those of de Bruijn, Fisher, Cramér, Rao, and Kullback carry over in a natural way from Euclidean space to unimodular Lie groups. These are groups that possess an integration measure that is simultaneously invariant under left and right shifts. All commutative groups are unimodular. And even in noncommutative cases unimodular Lie groups share many of the useful features of Euclidean space. The rotation and Euclidean motion groups, which are perhaps the most relevant Lie groups to problems in geometric mechanics, are unimodular, as are the unitary groups that play important roles in quantum computing. The extension of core information theoretic inequalities defined in the setting of Euclidean space to this broad class of Lie groups is potentially relevant to a number of problems relating to information gathering in mobile robotics, satellite attitude control, tomographic image reconstruction, biomolecular structure determination, and quantum information theory. In this paper, several definitions are extended from the Euclidean setting to that of Lie groups (including entropy and the Fisher information matrix), and inequalities analogous to those in classical information theory are derived and stated in the form of fifteen small theorems. In all such inequalities, addition of random variables is replaced with the group product, and the appropriate generalization of convolution of probability densities is employed. An example from the field of robotics demonstrates how several of these results can be applied to quantify the amount of information gained by pooling different sensory inputs.
Information Theory; Lie Group; Convolution; Inequalities
This paper presents an efficient group-theoretic approach for computing the statistics of non-reversal random walks (NRRW) on lattices. These framed walks evolve on proper crystallographic space groups. In a previous paper we introduced a convolution method for computing the statistics of NRRWs in which the convolution product is defined relative to the space-group operation. Here we use the corresponding concept of the fast Fourier transform for functions on crystallographic space groups together with a non-Abelian version of the convolution theorem. We develop the theory behind this technique and present numerical results for two-dimensional and three-dimensional lattices (square, cubic and diamond). In order to verify our results, the statistics of the end-to-end distance and the probability of ring closure are calculated and compared with results obtained in the literature for the random walks for which closed-form expressions exist.
Non-reversible random walk; crystallographic space groups; group Fourier transform; convolution theorem
Biological macromolecules, and the complexes that they form, can be described in a variety of ways ranging from quantum mechanical and atomic chemical models, to coarser grained models of secondary structure and domains, to continuum models. At each of these levels, group theory can be used to describe both geometric symmetries and conformational motion. In this survey, a detailed account is provided of how group theory has been applied across computational structural biology to analyze the conformational shape and motion of macromolecules and complexes.
Computational models provide insight into the structure-function relationship in proteins. These approaches, especially those based on normal mode analysis, can identify the accessible motion space around a given equilibrium structure. The large magnitude, collective motions identified by these methods are often well aligned with the general direction of the expected conformational transitions. However, these motions cannot realistically be extrapolated beyond the local neighborhood of the starting conformation. In this paper, the icNMA method is presented for traversing the energy landscape from a starting conformation to a desired goal conformation. This is accomplished by allowing the evolving geometry of the intermediate structures to define the local accessible motion space, and thus produce an appropriate displacement. Following the derivation of the icNMA method, a set of sample simulations are performed to probe the robustness of the model. A detailed analysis of β1,4-galactosyltransferase-T1 is also given, to highlight many of the capabilities of icNMA. Remarkably, during the transition, a helix is seen to be extended by an additional turn, emphasizing a new unknown role for secondary structures to absorb slack during transitions. The transition pathway for adenylate kinase, which has been frequently studied in the literature, is also discussed.
protein mechanics; elastic network; normal mode analysis (NMA); cluster-NMA (cNMA); rigid-body motions; β1,4-galactosyltransferase-T1; adenylate kinase
A nonholonomic system subjected to external noise from the environment, or internal noise in its own actuators, will evolve in a stochastic manner described by an ensemble of trajectories. This ensemble of trajectories is equivalent to the solution of a Fokker–Planck equation that typically evolves on a Lie group. If the most likely state of such a system is to be estimated, and plans for subsequent motions from the current state are to be made so as to move the system to a desired state with high probability, then modeling how the probability density of the system evolves is critical. Methods for solving Fokker-Planck equations that evolve on Lie groups then become important. Such equations can be solved using the operational properties of group Fourier transforms in which irreducible unitary representation (IUR) matrices play a critical role. Therefore, we develop a simple approach for the numerical approximation of all the IUR matrices for two of the groups of most interest in robotics: the rotation group in three-dimensional space, SO(3), and the Euclidean motion group of the plane, SE(2). This approach uses the exponential mapping from the Lie algebras of these groups, and takes advantage of the sparse nature of the Lie algebra representation matrices. Other techniques for density estimation on groups are also explored. The computed densities are applied in the context of probabilistic path planning for kinematic cart in the plane and flexible needle steering in three-dimensional space. In these examples the injection of artificial noise into the computational models (rather than noise in the actual physical systems) serves as a tool to search the configuration spaces and plan paths. Finally, we illustrate how density estimation problems arise in the characterization of physical noise in orientational sensors such as gyroscopes.
State estimation; Lie groups; nonholonomic motion planning; exponential map
In this paper we propose an algorithm for lossless conversion of data between Cartesian and polar coordinates, when the data is sampled from a two dimensional real-valued function (a mapping : ℝ2 ↦ ℝ) expressed as a particular kind of truncated expansion. We use Laguerre functions and the Fourier basis for the polar coordinate expression. Hermite functions are used for the Cartesian coordinate expression. A finite number of coefficients for the truncated expansion specifies the function in each coordinate system. We derive the relationship between the coefficients for the two coordinate systems. Based on this relationship, we propose an algorithm for lossless conversion between the two coordinate systems. Resampling can be used to evaluate a truncated expansion on the complementary coordinate system without computing a new set of coefficients. The resampled data is used to compute the new set of coefficients to avoid the numerical instability associated with direct conversion of the coefficients. In order to apply our algorithm to discrete image data, we propose a method to optimally fit a truncated expression to a given image. We also quantify the error that this filtering process can produce. Finally the algorithm is applied to solve the polar-Cartesian interpolation problem.
Coordinate conversion; Image processing; truncated expansions; Interpolation
Error propagation on the Euclidean motion group arises in a number of areas such as in dead reckoning errors in mobile robot navigation and joint errors that accumulate from the base to the distal end of kinematic chains such as manipulators and biological macromolecules. We address error propagation in rigid-body poses in a coordinate-free way. In this paper we show how errors propagated by convolution on the Euclidean motion group, SE(3), can be approximated to second order using the theory of Lie algebras and Lie groups. We then show how errors that are small (but not so small that linearization is valid) can be propagated by a recursive formula derived here. This formula takes into account errors to second-order, whereas prior efforts only considered the first-order case. Our formulation is nonparametric in the sense that it will work for probability density functions of any form (not only Gaussians). Numerical tests demonstrate the accuracy of this second-order theory in the context of a manipulator arm and a flexible needle with bevel tip.
Recursive error propagation; Euclidean group; spatial uncertainty
In this paper we propose an approach for the accurate rotation of a digital image using Hermite expansions. This exploits the fact that if a 2D continuous band-limited Hermite expansion is rotated, the resulting function can be expressed as a Hermite expansion with the same band limit. Furthermore, the Hermite coefficients of the initial 2D expansion and the rotated expansion are mapped through an invertible linear relationship. Two efficient methods to compute the mapping between Hermite coefficients during rotation are proposed. We also propose a method for connecting the Hermite expansion and a discrete image. Using this method, we can obtain the Hermite expansion from a discrete image and vice versa. Combining these techniques, we propose new methods for the rotation of discrete images. We assess the accuracy of our methods and compare with existing FFT-based methods implementing three shears. We find that the method proposed here consistently has better accuracy than FFT-based methods.
Image rotation; Hermite functions; Hermite expansions; Band-limited expansions
A coordinate-free Lie-group formulation for generating ensembles of DNA conformations in solution is presented. In this formulation, stochastic differential equations define sample paths on the Euclidean motion group. The ensemble of these paths exhibits the same behavior as solutions of the Fokker-Planck equation for the stochastically forced elastica. Longer chains for which the effects of excluded volume become important are handled by piecing together shorter chains and modeling their interactions. It is assumed that the final chain lengths of interest are long enough for excluded volume effects to become important, but not so long that the semi-flexible nature of the chain is lost. The effect of excluded volume is then taken into account by grouping short self-avoiding conformations into ‘bundles’ with common end constraints and computing average interaction effects between bundles. The accuracy of this approximation is shown to be good when using a numerically generated ensemble of self-avoiding sample paths as the baseline for comparison.
DNA; Conformation; Ensemble; Convolution; Lie Group; Excluded Volume; Probability Density Function
This paper presents a methodology to obtain candidate conformations of multidomain proteins for use in Molecular Replacement. For each separate domain, orientational relationship between the template and the target structure is obtained by using MR. Then, the orientational relationships of the domains are used to calculate the relative rotation between those domains in the target conformation by using pose estimation techniques from the field of Robotics and Computer Vision. With the angle of relative rotation between the domains as a cost function, iterative normal mode analysis is used to drive the template structure into the candidate conformation to match X-ray crystallography data obtained for the target conformation. As a validation, the proposed method is applied to three test proteins: Ribose-binding protein; Lactoferrin; and Calcium ATPase. In each test case, the orientation and translation of the final candidate conformation are generated correctly from the suggested procedure. The results show that the proposed method can yield applicable candidate conformations for MR and reveal the structural details of the target conformation and its position and orientation in the crystallographic unit cell.
This paper proposes a method for deblurring of class-averaged images in single-particle electron microscopy (EM). Since EM images of biological samples are very noisy, the images which are nominally identical projection images are often grouped, aligned and averaged in order to cancel or reduce the background noise. However, the noise in the individual EM images generates errors in the alignment process, which creates an inherent limit on the accuracy of the resulting class averages. This inaccurate class average due to the alignment errors can be viewed as the result of a convolution of an underlying clear image with a blurring function. In this work, we develop a deconvolution method that gives an estimate for the underlying clear image from a blurred class-averaged image using precomputed statistics of misalignment. Since this convolution is over the group of rigid body motions of the plane, SE(2), we use the Fourier transform for SE(2) in order to convert the convolution into a matrix multiplication in the corresponding Fourier space. For practical implementation we use a Hermite-function-based image modeling technique, because Hermite expansions enable lossless Cartesian-polar coordinate conversion using the Laguerre-Fourier expansions, and Hermite expansion and Laguerre-Fourier expansion retain their structures under the Fourier transform. Based on these mathematical properties, we can obtain the deconvolution of the blurred class average using simple matrix multiplication. Tests of the proposed deconvolution method using synthetic and experimental EM images confirm the performance of our method.
Single-particle electron microscopy; class average; deconvolution; Hermite expansions
We present a Lie-group-theoretic method for the kinematic and dynamic analysis of chiral semi-flexible polymers with end constraints. The first is to determine the minimum energy conformations of semi-flexible polymers with end constraints, and the second is to perform normal mode analysis based on the determined minimum energy conformations. In this paper, we use concepts from the theory of Lie groups and principles of variational calculus to model such polymers as inextensible or extensible chiral elastic rods with coupling between twisting and bending stiffnesses, and/or between twisting and extension stiffnesses. This method is general enough to include any stiffness and chirality parameters in the context of elastic filament models with the quadratic elastic potential energy function. As an application of this formulation, the analysis of DNA conformations is discussed. We demonstrate our method with examples of DNA conformations in which topological properties such as writhe, twist, and linking number are calculated from the results of the proposed method. Given these minimum energy conformations, we describe how to perform the normal mode analysis. The results presented here build both on recent experimental work in which DNA mechanical properties have been measured, and theoretical work in which the mechanics of non-chiral elastic rods has been studied.
Lie-group-theoretic method; elastica; semiflexible polymer; variational calculus; normal mode analysis
Over the past several decades a number of O(n) methods for forward and inverse dynamics computations have been developed in the multi-body dynamics and robotics literature. A method was developed in 1974 by Fixman for O(n) computation of the mass-matrix determinant for a serial polymer chain consisting of point masses. In other recent papers, we extended this method in order to compute the inverse of the mass matrix for serial chains consisting of point masses. In the present paper, we extend these ideas further and address the case of serial chains composed of rigid-bodies. This requires the use of relatively deep mathematics associated with the rotation group, SO(3), and the special Euclidean group, SE(3), and specifically, it requires that one differentiates functions of Lie-group-valued argument.
We present a unified method to generate conformational statistics which can be applied to any of the classical discrete-chain polymer models. The proposed method employs the concepts of Fourier transform and generalized convolution for the group of rigid-body motions in order to obtain probability density functions of chain end-to-end distance. In this paper, we demonstrate the proposed method with three different cases: the freely-rotating model, independent energy model, and interdependent pairwise energy model (the last two are also well-known as the Rotational Isomeric State model). As for numerical examples, for simplicity, we assume homogeneous polymer chains. For the freely-rotating model, we verify the proposed method by comparing with well-known closed-form results for mean-squared end-to-end distance. In the interdependent pairwise energy case, we take polypeptide chains such as polyalanine and polyvaline as examples.
Conformational statistics; Rigid-body motion group; Noncommutative harmonic analysis
We present algorithms for fast and stable approximation of the Hermite transform of a compactly supported function on the real line, attainable via an application of a fast algebraic algorithm for computing sums associated with a three-term relation. Trade-offs between approximation in bandlimit (in the Hermite sense) and size of the support region are addressed. Numerical experiments are presented that show the feasibility and utility of our approach. Generalizations to any family of orthogonal polynomials are outlined. Applications to various problems in tomographic reconstruction, including the determination of protein structure, are discussed.
generalized Fourier transform; Hermite transform; orthogonal polynomial transform; three-term recurrence; tomographic reconstruction; protein structure
This paper presents a new approach to study the statistics of lattice random walks in the presence of obstacles and local self-avoidance constraints (excluded volume). By excluding sequentially local interactions within a window that slides along the chain, we obtain an upper bound on the number of self-avoiding walks (SAWs) that terminate at each possible position and orientation. Furthermore we develop a technique to include the effects of obstacles. Thus our model is a more realistic approximation of a polymer chain than that of a simple lattice random walk, and it is more computationally tractable than enumeration of obstacle-avoiding SAWs. Our approach is based on the method of the lattice-motion-group convolution. We develop these techniques theoretically and present numerical results for 2-D and 3-D lattices (square, hexagonal, cubic and tetrahedral/diamond). We present numerical results that show how the connectivity constant μ changes with the length of each self-avoiding window and the total length of the chain. Quantities such as 〈R〉 and others such as the probability of ring closure are calculated and compared with results obtained in the literature for the simple random walk case.
This paper presents a new algorithm for generating the conformational statistics of lattice polymer models. The inputs to the algorithm are the distributions of poses (positions and orientations) of reference frames attached to sequentially proximal bonds in the chain as it undergoes all possible torsional motions in the lattice. If z denotes the number of discrete torsional motions allowable around each of the n bonds, our method generates the probability distribution in end-to-end pose corresponding to all of the zn independent lattice conformations in O(nD+1) arithmetic operations for lattices in D-dimensional space. This is achieved by dividing the chain into short segments and performing multiple generalized convolutions of the pose distribution functions for each segment. The convolution is performed with respect to the crystallographic space group for the lattice on which the chain is defined. The formulation is modified to include the effects of obstacles (excluded volumes), and to calculate the frequency of the occurrence of each conformation when the effects of pairwise conformational energy are included. In the latter case (which is for 3 dimensional lattices only) the computational cost is O(z4n4). This polynomial complexity is a vast improvement over the O(zn) exponential complexity associated with the brute force enumeration of all conformations. The distribution of end-to-end distances and average radius of gyration are calculated easily once the pose distribution for the full chain is found. The method is demonstrated with square, hexagonal, cubic and tetrahedral lattices.