Nucleic Acids Research, 2008, Vol. 36, Web Server issue W249 exhaustive comparison of all contiguous fragments in the two protein structures, our method can detect structurally similar fragments that are in opposite order along the protein sequences. After obtaining an exhaustive list of structurally similar fragment pairs, we need to resolve the conﬂicts among them. A conﬂict occurs if in the list of matched fragment pairs, a residue from one protein is matched with multiple residues from the other protein. In practice, we have found that biologically signiﬁcant matches have much longer fragment length than the spurious ones due to accidental structural similarity. So we remove the conﬂicts in the list by preferring fragment pairs with longer length. Finally, pFlexAna hierarchically clusters the fragment pairs. The idea is to treat each structurally similar fragment pair as a point and divide these points into k clusters so that the dominant structural diﬀerences occur across clusters. To do this, we build a similarity graph. The ver- tices of this graph correspond to the fragment pairs obtained after conﬂict resolution. There is an edge between every two vertices, and the associated edge weight rep- resents the similarity between the fragment pairs corre- sponding to the two vertices. Here, similarity is deﬁned as the root mean square deviation (RMSD) for the best superposition when the two fragment pairs are combined. After constructing the similarity graph, we recursively remove from the graph the edge with the greatest weight and thus separate the most dissimilar fragment pairs, which represent the largest structural diﬀerence. We con- tinue this edge removal process until the graph breaks into k connected components. The web server implementation of our method uses PHP for its front-end interface, C++ for back-end pro- cessing, and a Ruby daemon to interface the front and back ends. The output images are generated using PyMol (15) and interactive displays of each alignment are pro- vided using Jmol (16). RESULTS We illustrate the results of pFlexAna on several repre- sentative cases. Ubiquitin ligase The crystal structures of the E6AP and WWP1 ubiquitin ligases [PDB codes 1D5F:C (2) and 1ND7 (3)] display a striking example of domain movement (Figure 1). pFlexAna ﬁnds six core regions of signiﬁcant structural similarity between the proteins and successfully clusters them into two domains which move independently (see Figure 1). These images are obtained directly from the web server, but annotated with an arrow and dotted ovals to draw attention to the domains that are aligned. The relative movement between the domains has been char- acterized as a 100 degree sweep with a 30 degree tilt (3). Superpositions, such as those shown in Figure 1, help to highlight the context of each protein region undergoing conformation change. Superpositions of similar regions, as shown in Figure 1, are ideal for visualization because they show the diﬀerence as a divergence from a ﬁxed reference point. Beyond simply showing the context of each ‘ﬂexible’ region, each superposition indicates a transition from similar (rigid) to diﬀerent (ﬂexible). Glutamine amidotransferase and arabinose-binding protein The ubiquitin ligases have moderate sequence identity (< 40%), but we have tested pFlexAna on a range of pro- tein pairs with low sequence identity such as the isomerase domain of glucosamine 6P synthase [1MOQ (17)] and arabinose binding protein [8ABP (18)], which have 10% sequence identity. Figure 5 shows the alignments of 1MOQ and 8ABP. pFlexAna ﬁnds two independent domains. Each aligned domain centers around a parallel b-sheet buried by a-helices. In this ﬁgure, each align- ment is rotated for viewing down the plane of an aligned sheet. To see the magnitude of the domain movement, note that the N-terminal domain of 8ABP (magenta) appears in the upper-right of both views, and 1MOQ (orange) is dramatically shifted between the two alignments. Figure 5. Proteins 1MOQ (orange) and 8ABP (purple) are aligned by pFlexAna according to their N-terminal domains in (a) and according to their C-terminal domains in (b). The N-terminal residues of each protein are shaded lighter than the C-terminal residues. Each alignment includes a parallel b-sheet (circled).