Browsing by Author "Berlin, Konstantin"
Now showing 1 - 3 of 3
Results Per Page
Sort Options
Item A Hierarchical Algorithm for Fast Debye Summation with Applications to Small Angle Scattering(2011-09-01) Gumerov, Nail A.; Berlin, Konstantin; Fushman, David; Duraiswami, RamaniDebye summation, which involves the summation of sinc functions of distances between all pair of atoms in three dimensional space, arises in computations performed in crystallography, small/wide angle X-ray scattering (SAXS/WAXS) and small angle neutron scattering (SANS). Direct evaluation of Debye summation has quadratic complexity, which results in computational bottleneck when determining crystal properties, or running structure refinement protocols that involve SAXS or SANS, even for moderately sized molecules. We present a fast approximation algorithm that efficiently computes the summation to any prescribed accuracy epsilon in linear time. The algorithm is similar to the fast multipole method (FMM), and is based on a hierarchical spatial decomposition of the molecule coupled with local harmonic expansions and translation of these expansions. An even more efficient implementation is possible when the scattering profile is all that is required, as in small angle scattering reconstruction (SAS) of macromolecules. We examine the relationship of the proposed algorithm to existing approximate methods for profile computations, and provide detailed description of the algorithm, including error bounds and algorithms for stable computation of the translation operators. Our theoretical and computational results show orders of magnitude improvement in computation complexity over existing methods, while maintaining prescribed accuracy.Item Hierarchical O(N) Computation of Small-Angle Scattering Profiles and their Associated Derivatives(2013-05-25) Berlin, Konstantin; Gumerov, Nail A.; Fushman, David; Duraiswami, RamaniFast algorithms for Debye summation, which arises in computations performed in crystallography, small/wide-angle X-ray scattering (SAXS/WAXS) and small-angle neutron scattering (SANS), were recently presented in Gumerov et al. (J. Comput. Chem., 2012, 33:1981). The use of these algorithms can speed up computation of scattering profiles in macromolecular structure refinement protocols. However, these protocols often employ an iterative gradient-based optimization procedure, which then requires derivatives of the profile with respect to atomic coordinates. An extension to one of the algorithms is presented which allows accurate, O(N) cost computation of the derivatives along with the scattering profile. Computational results show orders of magnitude improvement in computational efficiency, while maintaining prescribed accuracy. This opens the possibility to efficiently integrate small-angle scattering data into structure determination and refinement of macromolecular systems.Item Protein-Protein Docking Using Long Range Nuclear Magnetic Resonance Constraints(2010) Berlin, Konstantin; O'Leary, Dianne P; Fushman, David; Computer Science; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)One of the main methods for experimentally determining protein structure is nuclear magnetic resonance (NMR) spectroscopy. The advantage of using NMR compared to other methods is that the molecule may be studied in its natural state and environment. However, NMR is limited in its facility to analyze multi-domain molecules because of the scarcity of inter-atomic NMR constraints between the domains. In those cases it might be possible to dock the domains based on long range NMR constraints that are related to the molecule's overall structure. We present two computational methods for rigid docking based on long range NMR constraints. The first docking method is based on the overall alignment tensor of the complex. The docking algorithm is based on the minimization of the difference between the predicted and experimental alignment tensor. In order to efficiently dock the complex we introduce a new, computationally efficient method called PATI for predicting the molecular alignment tensor based on the three-dimensional structure of the molecule. The increase in speed compared to the currently best-known method (PALES) is achieved by re-expressing the problem as one of numerical integration, rather than a simple uniform sampling (as in the PALES method), and by using a convex hull rather than a detailed representation of the surface of a molecule. Using PATI, we derive a method called PATIDOCK for efficiently docking a two-domain complex based solely on the novel idea of using the difference between the experimental alignment tensor and the predicted alignment tensor computed by PATI. We show that the alignment tensor fundamentally contains enough information to accurately dock a two-domain complex, and that we can very quickly dock the two domains by pre-computing the right set of data. A second new docking method is based on a similar concept but using the rotational diffusion tensor. We derive a minimization algorithm for this docking method by separating the problem into two simpler minimization problems and approximating our energy function by a quadratic equation. These methods provide two new efficient procedures for protein docking computations.