1 May 2018 in Applied and Computational Harmonic Analysis
29 April 2020 in Inverse Problems
Let be a compact group and let . We define the non-unique games (NUG) problem as finding to minimize . We introduce a convex relaxation of the NUG problem to a semidefinite program (SDP) by taking the Fourier transform of f
ij
over . The NUG framework can be seen as a generalization of the little Grothendieck problem over the orthogonal group and the unique games problem and includes many practically relevant problems, such as the maximum likelihood estimator to registering bandlimited functions over the unit sphere in d -dimensions and orientation estimation of noisy cryo-electron microscopy (cryo-EM) projection images. We implement an SDP solver for the NUG cryo-EM problem using the alternating direction method of multipliers (ADMM). Numerical study with synthetic datasets indicate that while our ADMM solver is slower than existing methods, it can estimate the rotations more accurately, especially at low signal-to-noise ratio (SNR).
11 January 2023 in Nature Communications
The new developments in Cryo-EM Single Particle Analysis are helping us to understand how the macromolecular structure and function meet to drive biological processes. By capturing many states at the particle level, it is possible to address how macromolecules explore different conformations, information that is classically extracted through 3D classification. However, the limitations of classical approaches prevent us from fully understanding the complete conformational landscape due to the reduced number of discrete states accurately reconstructed. To characterize the whole structural spectrum of a macromolecule, we propose an extension of our Zernike3D approach, able to extract per-image continuous flexibility information directly from a particle dataset. Also, our method can be seamlessly applied to images, maps or atomic models, opening integrative possibilities. Furthermore, we introduce the ZART reconstruction algorithm, which considers the Zernike3D deformation fields to revert particle conformational changes during the reconstruction process, thus minimizing the blurring induced by molecular motions.
4 March 2020 in Inverse Problems
Cryo-electron microscopy (cryo-EM), the subject of the 2017 Nobel Prize in Chemistry, is a technology for obtaining 3D reconstructions of macromolecules from many noisy 2D projections of instances of these macromolecules, whose orientations and positions are unknown. These molecules are not rigid objects, but flexible objects involved in dynamical processes. The different conformations are exhibited by different instances of the macromolecule observed in a cryo-EM experiment, each of which is recorded as a particle image. The range of conformations and the conformation of each particle are not known a priori ; one of the great promises of cryo-EM is to map this conformation space. Remarkable progress has been made in reconstructing rigid molecules based on homogeneous samples of molecules in spite of the unknown orientation of each particle image and significant progress has been made in recovering a few distinct states from mixtures of rather distinct conformations, but more complex heterogeneous samples remain a major challenge. We introduce the ‘hyper-molecule’ theoretical framework for modeling structures across different states of heterogeneous molecules, including continuums of states. The key idea behind this framework is representing heterogeneous macromolecules as high-dimensional objects, with the additional dimensions representing the conformation space. This idea is then refined to model properties such as localized heterogeneity. In addition, we introduce an algorithmic framework for reconstructing such heterogeneous objects from experimental data using a Bayesian formulation of the problem and Markov chain Monte Carlo (MCMC) algorithms to address the computational challenges in recovering these high dimensional hyper-molecules. We demonstrate these ideas in a preliminary prototype implementation, applied to synthetic data.
10 April 2013 in BMC Bioinformatics
Read alignment is a computational bottleneck in some sequencing projects. Most of the existing software packages for read alignment are based on two algorithmic approaches: prefix-trees and hash-tables. We propose a new approach to read alignment using random permutations of strings.