Biomedical subjects

Gregory S Chirikjian

Publications and source records attributed to Gregory S Chirikjian.

13 recordsLinked to original sources

PubMed2006

A method for finding candidate conformations for molecular replacement using relative rotation between domains of a known structure.

This paper presents a methodology to obtain candidate conformations of multidomain proteins for use in molecular replacement. For each separate domain, the orientational relationship between the template and the target structure is obtained using standard molecular replacement. The orientational relationships of the domains are then used to calculate the relative rotation between the 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 to a candidate conformation that matches the X-ray crystallographic data obtained for the target conformation. The selection of the correct intra-protein domain orientations from among the many spurious maxima in the rotation function (including orientations obtained from domains in symmetry mates rather than within the same copy of the protein) presents a challenge. This problem is resolved by checking R factors of each domain, measuring the absolute value of relative rotation between domains, and evaluating the cost value after each candidate conformation is driven to convergence with iterative NMA. 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 in the unit cell are generated correctly from the suggested procedure. The results show that the proposed method can yield viable candidate conformations for use in molecular replacement and can reveal the structural details and pose of the target conformation in the crystallographic unit cell.

Algorithms↗

PubMed2005

Rigid-cluster models of conformational transitions in macromolecular machines and assemblies.

We present a rigid-body-based technique (called rigid-cluster elastic network interpolation) to generate feasible transition pathways between two distinct conformations of a macromolecular assembly. Many biological molecules and assemblies consist of domains which act more or less as rigid bodies during large conformational changes. These collective motions are thought to be strongly related with the functions of a system. This fact encourages us to simply model a macromolecule or assembly as a set of rigid bodies which are interconnected with distance constraints. In previous articles, we developed coarse-grained elastic network interpolation (ENI) in which, for example, only Calpha atoms are selected as representatives in each residue of a protein. We interpolate distance differences of two conformations in ENI by using a simple quadratic cost function, and the feasible conformations are generated without steric conflicts. Rigid-cluster interpolation is an extension of the ENI method with rigid-clusters replacing point masses. Now the intermediate conformations in an anharmonic pathway can be determined by the translational and rotational displacements of large clusters in such a way that distance constraints are observed. We present the derivation of the rigid-cluster model and apply it to a variety of macromolecular assemblies. Rigid-cluster ENI is then modified for a hybrid model represented by a mixture of rigid clusters and point masses. Simulation results show that both rigid-cluster and hybrid ENI methods generate sterically feasible pathways of large systems in a very short time. For example, the HK97 virus capsid is an icosahedral symmetric assembly composed of 60 identical asymmetric units. Its original Hessian matrix size for a Calpha coarse-grained model is >(300,000)(2). However, it reduces to (84)(2) when we apply the rigid-cluster model with icosahedral symmetry constraints. The computational cost of the interpolation no longer scales heavily with the size of structures; instead, it depends strongly on the minimal number of rigid clusters into which the system can be decomposed.

Algorithms↗

PubMed2005

Efficient determination of low-frequency normal modes of large protein structures by cluster-NMA.

The structure-function relationship is critical to understanding the biologically relevant functions of protein structures. Various experimental techniques and numerical modeling methods, normal mode analysis (NMA) in particular, have been employed to gain insight into this relationship. Experimental methods are often unable to provide all the desired information and comprehensive modeling techniques are often too computationally expensive. The authors build upon and optimize their cluster normal mode analysis (cNMA) tool, which uses embedded rigid-bodies and harmonic potentials to capture the biologically significant, low-frequency, oscillations of protein structures. cNMA represents atomic details with a scalable number of degrees-of-freedom, which can be chosen independent of structure size. This representation overcomes the otherwise quadratic order memory requirements and cubic order computational complexity associated with traditional all-atom NMA. cNMA is two orders of magnitude faster than traditional all-atom NMA when clustering by residue (very high resolution) and in the more traditional application using a fixed number of clusters, cNMA computationally scales as O(n), which is two orders of complexity faster than all-atom NMA. cNMA is presented and very large example structures with up to 10(6) atoms are analyzed on a notebook PC in the time scale of minutes/hours. The resulting mode shapes help identify biologically significant, conformational pathways.

Cluster Analysis↗

PubMed2005

FTRAC--a robust fluoroscope tracking fiducial.

C-arm fluoroscopy is ubiquitous in contemporary surgery, but it lacks the ability to accurately reconstruct three-dimensional (3D) information. A major obstacle in fluoroscopic reconstruction is discerning the pose of the x-ray image, in 3D space. Optical/magnetic trackers tend to be prohibitively expensive, intrusive and cumbersome in many applications. We present single-image-based fluoroscope tracking (FTRAC) with the use of an external radiographic fiducial consisting of a mathematically optimized set of ellipses, lines, and points. This is an improvement over contemporary fiducials, which use only points. The fiducial encodes six degrees of freedom in a single image by creating a unique view from any direction. A nonlinear optimizer can rapidly compute the pose of the fiducial using this image. The current embodiment has salient attributes: small dimensions (3 x 3 x 5 cm); need not be close to the anatomy of interest; and accurately segmentable. We tested the fiducial and the pose recovery method on synthetic data and also experimentally on a precisely machined mechanical phantom. Pose recovery in phantom experiments had an accuracy of 0.56 mm in translation and 0.33 degrees in orientation. Object reconstruction had a mean error of 0.53 mm with 0.16 mm STD. The method offers accuracies similar to commercial tracking systems, and appears to be sufficiently robust for intraoperative quantitative C-arm fluoroscopy. Simulation experiments indicate that the size can be further reduced to 1 x 1 X 2 cm, with only a marginal drop in accuracy.

Algorithms↗

PubMed2005

Matching and reconstruction of brachytherapy seeds using the Hungarian algorithm (MARSHAL).

Intraoperative dosimetric quality assurance in prostate brachytherapy critically depends on discerning the three-dimensional (3D) locations of implanted seeds. The ability to reconstruct the implanted seeds intraoperatively will allow us to make immediate provisions for dosimetric deviations from the optimal implant plan. A method for seed reconstruction from segmented C-arm fluoroscopy images is proposed. The 3D coordinates of the implanted seeds can be calculated upon resolving the correspondence of seeds in multiple x-ray images. We formalize seed-matching as a combinatorial optimization problem, which has salient features: (a) extensively studied solutions by the computer science community; (b) proof for the nonexistence of any polynomial time exact algorithm; and (c) a practical pseudo-polynomial algorithm that mostly runs in O(N3) time using any number of images. We prove that two images are insufficient to correctly match the seeds, while a third image renders the matching problem to be of nonpolynomial complexity. We utilize the special structure of the problem and propose a pseudopolynomial time algorithm. Using three presegmented images, matching and reconstruction of brachytherapy seeds using the Hungarian algorithm achieved complete matching in simulation experiments; and 98.5% in phantom experiments. 3D reconstruction error for correctly matched seeds has a mean of 0.63 mm, and 0.9 mm for incorrectly matched seeds. The maximum seed reconstruction error in each implant was typically around 1.32 mm. Both on synthetic data and in phantom experiments, matching rate and reconstruction error achieved using presegmented images was found to be sufficient for prostate brachytherapy. The algorithm is extendable to deal with arbitrary number of images without any loss in speed or accuracy. The algorithm is sufficiently generic to provide a practical solution to any correspondence problem, across different imaging modalities and features.

Algorithms↗

PubMed2004

Analysis of the conformational dependence of mass-metric tensor determinants in serial polymers with constraints.

It is well known that mass-metric tensor determinants det(G(s)) influence the equilibrium statistics and the rates of conformational transitions for polymers with constrained bond lengths and bond angles. It is now standard practice to include a Fixman-style compensating potential of the form U(c)(q(s)) proportional, variant(-k(B)T/2)ln[det(G(s))] as part of algorithms for torsional space molecular dynamics. This elegant strategy helps eliminate unwarranted biases that arise due to the imposition of holonomic constraints. However, the precise nature and extent of variation of det(G(s)) and hence ln[det(G(s))] with chain conformation and chain length has never been quantified. This type of analysis is crucial for understanding the nature of the conformational bias that the introduction of a Fixman potential aims to eliminate. Additionally, a detailed analysis of the conformational dependence of det(G(s)) will help resolve ambiguities regarding suggestions for incorporating terms related to det(G(s)) in the design of move sets in torsional space Monte Carlo simulations. In this work, we present results from a systematic study of the variation of det(G(s)) for a serial polymer with fixed bond lengths and bond angles as a function of chain conformation and chain length. This analysis requires an algorithm designed for rapid computation of det(G(s)) which simultaneously allows for a physical/geometric interpretation of the conformational dependence of det(G(s)). Consequently, we provide a detailed discussion of our adaptation of an O(n) algorithm from the robotics literature, which leads to simple recursion relations for direct evaluation of det(G(s)). Our analysis of the conformational dependence of det(G(s)) yields the following insights. (1) det(G(s)) is maximized for spatial conformers and minimized for planar conformations. (2) Previous work suggests that it is logical to expect that the conformational dependence of det(G(s)) becomes more pronounced with increase in chain length. Confirming this expectation, we provide systematic quantification of the nature of this dependency and show that the difference in det(G(s)) between spatial and planar conformers, i.e., between the maxima and minima of det(G(s)) grows systematically with chain length. Finally, we provide a brief discussion of implications of our analysis for the design of move sets in Monte Carlo simulations.

Journal Article↗

PubMed2004

Interhelical angle and distance preferences in globular proteins.

Orientational preferences between interacting helices within globular proteins have been studied extensively over the years. A number of classical structural models such as "knobs into holes" and "ridges into grooves" were developed decades ago to explain perceived preferences in interhelical angle distributions. In contrast, relatively recent works have examined statistical biases in angular distributions which result from spherical geometric effects. Those works have concluded that the predictions of classical models are due in large part to these biases. In this article we perform an analysis on the largest set of helix-helix interactions within high-resolution structures of nonhomologous proteins studied to date. We examine the interhelical angle distribution as a function of spatial distance between helix pairs. We show that previous efforts to normalize angle distribution data did not include two important effects: 1), helices can interact with each other in three distinct ways which we refer to as "line-on-line," "endpoint-to-line," and "endpoint-to-endpoint," and each of these interactions has its own geometric effects which must be included in the proper normalization of data; and 2), all normalizations that depend on geometric parameters such as interhelical angle must occur before the data is binned to avoid artifacts of bin size from biasing the conclusions. Taking these two points into account, we find that there are very pronounced preferences for helices to interact at angles of approximately +/-160 and +/-20 degrees in the line-on-line case. This pattern persists when the closest alpha-carbons in the helices vary from 4 to 12 A. The endpoint-to-line and endpoint-to-endpoint cases also exhibit distinct preferences when the data is normalized properly. Analysis of the local structural interactions which give rise to these preferences has not been studied here and is left for future work.

Computer Simulation↗

PubMed2004

Normal mode analysis of proteins: a comparison of rigid cluster modes with C(alpha) coarse graining.

The ability to infer dynamic motions from an equilibrium (static) conformation of a protein can be essential in establishing structure-function relationships. In particular, the low-frequency motions are of functional interest because statistical mechanics predicts these motions will have the largest amplitudes. In this paper, we address the computational cost of normal mode analysis (NMA) applied to a C(alpha)-based elastic network model (C(alpha)-NMA) and present a new coarse-grained rigid-body-based analysis (cluster-NMA). This new method represents a protein as a collection of rigid bodies interconnected with harmonic potentials. This representation produces reduced degree-of-freedom (DOF) equations of motion (EOMs) which, even in the case of large structures (10(3+) residues), enables the computation of normal modes to be done on a desktop PC. We present the complete theory and analysis of cluster-NMA and also include its application to a variety of structures. The results of the new method are compared with C(alpha)-NMA and it is shown that cluster-NMA produces very good approximations to the lowest modes at a fraction of the computational cost.

Algorithms↗

PubMed2003

An elastic network model of HK97 capsid maturation.

The structure of the capsid of bacteriophage HK97 has been solved at various stages of maturity by crystallography and cryo-electron microscopy, and has been reported previously in the literature. Typically the capsid assembles through polymerization and maturation processes. Maturation is composed of proteolytic cleavages to the precursor capsid (called Prohead II), expansion triggered by DNA packaging (in which the largest conformational changes of the capsid appear), and covalent cross-links of neighboring subunits to create the mature capsid called Head II. We apply a coarse-grained elastic network interpolation (ENI) to generate a feasible pathway for conformational change from Prohead II to Head II. The icosahedral symmetry of the capsid structure offers a significant computational advantage because it is not necessary to consider the whole capsid structure but only an asymmetric unit consisting of one hexamer plus an additional subunit from an adjacent pentamer. We also analyze normal modes of the capsid structure using an elastic network model which is also subject to symmetry constraints. Using our model, we can visualize the smooth evolution of capsid expansion and revisit in more detail several interesting geometric changes recognized in early experimental works such as rigid body motion of two compact domains (A and P) with two refolding extensions (N-arm and E-loop) and track the approach of the two particular residues associated with isopeptide bonds that make hexagonal cross-links in Head II. The feasibility of the predicted pathway is also supported by the results of our normal mode analysis.

Bacteriophages↗

PubMed2003

A comparison between elastic network interpolation and MD simulation of 16S ribosomal RNA.

In this paper a coarse-grained method called elastic network interpolation (ENI) is used to generate feasible transition pathways between two given conformations of the core central domain of 16S Ribosomal RNA (16S rRNA). The two given conformations are the extremes generated by a molecular dynamics (MD) simulation, which differ from each other by 10A in root-mean-square deviation (RMSD). It takes only several hours to build an ENI pathway on a 1.5GHz Pentium with 512 MB memory, while the MD takes several weeks on high-performance multi-processor servers such as the SGI ORIGIN 2000/2100. It is shown that multiple ENI pathways capture the essential anharmonic motions of millions of timesteps in a particular MD simulation. A coarse-grained normal mode analysis (NMA) is performed on each intermediate ENI conformation, and the lowest 1% of the normal modes (representing about 40 degrees of freedom (DOF)) are used to parameterize fluctuations. This combined ENI/NMA method captures all intermediate conformations in the MD run with 1.5A RMSD on average. In addition, if we restrict attention to the time interval of the MD run between the two extreme conformations, the RMSD between the closest ENI/NMA pathway and the MD results is about 1A. These results may serve as a paradigm for reduced-DOF dynamic simulations of large biological macromolecules as well as a method for the reduced-parameter interpretation of massive amounts of MD data.

Algorithms↗

PubMed2002

Efficient generation of feasible pathways for protein conformational transitions.

We develop a computationally efficient method to simulate the transition of a protein between two conformations. Our method is based on a coarse-grained elastic network model in which distances between spatially proximal amino acids are interpolated between the values specified by the two end conformations. The computational speed of this method depends strongly on the choice of cutoff distance used to define interactions as measured by the density of entries of the constant linking/contact matrix. To circumvent this problem we introduce the concept of using a cutoff based on a maximum number of nearest neighbors. This generates linking matrices that are both sparse and uniform, hence allowing for efficient computations that are independent of the arbitrariness of cutoff distance choices. Simulation results demonstrate that the method developed here reliably generates feasible intermediate conformations, because our method observes steric constraints and produces monotonic changes in virtual bond and torsion angles. Applications are readily made to large proteins, and we demonstrate our method on lactate dehydrogenase, citrate synthase, and lactoferrin. We also illustrate how this framework can be used to complement experimental techniques that partially observe protein motions.

Biophysical Phenomena↗

PubMed2002

Elastic models of conformational transitions in macromolecules.

We develop a computationally efficient and physically realistic method to simulate the transition of a macromolecule between two conformations. Our method is based on a coarse-grained elastic network model in which contact interactions between spatially proximal parts of the macromolecule are modelled with Gaussian/harmonic potentials. To delimit the interactions in such models, we introduce a cutoff to the permitted number of nearest neighbors. This generates stiffness (Hessian) matrices that are both sparse and quite uniform, hence, allowing for efficient computations. Several toy models are tested using our method to mimic simple classes of macromolecular motions such as stretching, hinge bending, shear, compression, ligand binding and nucleic acid structural transitions. Simulation results demonstrate that the method developed here reliably generates sequences of feasible intermediate conformations of macromolecules, since our method observes steric constraints and produces monotonic changes to virtual bond angles and torsion angles. A final application is made to the opening process of the protein lactoferrin.

Computer Simulation↗

PubMed2002

Numerical algorithms for spatial registration of line fiducials from cross-sectional images.

We present several numerical algorithms for six-degree-of-freedom rigid-body registration of line fiducial objects to their marks in cross-sectional planar images, such as those obtained in CT and MRI, given the correspondence between the marks and line fiducials. The area of immediate application is frame-based stereotactic procedures, such as radiosurgery and functional neurosurgery. The algorithms are also suitable to problems where the fiducial pattern moves inside the imager, as is the case in robot-assisted image-guided surgical applications. We demonstrate the numerical methods on clinical CT images and computer-generated data and compare their performance in terms of robustness to missing data, robustness to noise, and speed. The methods show two unique strengths: (1) They provide reliable registration of incomplete fiducial patterns when up to two-thirds of the total fiducials are missing from the image; and (2) they are applicable to an arbitrary combination of line fiducials without algorithmic modification. The average speed of the fastest algorithm is 0.3236 s for six fiducial lines in real CT data in a Matlab implementation.

Algorithms↗