Semi-isometric registration of line features for flexible fitting of protein structures

Abstract

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.

Figure 1

Protein fitting aims at deforming a protein structure (a) into a density volume (b) imaged at a low-resolution of a similar protein or the same protein at a different state. For validation purpose, the volume in (b) is simulated.

Figure 2

Two sets of features with symmetric subunits (left), and several ways these subunits can be matched (right). The (red) highlighted matchings are less plausible as they map neighboring subunits in one set to distant ones in the other.

Figure 3

The R(e⃗₁, e⃗₂) descriptor for the oriented line segments e⃗₁ and e⃗₂ consists of the distance between their centroids d, and the angles α, β and θ.

Figure 4

The zero-tolerance product graph G₀ (right) constructed for two sets of line features S,T (left), where each feature is represented by two oriented line segments (OLSs) indicated by arrows and labeled by letters. A clique (highlighted in orange) in the graph corresponds to an isometric mapping from a cluster of OLSs in S to another cluster in T.

Figure 5

Our triangle-based search finds the largest clique in our product graph by first finding the highest valence edge (darkened in (a)), and for each vertex that forms a triangle with this edge (“?” in (b)) we add it to the clique if it shares edges with the vertices already in the clique, and discard it otherwise (“?” in (c)). The final clique is shown in (d).

Figure 6

Isometric clusters identified after the best-first search (a) (different clusters are colored differently, and black lines are un-assigned), the cost matrix for the single-feature registration (selected feature pairs have been highlighted with white circles) (b), and the final set of isometric clusters after the single-feature matching step.

Figure 7

Line features in the example of Figure 1, shown as cylinders (a) and coils (b), are colored by the isometric clusters identified using our method (black features and unassigned). (c,d) show the alignment of the two structures respectively using the isometry of red and green cluster pairs.

Figure 8

Line features detected in the 3E8K (a) and 2GP1 (b) proteins colored by the identified isometric clusters. The two shapes are overlayed (c) to show their differences. Observe that our method has successfully tolerated feature identification errors where one line feature has broken into multiple lines (region A), and where features in one shape are not present in the other (region B).

Figure 9

Registering a single chain (1OEL-A) to a large complex containing multiple similar chains (2C7C) without (a) and with (b,c) the spatial-coherence term, and the segmentation of the complex into individual chains (d, colored by chains) after repeated execution of the algorithm.

Figure 10

Applying our method repeated to segment individual chains, showing one chain (left, where colors indicate matching clusters) and the segmentation (right, where colors indicate chains).