In this paper, we study a registration problem that is motivated by a practical biology problem - fitting protein structures to low-resolution density maps. We consider registration between two sets of lines features (e.g., helices in the proteins) that have undergone not a single, but multiple isometric transformations (e.g., hinge-motions). The problem is further complicated by the presence of symmetry in each set. We formulate the problem as a clique-finding problem in a product graph, and propose a heuristic solution that includes a fast clique-finding algorithm unique to the structure of this graph. When tested on a suite of real protein structures, the algorithm achieved high accuracy even for very large inputs containing hundreds of helices.

Medical imaging has produced a large number of volumetric images capturing biological structures in 3D. Computer-based understanding of these structures can often benefit from the knowledge of shape components, particularly rod-like and plate-like parts, in such volumes. Previously, skeletons have been a common tool for identifying these shape components in a solid object. However, obtaining skeletons of a grayscale volume poses new challenges due to the lack of a clear boundary between object and background. In this paper, we present a new skeletonization algorithm on grayscale volumes typical to medical imaging (e.g., MRI, CT and EM scans), for the purpose of identifying shape components. Our algorithm does not require an explicit segmentation of the volume into object and background, and is capable of producing skeletal curves and surfaces that lie centered at rod-shaped and plate-shaped parts in the grayscale volume. Our method is demonstrated on both synthetic and medical data.

In this paper, we describe a novel, shape-modeling approach to recovering 3D protein structures from volumetric images. The input to our method is a sequence of α-helices that make up a protein, and a low-resolution volumetric image of the protein where possible locations of α-helices have been detected. Our task is to identify the correspondence between the two sets of helices, which will shed light on how the protein folds in space. The central theme of our approach is to cast the correspondence problem as that of shape matching between the 3D volume and the 1D sequence. We model both the shapes as attributed relational graphs, and formulate a constrained inexact graph matching problem. To compute the matching, we developed an optimal algorithm based on the A*-search with several choices of heuristic functions. As demonstrated in a suite of real protein data, the shape-modeling approach is capable of correctly identifying helix correspondences in noise-abundant volumes with minimal or no user intervention.

Efforts in structural biology have targeted the systematic determination of all protein structures through experimental determination or modeling. In recent years, 3-D electron cryomicroscopy (cryoEM) has assumed an increasingly important role in determining the structures of these large macromolecular assemblies to intermediate resolutions (6-10 A). While these structures provide a snapshot of the assembly and its components in well-defined functional states, the resolution limits the ability to build accurate structural models. In contrast, sequence-based modeling techniques are capable of producing relatively robust structural models for isolated proteins or domains. In this work, we developed and applied a hybrid modeling approach, utilizing cryoEM density and ab initio modeling to produce a structural model for the core domain of a herpesvirus structural protein, VP26. Specifically, this method, first tested on simulated data, utilizes the cryoEM density map as a geometrical constraint in identifying the most native-like models from a gallery of models generated by ab initio modeling. The resulting model for the core domain of VP26, based on the 8.5-A resolution herpes simplex virus type 1 (HSV-1) capsid cryoEM structure and mutational data, exhibited a novel fold. Additionally, the core domain of VP26 appeared to have a complementary interface to the known upper-domain structure of VP5, its cognate binding partner. While this new model provides for a better understanding of the assembly and interactions of VP26 in HSV-1, the approach itself may have broader applications in modeling the components of large macromolecular assemblies.