Search tips
Search criteria 


Logo of bioinfoLink to Publisher's site
Bioinformatics. 2011 September 15; 27(18): 2537–2545.
Published online 2011 July 26. doi:  10.1093/bioinformatics/btr432
PMCID: PMC3167051

Alignment of distantly related protein structures: algorithm, bound and implications to homology modeling


Motivation: Building an accurate alignment of a large set of distantly related protein structures is still very challenging.

Results: This article presents a novel method 3DCOMB that can generate a multiple structure alignment (MSA) with not only as many conserved cores as possible, but also high-quality pairwise alignments. 3DCOMB is unique in that it makes use of both local and global structure environments, combined by a statistical learning method, to accurately identify highly similar fragment blocks (HSFBs) among all proteins to be aligned. By extending the alignments of these HSFBs, 3DCOMB can quickly generate an accurate MSA without using progressive alignment. 3DCOMB significantly excels others in aligning distantly related proteins. 3DCOMB can also generate correct alignments for functionally similar regions among proteins of very different structures while many other MSA tools fail. 3DCOMB is useful for many real-world applications. In particular, it enables us to find out that there is still large improvement room for multiple template homology modeling while several other MSA tools fail to do so.

Availability: 3DCOMB is available at

Contact: jinboxu/at/

Supplementary Information: Supplementary data are available at Bioinformatics online.


Multiple protein alignment has been extensively used for classification, analysis of evolutionary relationship, motif detection and structure/function prediction. When proteins are distantly related, sequence methods usually fail to yield accurate alignment. In contrast, structure methods, which exploit geometrical information, may still work well. As more protein structures are experimentally solved, multiple structure alignment (MSA) is becoming more useful and important. However, developing computational methods for accurate MSA, especially of a large set of distantly related protein structures, is still regarded as an open challenge. An MSA method consists of two critical components: a scoring function measuring of the quality of an MSA and an algorithm searching for the MSA optimizing the score.

Many MSA algorithms have been developed, such as MAMMOTH (Lupyan et al., 2005), MATT (Menke et al., 2008), MultiProt (Shatsky et al., 2004), MUSTANG (Konagurthu et al., 2006), POSA (Ye and Godzik, 2005) and SALIGN (Eswar et al., 2008; Madhusudhan et al., 2009). These methods can be broadly divided into two groups: ‘horizontal-first’ or ‘vertical-first’. The former progressively merges pairwise alignments into an MSA, which may be suboptimal since pairwise alignment errors carry over to the final result. The vertical-first methods identify some similar fragment blocks (SFB) among proteins and then extend the SFB alignments to MSAs. The number of SFBs could grow exponentially with respect to the number of proteins, so these methods may have to examine a large number of SFBs not to miss the best MSA, which is usually computationally expensive. As such, the challenge facing a vertical-first method is to identify only those SFBs, which are very likely contained in the best MSA.

This article presents 3DCOMB, a novel vertical-first method for MSA. 3DCOMB distinguishes itself from others in its search algorithm and scoring function. 3DCOMB makes use of both local and global structure environments, combined by a novel machine learning method, to accurately identify highly similar fragment blocks (HSFBs), which are very likely contained in the best MSA. 3DCOMB searches for the best MSA starting from the alignment of an HSFB. Local structure environment is used to describe the structural difference between two short segments centered on two residues. Global structure environment is used to measure the similarity of two substructures centered at the two residues. Both features are combined by a probabilistic graphical model Conditional Random Fields (CRF) (Lafferty et al., 2001) to determine if two residues shall be aligned or not. Existing methods [e.g. BLOMAPS (Wang and Zheng, 2009)] employ only local structure environment and sometimes fail to detect good HSFBs. They usually have to examine a large number of not-so-conserved fragment blocks in order to find the best MSA. In contrast, 3DCOMB can generate accurate MSAs from only very few HSFBs and thus, improve accuracy without too much computational time.

Many methods do not explicitly take into consideration the quality of pairwise alignments in building an MSA, so it may not necessarily contain high-quality pairwise alignments. 3DCOMB aims to generate an MSA with not only as many conserved cores as possible, but also accurate pairwise alignments. A core is a fully aligned column without any gaps, consisting of one residue from each input protein. 3DCOMB achieves this by employing a novel scoring function An external file that holds a picture, illustration, etc.
Object name is btr432i1.jpg for MSA where CORE-LEN is the number of cores in the MSA. TMscore (Zhang and Skolnick, 2004), ranging from 0 to 1, is a widely used measure for pairwise structure similarity. The higher the TMscore, the more similar two protein structures are. An external file that holds a picture, illustration, etc.
Object name is btr432i2.jpg is the TMscore averaged over all the pairwise alignments and thus, analogous to ‘sum-of-pairs’ used for MSA. The strength of this scoring function will be detailed in Section 2.

Our tests show that 3DCOMB generates alignments with not only better CORE-LEN and An external file that holds a picture, illustration, etc.
Object name is btr432i3.jpg, but also smaller core RMSD although it is not explicitly optimized. 3DCOMB significantly excels others for the alignment of a large group of distantly related proteins. Although not specifically designed for this, 3DCOMB can also generate correct alignments for functionally similar sites among proteins not in the same superfamily while many other MSA tools fail. We also estimate the gap between 3DCOMB alignments and the best possible. When proteins are closely related, 3DCOMB alignments are almost the best possible. Otherwise they may still have a gap from the best possible. 3DCOMB also helps us find out that there is still large improvement room for homology modeling, but several other MSA tools fail to do so.


This section contains (i) a machine learning method to detect HSFBs, using both local and global structure information; and (ii) a new scoring function and an optimization algorithm to search for the best MSA starting from the HSFBs.

2.1 HSFB

We use both local and global structure environments to determine how likely two residues should be aligned. To the best of our knowledge, no previous methods consider the global structure environment. The local structure environment of a residue consists of 10 structure segments of length 2k+1(k=1, 2,…, 10) centered at this residue. Given two residues of two different proteins, the similarity of their local structure environments is measured by 10 TMscore values, each measuring the similarity of two structure segments of the same size. The global structure environment of a residue i is defined as follows. Let N(i, d) denote all the residues in the same protein within distance cutoff d from i. The global structure environment of i (under a given distance cutoff d) consists of all the 5mer segments centered at the residues in N(i, d). Given two residues of different proteins, to calculate the similarity of their global structure environments, we first generate a rigid body transformation for them by minimizing the RMSD of two center 5mer segments. Then we fix this transformation and run dynamic programming to align them by maximizing TMscore. We generate 10 such global structure environment features, using 10 distance cutoff values 6, 7,…, 15 Å.

Modeling pairwise structure alignment using CRF: CRFs are probabilistic graphical models that have been applied to protein secondary structure prediction (Wang et al., 2010), protein conformation sampling (Zhao et al., 2010a; Zhao et al., 2010b), protein sequence alignment (Do et al., 2006) and protein threading (Peng and Xu, 2010). Here, we use CRF to model protein structure alignment, which then is used to identify HSFBs among proteins under consideration.

Let p, q denotes two input proteins and their associated structural features (i.e. local and global structure environment similarity scores). Let X={M, Ip, Iq} be a set of three possible alignment states. Meanwhile, M indicates that two residues are aligned and Ip and Iq indicate insertion at proteins p and q, respectively. Let A={a1, a2,…, aNA} denote an alignment between p and q where ai[set membership]X represents the state (or label) at position i and NA denotes the length of this alignment. Our CRF model defines the conditional probability of an alignment A given p and q as follows:

equation image

equation image

and θ={λ1, λ2,…, λd} is the model parameter and F(A, p, q, i) is a function estimating the log-likelihood of an alignment at position i:

equation image

where ek(ai−1, ai) and νl(ai, p, q, i) are called edge and label feature functions, respectively. The edge features model the dependency of the state transition from alignment position i −1 to i. Here, we assume ek(ai−1, ai) is independent of protein features to make our formulation simple. ek(ai−1, ai) is equal to 1 if the transition ai−1ai exists at position i; otherwise 0. We forbid transition from Iq to Ip, so there are in total eight state transitions. That is, k ranges from 1 to 8. The label features model the relationship between ai and the local and global structure environment similarity scores at the alignment position i. There are in total 20 different label feature functions, each corresponding to one local or global structure environment similarity score. Therefore, l ranges from 1 to 20. To make the formulation simple, we assume an insertion state is independent of protein features, so modeling of insertions is implicitly taken into consideration in the edge feature functions.

We train the model parameters using a set of reference alignments taken from FSSP (Holm and Sander, 1994). In particular, we randomly selected 50 pairs for training and the other 50 pairs for test. The training and test sets have no overlap with our benchmarks. All the structural alignments (i.e. reference alignments) were generated by DALI (Holm and Sander, 1993) and each alignment has a DALI Z-score >8.0. The model parameters are initialized randomly to a value between 0 and 1 and the training process converges within ~100 iterations. Five-fold cross-validation is conducted to determine the regularization factor in the CRF model. Once the model parameters are determined, for a given protein pair p and q, we can generate their alignment by maximizing Pθ(A|p, q). This alignment may not be the best, but can be used as an initial alignment between p and q. Starting from these initial alignments, we can build very accurate pairwise alignments (Supplementary Material).

As shown in Supplementary Figure S1, the global features corresponding to distance cutoffs 7, 8, 14 and 15 Å have relatively large weight factors. This is consistent with the findings in da Silveira et al. (2009), which shows that 7 Å is the best cutoff for distance-based contact definition. Both 14 and 15 Å may be interpreted as the distance cutoffs for second-order contacts. To speed up, we exclude six local structure environment features and eight global structure environment features with small weight factors from our final CRF model. By using only six features, we will not lose much accuracy in identifying HSFBs. The remaining two global features correspond to global structure environments at radius 8.0 and 14.0 Å. The remaining four local features correspond to structure segments with lengths 9, 13, 17 and 21, respectively.

Detecting HSFBs using CRF: given two protein structures, we can calculate the marginal probability of two fragments being aligned using the forward–backward algorithm (Lafferty et al., 2001). In this article, we consider only fragments of length L=12. Such a fragment is likely to cover at least one secondary structure segment. A slight change of L will not impact the final result much. This marginal probability is defined as the similarity score of two structure fragments. Given a short fragment F1 in protein p1 and another protein pi, let Fi denote the fragment of the same size in pi, which has the highest similarity score with F1. All the fragments F1, F2,…, FM form an HSFB with F1 being the pivot fragment. A protein of size N in total have NL+1 HSFBs. Note that the ‘highest similarity’ relationship is asymmetric. That is, among all fragments in protein pi, Fi is the most similar one to F1 may not imply that among all fragments of p1, F1 also is the most similar one to Fi. Therefore, given M proteins with lengths N1, N2,…, NM, there are in total (∑i=1MNi)−ML+M HSFBs.

Ranking HSFBs by spatial consistency: two HSFBs may be geometrically inconsistent with each other. That is, we cannot superimpose well the fragments in both HSFBs using a single set of rigid body transformations. We can calculate the degree to which two HSFBs are geometrically consistent and then rank all the HSFBs according to their consistency with others. The HSFB with the highest consistency score is very likely contained in the best MSA. We use a simple method to estimate the consistency score of one HSFB as follows. For each fragment in the HSFB, we generate a rigid body transformation by minimizing the RMSD between this fragment (Kabsch, 1976) and the pivot fragment. Let B1={F11, F12,…, F1M} denote the HSFB for which we want to calculate its consistency score and F11 is the pivot fragment. Let Ti(i=2, 3,…, M) denote the rigid body transformations derived from superimposing F1i to F11. Let B2={F21, F22,…, F2M} denote another HSFB. For any fragment F2i (i=2, 3,…, M) in B2, we superimpose F2i to F21 using the transformation Ti and then calculate the RMSD between F2i and F21. If the distance is within 3 Å, we increase the consistency score of B1 by 1, otherwise by 0.

2.2 Algorithm for MSA

Overview: as shown in Figure 1, 3DCOMB first generates a list of pivot structures. By default, this list contains all the input proteins, so TopK is equal to M. For each pivot structure, 3DCOMB uses the CRF model to generate HSFBs, which are ranked by their spatial consistency scores and only the TopJ with the highest scores are extended to initial MSAs. 3DCOMB identifies those ‘unanchored’ proteins which are not well aligned to the pivot. To improve an initial MSA, 3DCOMB conducts TopF trials to realign each of the ‘unanchored’ proteins to the pivot. Finally, 3DCOMB refine the whole MSA based on the consensus structure derived from the MSA.

Fig. 1.
The 3DCOMB algorithm overview.

Scoring function: a good MSA should have a large number of cores (i.e. CORE-LEN) and also a small core RMSD. A core is a fully aligned column, consisting of one residue from each input protein. In addition, pairwise alignments in an MSA should also be of high quality. It is challenging to develop an algorithm that can optimize these criteria simultaneously since sometimes they contradict with one another. For example, a large CORE-LEN usually leads to a large RMSD value. A simple solution is to fix one criterion and then optimize the others, e.g. maximizing CORE-LEN while restricting RMSD. This solution is not very flexible in that we have to determine RMSD in advance, not to mention that neither CORE-LEN nor RMSD is the best measure.

We use An external file that holds a picture, illustration, etc.
Object name is btr432i4.jpg as the scoring function where An external file that holds a picture, illustration, etc.
Object name is btr432i5.jpg of an MSA is defined as the average TMscore of all the pairwise alignments implied in the MSA. TMscore is widely used to measure the pairwise structure similarity and the quality of a protein model. It is defined as follows:

equation image

equation image

Meanwhile, Lali is the alignment between protein p and q, LS is the shorter protein length, di is the deviation of two aligned residues and d0 is the length-related normalization term.

Our scoring function has the following features: (i) it leads to an MSA with not only a large number of conserved cores, but also high-quality pairwise alignments; (ii) the distance between two aligned residues is used as denominator, so it favors the aligned residue pairs within small distance and disfavors or even ignores those with large deviation. This enables us to detect even a small conserved region among proteins of very different structures. In contrast, RMSD for the whole alignment, even normalized by alignment length, is (Levitt and Gerstein, 1998; Siew et al., 2000) greatly affected by a small number of badly aligned residue pairs and not sensitive in detecting small but conserved regions; (iii) TMscore is also better than the alignment length since the latter does not take into consideration the distance deviation of aligned residue pairs; (iv) TMscore is almost independent of the protein length (Zhang and Skolnick, 2004) since the distance at each position is normalized by a length-dependent factor. This is particularly useful for the alignment of a large set of proteins with very different lengths; (v) TMscore is not only good for alignment, but also very sensitive in detecting fold-level similarity. As reported in Xu and Zhang (2010), when TMscore >0.6, it is very likely (90% of chance) that two proteins have the same fold. When TMscore <0.4, it is very likely (90% of chance) that two proteins have different folds. When TMscore >0.5, there is 50% of chance that two proteins have similar folds.

Building an initial MSA from an HSFB: given an HSFB of M structures, we first generate a set of M − 1 rigid body transformations by superimposing each fragment in the HSFB to the pivot fragment and minimizing the RMSD of these two fragments. Then we superimpose each structure to the pivot structure using the transformation generated from fragment superimposition, and run dynamic programming to generate an alignment of the two structures by maximizing the TMscore. Finally, we assemble the M − 1 pairwise alignments into an initial MSA using the pivot structure as the anchor.

Adjustment of pairwise alignment: given the initial MSA, we may refine it by adjusting the pairwise alignment between each input structure and the pivot structure (Wang and Zheng, 2008). First, we calculate the TMscore of the pairwise alignment between each input structure and the pivot. If TMscore <0.5 (Xu and Zhang, 2010), this input structure is called ‘unanchored’. We adjust the alignment between each unanchored structure and the pivot using rigid body transformations derived from other TopF HSFBs. In particular, for each top HSFB, let F1 and F2 denote the fragments in the HSFB belonging to the pivot and the unanchored structure, respectively. We realign the unanchored structure to the pivot structure using the rigid body transformation generated from minimizing the RMSD between F1 and F2. The pairwise alignment with the maximum TMscore is kept in the MSA.

Consensus-based MSA refinement: 3DCOMB refines an MSA by realigning each input structure to the consensus structure, which is constructed as follows. At each column of this MSA, we calculate the center of all the aligned residues (only Cα is considered). Second, we merge two neighbor columns into a single one if the following two conditions are satisfied: (i) the total number of aligned residues in these two columns is not more than the total number of input structures; and (ii) the distance between their two centers is <3.0 Å. We use 3.0 Å as the cutoff because in native protein structures, >99% of Cα−Cα virtual bonds are >3.0 Å. This merge procedure is repeated until no columns can be merged. The consensus structure consists of all the centers. This refinement procedure is repeated until a given number of iterations or the scoring function cannot be improved further.

2.3 3DCOMB time complexity

Let N denote the maximum length of the input M protein structures. We analyze the time complexity of 3DCOMB as follows:

  • Step 1: Generate HSFB: given one pivot protein and another one, it takes time O(N2) to generate protein features and run the forward–backward algorithm to calculate all the marginal probabilities. Afterwards, given one fragment F in the pivot, it takes time O(N) to detect a fragment on another protein with the highest similarity score to F. There are M proteins, so the time complexity of HSFB generation for a given pivot protein is O(MN2).
  • Step 2: Sort HSFB by spatial consistency: it takes O(M) time to generate M −1 rigid body transformations to align the fragments in one HSFB. It takes O(M) time to calculate the spatial consistency score of one HSFB with another HSFB. So the total time complexity for a given pivot protein is O(MN2).
  • Step 3: Building an initial MSA from an HSFB: it takes O(M) time to generate M −1 rigid body transformations to align the M − 1 fragments in one HSFB to the pivot fragment. It takes O(N2) time to align one structure to the pivot given a rigid body transformation. The total time complexity is O(MN2).
  • Step 4: Adjust pairwise alignments in an initial MSA: given one HSFB and the pivot protein, we need to conduct at most TopF adjustments to realign each of the unanchored proteins to the pivot. Each needs to run a dynamic programming algorithm with time O(N2), so the total time complexity is O(TopF × MN2).
  • Step 5: Refine MSA by the consensus-based optimization: empirically, the length of the consensus structure is <2N, so it takes time O(MN) to build a consensus structure from a given MSA. The column merge procedure takes time O(MN) by using a 3D-hashing technique. It takes time O(N2) to align each structure to the consensus structure. At most 10 iterations are executed to refine the MSA, so the total time complexity is O(MN2).

The first two steps will be conducted for each of the TopK, resulting in a time complexity O(TopK × MN2). The last two steps will be conducted for each of the TopK and TopJ, leading to O(TopK × TopJ × TopF × MN2) time complexity. The overall time complexity is O(TopK × TopJ × TopF × MN2).


3.1 3DCOMB alignment accuracy

The programs to be compared: we compare 3DCOMB with BLOMAPS (Wang and Zheng, 2009), MAMMOTH (Lupyan et al., 2005), MAPSCI (Ilinkin et al., 2010), MATT (Menke et al., 2008), MultiProt (Shatsky et al., 2004) and MUSTANG (Konagurthu et al., 2006). Meanwhile, BLOMAPS, MultiProt and 3DCOMB are vertical-first algorithms while the other four are horizontal-first. We do not compare 3DCOMB with POSA because it has only a web server version and is not amendable to a large-scale test. 3DCOMB differs from BLOMAPS mainly in that 3DCOMB uses both local and global structure environments to identify HSFBs while BLOMAPS uses only local information. 3DCOMB also uses a better scoring function. 3DCOMB differs from MultiProt in both search algorithms and scoring functions.

The benchmarks: we use three benchmarks: HOMSTRAD (Mizuguchi et al., 1998), SABmark-sup and SABmark-twi (Van Walle et al., 2005). HOMSTRAD contains 398 homologous protein families, each with at least three structures. SABmark-sup is the superfamily set in SABmark (version 1.65), containing 425 families with low to intermediate sequence identity. SABmark-twi represents the twilight set in SABmark, containing 209 families with low sequence identity. We apply three metrics CORE-LEN, core RMSD and An external file that holds a picture, illustration, etc.
Object name is btr432i6.jpg to evaluating all the methods. The former two are also used by others such as MATT (Menke et al., 2008). We normalize CORE-LEN by the length of the shortest protein in a group and denote it as CORE-LEN%.

Performance on HOMSTRAD: 3DCOMB obtains the largest average CORE-LEN and the third best average core RMSD (slightly larger than MultiProt and MAPSCI). Note that because MultiProt uses a very strict cutoff to determine if an aligned column is a core or not, it always obtains the smallest core RMSD and also very small CORE-LEN on all the benchmarks. As shown in Table 1, MAMMOTH and MUSTANG can generate alignments with CORE-LEN comparable to 3DCOMB, Matt and BLOMAPS, but much larger RMSD. The average An external file that holds a picture, illustration, etc.
Object name is btr432i7.jpg achieved by 3DCOMB, BLOMAPS, MATT, MAMMOTH, MUSTANG, MAPSCI and MultiProt is 0.800, 0.779, 0.781, 0.786, 0.765, 0.792 and 0.649, respectively. 3DCOMB not only achieves the best average An external file that holds a picture, illustration, etc.
Object name is btr432i8.jpg, but also excels others on almost each individual structure group (Supplementary Fig. S2a).

Table 1.
Alignment accuracy of seven MSA tools on three benchmarks HOMSTRAD, SABmark-sup and SABmark-twi

Performance on SABmark-sup: 3DCOMB obtains the best average CORE-LEN and An external file that holds a picture, illustration, etc.
Object name is btr432i11.jpg. By core RMSD, 3DCOMB is second to only MultiProt, but MultiProt obtains a much smaller CORE-LEN. The average An external file that holds a picture, illustration, etc.
Object name is btr432i12.jpg achieved by 3DCOMB, BLOMAPS, MATT, MAMMOTH, MUSTANG, MAPSCI and MultiProt is 0.655, 0.613, 0.613, 0.614, 0.583, 0.627 and 0.404, respectively. By An external file that holds a picture, illustration, etc.
Object name is btr432i13.jpg, 3DCOMB is ~4.5% better than the second best method MAPSCI and also outperforms others on almost each individual structure group (Supplementary Fig. S2b).

Performance on SABmark-twi: SABmark-twi is more challenging because it consists of mostly distantly related proteins. However, 3DCOMB excels others at an even larger margin. By CORE-LEN, 3DCOMB is 6.6% better than the second best method BLOMAPS and excels others on a majority of structure groups. By core RMSD, 3DCOMB is second to MultiProit and slightly to Matt. The An external file that holds a picture, illustration, etc.
Object name is btr432i14.jpg obtained by 3DCOMB, BLOMAPS, MATT, MAMMOTH, MUSTANG, MAPSCI and MultiProt is 0.526, 0.457, 0.453, 0.436, 0.422, 0.466 and 0.259, respectively. By An external file that holds a picture, illustration, etc.
Object name is btr432i15.jpg, 3DCOMB outperforms the second best algorithm MAPSCI by 12.9% and also excels others on almost each individual structure group (Supplementary Fig. S2c).

Alignment accuracy versus core definition: different methods may use different distance cutoff values in determining if an aligned column is a core or not, so it is unfair to compare them simply in terms of CORE-LEN and core RMSD without specifying a uniform distance cutoff. To ensure a more fair comparison, we employ three cutoff values 4, 5 and 6 Å to determine if an aligned column is a core or not, respectively. That is, given a fully aligned column, we calculate all the pairwise distance of the aligned residues. If all the pairwise distances are within a given cutoff, this column is a core, otherwise not. As shown in Table 2, regardless of distance cutoffs, 3DCOMB consistently outperforms others in terms of CORE-LEN for distantly related proteins. In particular, 3DCOMB excels Matt in terms of both CORE-LEN and core RMSD. MAPSCI has similar performance as 3DCOMB on HOMSTRAD, but is much worse on the other two benchmarks.

Table 2.
Performance of seven MSA tools when three distance cutoff values 4.0, 5.0 and 6.0 Å are used to determine if an aligned column is a core or not

Performance on large structure groups: 3DCOMB builds MSAs from only those HSFBs. Does 3DCOMB suffer from using too few similar fragment blocks (and thus, too few initial MSAs) in aligning a large structure group (with >15 structures) consisting of distantly related proteins? We examined the performance of 3DCOMB on all the large groups in the three benchmarks and found out that 3DCOMB does not have such an issue. Measured by An external file that holds a picture, illustration, etc.
Object name is btr432i16.jpg, 3DCOMB excels others especially on the groups containing distantly related proteins. The advantage of 3DCOMB over others is even larger on the large structure groups than that on all the structure groups. See Supplementary Tables S10, S11 and S12 for detailed results.

3.2 How much room is left for further improvement?

Given a set of M structures, how good is a given MSA in terms of a specific quality metric (e.g. TMscore)? Can we estimate the difference between this MSA and the best possible even if we do not know how to generate the best? This problem is important because if we can answer it, we may know how much room is left for further improvement. If the difference is quite small, it does not make much sense to further search for a better MSA. Here we estimate the (upper bound) quality, measured by An external file that holds a picture, illustration, etc.
Object name is btr432i17.jpg, of the best possible MSA using the average TMscore of all the pairwise alignments. However, it is challenging not to underestimate the TMscore of a protein pair. To handle this, we employ several tools such as TMalign, DALI, MATT and MAMMOTH to generate pairwise alignments and then choose the highest TMscore.

Figure 2 shows the real An external file that holds a picture, illustration, etc.
Object name is btr432i20.jpg of the 3DCOMB alignments and their estimated An external file that holds a picture, illustration, etc.
Object name is btr432i21.jpg difference from the best possible. Overall, the estimated An external file that holds a picture, illustration, etc.
Object name is btr432i22.jpg difference decreases with respect to the similarity of input structures. That is, when the structures are quite similar, it is easier to generate an MSA consistent with all the pairwise alignments. Otherwise, it is much more challenging. When input structures are distantly related, an MSA consistent with all the pairwise alignments may not exist at all.

Fig. 2.
MSA upper bound analysis on three datasets (a) HOMSTRAD, (b) SABmark-sup and (c) SABmark-twi. The X-axis is An external file that holds a picture, illustration, etc.
Object name is btr432i18.jpg of the MSAs generated by 3DCOMB and the Y-axis is the estimated An external file that holds a picture, illustration, etc.
Object name is btr432i19.jpg difference between the 3DCOMB alignments and the best possible.

3.3 Specific examples

We have visually examined many structure groups in the three benchmarks and found out 3DCOMB generates significantly better alignments for many groups than others. It is very challenging to visualize the alignments, though. Here, we show three groups for which 3DCOMB generates correct alignments in functionally similar regions while others (especially the horizontal-first methods) fail. See the upplementary Material for more results and case studies.

SABmark-sup group 323 contains three Glutamine synthetase/guanido kinase proteins: d1f52a2 [SCOP (Murzin et al., 1995) ID d.128.1.1, 368 AAs], d1m15a2 (d.128.1.2, 262 AAs) and d1qh4a2 (d.128.1.2, 279 AAs). PDB (Berman et al., 2002) shows that 1f52 (Glutamine synthetase) and 1m15 (arginine kinase) bind to ADP. The three proteins share a common core consisting of two beta-alpha-beta2-alpha repeats and the six-beta sheets form an unsealed pocket where ATP/ADP binds. That is, the common core is the active site of the synthetase/kinase.

By the 3DCOMB alignment (Fig. 3a1), we may infer that the aligned unsealed pocket in 1qh4 possibly is its active site. This is confirmed by the prediction result from ConCavity (Capra et al., 2009) in Figure 3a2, which predicts binding sites without using structure alignment. Two other vertical-first methods BLOMAPS and MultiProt generate reasonable but worse alignments than 3DCOMB (Supplementary Fig. S9). All the horizontal-first methods (MATT, MAPSCI, MUSTANG and MAMMOTH) generate incorrect alignment for 1f52a2 and the binding sites. This example demonstrates the vertical-first methods are better than horizontal-first methods in discovering conserved regions among proteins which are not very similar and also of very different sizes.

Fig. 3.
The pictures in (a1), (b1) and (c1) show the 3DCOMB alignments of SABmark-sup 323, SABmark-twi 124 and SABmark-twi 118, respectively. Proteins are displayed in different colors. The full-core positions (where all proteins are aligned) are displayed in ...

SABmark-twi group 124 contains six Lysozyme-like proteins: d153l_ (SCOP ID d.2.1.5, 185 AAs), d1dxja_ (d.2.1.1, 242 AAs), d1lw9a_ (d.2.1.3, 164 AAs), d1qgia_ (d.2.1.7, 259 AAs), d1qsaa2 (d.2.1.6, 168 AAs) and d3lzt_ (d.2.1.2, 129 AAs). Meanwhile, 153l, 3lzt and 1dxj are goose lysozyme, hen egg-white lysozyme and jack bean chitinase, respectively. Proteins 1lw9 and 1qgi are T4 lysozyme and chitosanase from Bacillus circulans. d1qsaa2 is Lytic Transglycosylase Slt70 from Escherichia coli, resembling goose-type lysozyme (van Asselt et al., 1999). These proteins represent a superfamily of hydrolases arising from the divergent evolution of an ancient protein (Robertus et al., 1998).

By SCOP, these proteins have ‘alpha + beta motif for the active site region’. Although their sequence similarity is low, they have a conserved core containing two helices and a three-stranded sheet, which form the substrate binding and catalytic cleft (Monzingo et al., 1996). Their active binding sites lie in the cleft between the upper and lower domains. Their two catalytic centers are located at the upper domain, one in front of the three-stranded sheet and the other in the N-terminal helix (Saito et al., 1999).

As shown in Figure 3b1, 3DCOMB correctly aligns the functional sites described in Monzingo et al. (1996) (i.e. three-sheet plus two-helix in the upper domain). As shown in Figure 3b2, all the binding sites with predicted by ConCavity with high confidence are well aligned. 3DCOMB even correctly aligns the shortest protein 3lzt and the longest protein 1qgi, which are conserved only in the functional sites. 3DCOMB also indicates that there are several conserved helixes in the lower domain. As shown in Supplementary Figure S6, only 3DCOMB and BLOMAPS generate correct alignments for the functional sites while all the horizontal-first methods fail. This confirms the strength of vertical-first methods. However, another vertical-first method MultiProt fails to produce a correct alignment, maybe because MultiPort cannot identify good similar fragment blocks to build initial MSAs.

SABmark-twi group 118 contains six chelatase-like proteins: d1doza_ (SCOP ID c.92.1.1, 309 AAs), d1m1na_ (c.92.2.3, 477 AAs), d1m1nb_ (c.92.2.3, 522 AAs), d1n2za_ (c.92.2.2, 245 AAs), d1qgoa_ (c.92.1.2, 257 AAs) and d1toaa_ (c.92.2.2, 277 AAs). Meanwhile, d1doza_, d1qgoa_, d1n2za_ and d1toaa are ferrochelatase, cobalt chelatase, vitamin B12 binding protein and Zn2+ binding protein, respectively, and d1m1na_ and d1m1nb_ are the molybdenum iron (MoFe) protein of nitrogenase. It is very challenging to align these proteins since they are similar only at fold level and also of very different sizes. Even SCOP and CATH are inconsistent on them. CATH splits d1doza_, d1n2za_, d1qgoa_ and d1toaa_ into two domains, d1m1na_ into 3 and d1m1nb_ into 4 while SCOP treats all of them as single domain proteins.

These proteins have different (non-conserved) binding ligands, but the locations of the binding pockets and the domains surrounding the pockets are conserved. In particular, d1doza_, d1qgoa_, d1n2za_ and d1toaa_ have two structurally similar lobes (the synonym for ‘domain’, may refer to a smaller substructure unit), each being a Rossmann-like fold (Al-Karadaghi et al., 1997). These two lobes interact with each other in a head-to-head manner (Lee et al., 1999) and the active sites of these four proteins lie in a deep cleft between the two lobes (Schubert et al., 1999). d1n2za_ and d1toaa_have a single long helix linking the two lobes, d1doza_ and d1qgoa do not. This unique helix is possibly adopted to limit the hinge motion associated with ligand exchange (Lee et al., 1999). d1m1na_ (d1m1nb_ ) has three lobes (Borths et al., 2002) and its αII (βII) and αIII (βIII) lobes are similar to those in d1n2za_ and d1toaa and also linked by a helix. Similar to others, the binding ligand of d1m1na_ is located at the interface between the αII and αIII lobes (Kim and Rees, 1992).

3DCOMB alignment is consistent with the above structural description and ConCavity prediction, as shown in Figure 3c1 and c2. Only 3DCOMB generates a correct alignment for this group while all the other methods fail (Supplementary Fig. S5). This result confirms that 3DCOMB not only has a good search algorithm, but also a good scoring function (since the other two vertical-first methods BLOMAPS and MultiProt also fail).

Comparison with a binding site alignment program MultiBind (Shulman-Peleg et al., 2008): MultiBind needs to know binding site positions in order to generate alignments while 3DCOMB does not. MultiBind also runs very slowly and generates many alternative alignments. Many proteins in these examples have no binding site information in PDB. In order to run MultiBind, we assign binding sites to them based upon 3DCOMB alignments and ConCavity predictions. Even so, for these examples MultiBind cannot generate correct alignments at functionally similar regions.

3.4 Implications to homology modeling

Multiple template modeling has been used to enhance homology modeling (Cheng, 2008; Joo et al., 2007; Peng and Xu, 2011). An interesting question to ask is how much improvement room is left for this method in terms of alignment accuracy? To answer this, we conduct an experiment using 47 CASP9 (the 9th Critical Assessment of Structure Prediction) test targets, all of them have at least two good templates. See Supplementary Material for a list of the targets and templates. We use seven MSA tools to build an MSA for a target and its templates, assuming that the native structures of the target and templates are known. We also used RaptorX (Peng and Xu, 2011), one of the best threading programs, to generate an alignment between the target and its templates, without using the native structure for the target. All the alignments are fed into MODELLER to generate 3D models for the targets. As shown in Supplementary Figure S11 and Table S14, the 3DCOMB models excel the RaptorX models. That is, there may be still improvement room for multiple template modeling. However, the 3D models derived from other MSA tools are not better than the RaptorX models. This shows that in order to identify the limitation of multiple template modeling, a good MSA tool is critical. Otherwise we may reach very different or even opposite conclusions.

3.5 3DCOMB running time analysis

We tested 3DCOMB on an Ubuntu Linux PC with 2 GB RAM and Intel®Core2 Quad CPU T5600 @1.83 GHz. The input structures are sorted according to the length in ascending order. We use the TopK = All, TopJ = 1, TopF = 5 as our default parameters to run 3DCOMB on SABmark-twi. 3DCOMB, MATT and MUSTANG have running times of 43 706, 45 328 and 50 728 s, respectively. 3DCOMB yields better accuracy than MATT and MUSTANG. It takes MultiProt and MAMMOTH 39 642 and 1279 s, respectively, to run this benchmark, but they have much worse alignment accuracy than 3DCOMB and MATT. BLOMAPS and MAPSCI are very fast, taking only 780 and 240 s. The performance of 3DCOMB depends on three parameters TopK, TopJ and TopF, which can be further set smaller to reduce running time without losing much alignment accuracy. Supplementary Table S13 shows the 3DCOMB running time and accuracy on SABmark-twi with respect to different parameter s.


This article presents a novel method 3DCOMB for MSA. By using a probabilistic model to combine both local and global structure information, we can accurately identify the most conserved short fragment blocks among proteins to be aligned. These conserved fragment blocks are very likely contained in the best MSA, so 3DCOMB can quickly extend them to the best MSA. This article also introduces a novel scoring function to generate an MSA with a large number of cores and also high-quality pairwise alignments.

We have compared 3DCOMB with BLOMAPS, MAMMOTH, MAPSCI, MATT, MultiProt and MUSTANG on the popular benchmarks. Both the MSAs and the pairwise alignments generated by 3DCOMB are of high quality. In particular, 3DCOMB shows significant advantages over others in aligning a large set of distantly related proteins and their functionally similar regions. 3DCOMB also has a very reasonable running time and can scale well up to a large structure group.

Currently, 3DCOMB uses only geometrical information. We may improve 3DCOMB by including sequence information and the physical–chemical properties of amino acids. Sequence similarity measure can be used to explicitly model evolutionary relationship. Other geometrical information such as Voronoi tessellations (Birzele et al., 2007) and Conformational Letter (CLE) (Zheng, 2008a; Zheng, 2008b; Zheng and Liu, 2005) can also be used to further improve HSFB identification.

3DCOMB will be useful for many real-world applications and sometimes can produce results dramatically different from other tools. For example, 3DCOMB indicates that there may be still large improvement room for multiple template modeling while other MSA tools fail to do so. Coupled with tools like ConCavity (Capra et al., 2009), 3DCOMB can be potentially used for binding site prediction.

Funding: National Institutes of Health (grant R01GM089753 to J.X.); National Science Foundation (grant DBI-0960390 to J.X).

Conflict of Interest: none declared.

Supplementary Material

Supplementary Data:


  • Al-Karadaghi S., et al. Crystal structure of ferrochelatase: the terminal enzyme in heme biosynthesis. Structure. 1997;5:1501–1510. [PubMed]
  • Berman H., et al. The protein data bank. Acta Crystallogr. D Biol. Crystallogr. 2002;58:899–907. [PubMed]
  • Birzele F., et al. Vorolign–fast structural alignment using Voronoi contacts. Bioinformatics. 2007;23:e205–e211. [PubMed]
  • Borths E.L., et al. The structure of Escherichia coli BtuF and binding to its cognate ATP binding cassette transporter. Proc. Natl Acad. Sci. USA. 2002;99:16642. [PubMed]
  • Capra J.A., et al. Predicting protein ligand binding sites by combining evolutionary sequence conservation and 3D structure. PLoS Comput. Biol. 2009;5:e1000585. [PMC free article] [PubMed]
  • Cheng J. A multi-template combination algorithm for protein comparative modeling. BMC Struct. Biol. 2008;8:18. [PMC free article] [PubMed]
  • da Silveira C., et al. Protein cutoff scanning: A comparative analysis of cutoff dependent and cutoff free methods for prospecting contacts in proteins. Proteins Struct. Funct. Bioinformatics. 2009;74:727–743. [PubMed]
  • Do C., et al. RECOMB/Lecture Notes in Computer Science. Vol. 3909. Venice, Italy: Springer; 2006. CONTRAlign: discriminative training for protein sequence alignment; pp. 160–174.
  • Eswar N., et al. Protein structure modeling with MODELLER. Methods Mol. Biol. 2008;426:145. [PubMed]
  • Holm L., Sander C. Protein structure comparison by alignment of distance matrices. J. Mol. Biol. 1993;233:123–128. [PubMed]
  • Holm L., Sander C. The FSSP database of structurally aligned protein fold families. Nucleic Acids Res. 1994;22:3600–3609. [PMC free article] [PubMed]
  • Ilinkin I., et al. Multiple structure alignment and consensus identification for proteins. BMC Bioinformatics. 2010;11:71. [PMC free article] [PubMed]
  • Joo K., et al. High accuracy template based modeling by global optimization. Proteins. 2007;69(Suppl. 8):83–89. [PubMed]
  • Kabsch W. A solution for the best rotation to relate two sets of vectors. Acta Crystallogr. A. 1976;32:922–923.
  • Kim J., Rees D. Structural models for the metal centers in the nitrogenase molybdenum-iron protein. Science. 1992;257:1677. [PubMed]
  • Konagurthu A.S., et al. MUSTANG: a multiple structural alignment algorithm. Proteins. 2006;64:559–574. [PubMed]
  • Lafferty J., et al. Conditional random fields: probabilistic models for segmenting and labeling sequence data. Citeseer. 2001:282–289.
  • Lee Y.H., et al. Treponema pallidum TroA is a periplasmic zinc-binding protein with a helical backbone. Nat. Struct. Mol. Biol. 1999;6:628–633. [PubMed]
  • Levitt M., Gerstein M. A unified statistical framework for sequence comparison and structure comparison. Proc. Natl Acad. Sci. USA. 1998;95:5913–5920. [PubMed]
  • Lupyan D., et al. A new progressive-iterative algorithm for multiple structure alignment. Bioinformatics. 2005;21:3255–3263. [PubMed]
  • Madhusudhan M.S., et al. Alignment of multiple protein structures based on sequence and structure features. Protein Eng. Des. Sel. 2009;22:569–574. [PMC free article] [PubMed]
  • Menke M., et al. Matt: local flexibility aids protein multiple structure alignment. PLoS Comput. Biol. 2008;4:e10. [PubMed]
  • Mizuguchi K., et al. HOMSTRAD: a database of protein structure alignments for homologous families. Protein Sci. 1998;7:2469–2471. [PubMed]
  • Monzingo A.F., et al. Chitinases, chitosanases, and lysozymes can be divided into procaryotic and eucaryotic families sharing a conserved core. Nat. Struct. Biol. 1996;3:133–140. [PubMed]
  • Murzin A., et al. SCOP: a structural classification of proteins database for the investigation of sequences and structures. J. Mol. Biol. 1995;247:536–540. [PubMed]
  • Peng J., Xu J. RECOMB/Lecture Notes in Computer Science. Vol. 5541. Tucson, AZ: Springer; 2009. Boosting protein threading accuracy; pp. 31–45. [PMC free article] [PubMed]
  • Peng J., Xu J. Low-homology protein threading. Bioinformatics. 2010;26:i294. [PMC free article] [PubMed]
  • Peng J., Xu J. A multiple template approach to protein threading. Proteins. 2011;79:1930–1959. [PMC free article] [PubMed]
  • Robertus J.D., et al. Structural analysis shows five glycohydrolase families diverged from a common ancestor. J. Exp. Zool. 1998;282:127–132. [PubMed]
  • Saito J., et al. Crystal structure of chitosanase from Bacillus circulans MH-K1 at 1.6-Å resolution and its substrate recognition mechanism. J. Biol. Chem. 1999;274:30818. [PubMed]
  • Schubert H.L., et al. Common chelatase design in the branched tetrapyrrole pathways of heme and anaerobic cobalamin synthesis. Biochemistry. 1999;38:10660–10669. [PubMed]
  • Shatsky M., et al. A method for simultaneous alignment of multiple protein structures. Proteins. 2004;56:143–156. [PubMed]
  • Shulman-Peleg A., et al. MultiBind and MAPPIS: webservers for multiple alignment of protein 3D-binding sites and their interactions. Nucleic Acids Res. 2008;36:W260. [PMC free article] [PubMed]
  • Siew N., et al. MaxSub: an automated measure for the assessment of protein structure prediction quality. Bioinformatics. 2000;16:776–785. [PubMed]
  • van Asselt E.J., et al. High resolution crystal structures of the Escherichia coli lytic transglycosylase slt70 and its complex with a peptidoglycan fragment1. J. Mol. Biol. 1999;291:877–898. [PubMed]
  • Van Walle I., et al. SABmark–a benchmark for sequence alignment that covers the entire known fold space. Bioinformatics. 2005;21:1267–1268. [PubMed]
  • Wang S., Zheng W.M. CLePAPS: fast pair alignment of protein structures based on conformational letters. J. Bioinform. Comput. Biol. 2008;6:347–366. [PubMed]
  • Wang S., Zheng W. Fast multiple alignment of protein structures using conformational letter blocks. Open Bioinformatics J. 2009;3:69–83.
  • Wang Z., et al. Protein 8-class secondary structure prediction using conditional neural fields. BIBM 2010. 2010 [PMC free article] [PubMed]
  • Xu J., Zhang Y. How significant is a protein structure similarity with TM-score = 0.5? Bioinformatics. 2010;26:889–895. [PMC free article] [PubMed]
  • Ye Y., Godzik A. Multiple flexible structure alignment using partial order graphs. Bioinformatics. 2005;21:2362. [PubMed]
  • Zhang Y., Skolnick J. Scoring function for automated assessment of protein structure template quality. Proteins. 2004;57:702–710. [PubMed]
  • Zhao F., et al. A probabilistic and continuous model of protein conformational space for template-free modeling. J. Comput. Biol. 2010a;17:783–798. [PMC free article] [PubMed]
  • Zhao F., et al. Fragment-free approach to protein folding using conditional neural fields. Bioinformatics. 2010b;26:i310. [PMC free article] [PubMed]
  • Zheng W. Protein conformational alphabets. In: Roswell L.B., editor. Protein Conformations: New Research. New York: Nova Science Publishers; 2008a. pp. 1–49.
  • Zheng W. The use of a conformational alphabet for fast alignment of protein structures. Bioinformatics Res. Appl. 2008b:331–342.
  • Zheng W., Liu X. Transactions on Computational Systems Biology II. Berlin: Springer; 2005. A Protein Structural Alphabet and its Substitution Matrix CLESUM.

Articles from Bioinformatics are provided here courtesy of Oxford University Press