Structural alignment

Structural alignment is a form of sequence alignment based on comparison of shape. These alignments attempt to establish equivalences between two or more polymer structures based on their shape and three-dimensional conformation. This process is usually applied to protein tertiary structures but can also be used for large RNA molecules. In contrast to simple structural superposition, where at least some equivalent residues of the two structures are known, structural alignment requires no "a priori" knowledge of equivalent positions. Structural alignment is a valuable tool for the comparison of proteins with low sequence similarity, where evolutionary relationships between proteins cannot be easily detected by standard sequence alignment techniques. Structural alignment can therefore be used to imply evolutionary relationships between proteins that share very little common sequence. However, caution should be used in using the results as evidence for shared evolutionary ancestry because of the possible confounding effects of convergent evolution by which multiple unrelated amino acid sequences converge on a common tertiary structure.

Structural alignments can compare two sequences or multiple sequences. Because these alignments rely on information about all the query sequences' three-dimensional conformations, the method can only be used on sequences where these structures are known. These are usually found by X-ray crystallography or NMR spectroscopy. It is possible to perform a structural alignment on structures produced by structure prediction methods. Indeed, evaluating such predictions often requires a structural alignment between the model and the true known structure to assess the model's quality. Structural alignments are especially useful in analyzing data from structural genomics and proteomics efforts, and they can be used as comparison points to evaluate alignments produced by purely sequence-based bioinformatics methods.Zhang Y, Skolnick J. (2005). The protein structure prediction problem could be solved using the current PDB library. Proc Natl Acad Sci USA 102(4):1029-34.]

The outputs of a structural alignment are a superposition of the atomic coordinate sets and a minimal root mean square distance (RMSD) between the structures. The RMSD of two aligned structures indicates their divergence from one another. Structural alignment can be complicated by the existence of multiple protein domains within one or more of the input structures, because changes in relative orientation of the domains between two structures to be aligned can artificially inflate the RMSD.

Data produced by structural alignment

The minimum information produced from a successful structural alignment is a set of superposed three-dimensional coordinates for each input structure. (Note that one input element may be fixed as a reference and therefore its superposed coordinates do not change.) The fitted structures can be used to calculate mutual RMSD values, as well as other more sophisticated measures of structural similarity such as the global distance test (GDTZemla A. (2003). LGA - A Method for Finding 3-D Similarities in Protein Structures. "Nucleic Acids Research", 31(13):3370-3374.] , the metric used in CASP). The structural alignment also implies a corresponding one-dimensional sequence alignment from which a sequence identity, or the percentage of residues that are identical between the input structures, can be calculated as a measure of how closely the two sequences are related.

Types of comparisons

Because protein structures are composed of amino acids whose side chains are linked by a common protein backbone, a number of different possible subsets of the atoms that make up a protein macromolecule can be used in producing a structural alignment and calculating the corresponding RMSD values. When aligning structures with very different sequences, the side chain atoms generally are not taken into account because their identities differ between many aligned residues. For this reason it is common for structural alignment methods to use by default only the backbone atoms included in the peptide bond. For simplicity and efficiency, often only the alpha carbon positions are considered, since the peptide bond has a minimally variant planar conformation. Only when the structures to be aligned are highly similar or even identical is it meaningful to align side-chain atom positions, in which case the RMSD reflects not only the conformation of the protein backbone but also the rotameric states of the side chains. Other comparison criteria that reduce noise and bolster positive matches include secondary structure assignment, native contact maps or residue interaction patterns, measures of side chain packing, and measures of hydrogen bond retention.Godzik A. (1996). The structural alignment of proteins: is there a unique answer? "Protein Sci" 5:1325-8.]

tructural superposition

The most basic possible comparison between protein structures makes no attempt to align the input structures and requires a precalculated alignment as input to determine which of the residues in the sequence are intended to be considered in the RMSD calculation. Structural superposition is commonly used to compare multiple conformations of the same protein (in which case no alignment is necessary, since the sequences are the same) and to evaluate the quality of alignments produced using only sequence information between two or more sequences whose structures are known. This method traditionally uses a simple least-squares fitting algorithm, in which the optimal rotations and translations are found by minimizing the sum of the squared distances among all structures in the superposition. Martin ACR. http://www.bioinf.org.uk/software/profit/doc/ The software package [http://www.bioinf.org.uk/software/profit/ ProFit] (implements McLachlan, AD (1982). Rapid Comparison of Protein Structures. "Acta Cryst" A38, 871-873.)] More recently, maximum likelihood and Bayesian methods have greatly increased the accuracy of the estimated rotations, translations, and covariance matrices for the superposition Theobald DL, Wuttke DS (2006). Empirical Bayes hierarchical models for regularizing maximum likelihood estimation in the matrix Gaussian Procrustes problem. "Proceedings of the National Academy of Sciences" 103(49):18521-18527. [http://www.pnas.org/cgi/content/full/103/49/18521 Open Access] ] Theobald DL, Wuttke DS (2006). THESEUS: Maximum likelihood superpositioning and analysis of macromolecular structures. "Bioinformatics" 22(17):2171-2172. [http://bioinformatics.oxfordjournals.org/cgi/reprint/btl332?ijkey=BrYm4QyQZzMzu8s&keytype=ref Open Access] http://www.theseus3d.org/ ] .

Algorithms based on multidimensional rotations and modified quaternions have been developed to identify topological relationships between protein structures without the need for a predetermined alignment. Such algorithms have successfully identified canonical folds such as the four-helix bundle.Diederichs K. (1995). Structural superposition of proteins with unknown alignment and detection of topological similarity using a six-dimensional search algorithm. "Proteins" 23(2):187-95.] The [http://wishart.biology.ualberta.ca/SuperPose/ SuperPose] method is sufficiently extensible to correct for relative domain rotations and other structural pitfalls.Maiti R, Van Domselaar GH, Zhang H, Wishart DS. (2004). SuperPose: a simple server for sophisticated structural superposition. "Nucleic Acids Res" 32(Web Server issue):W590-4.]

Algorithmic complexity

Both the optimal "threading" of a protein sequence onto a known structureLathrop RH. (1994). The protein threading problem with sequence amino acid interaction preferences is NP-complete. "Protein Eng" 7(9):1059-68.] and the production of an optimal multiple sequence alignmentWang L, Jiang T. (1994) On the complexity of multiple sequence alignment. "J Comput Biol" 1:337-348.] have been shown to be NP-complete. However, this does not imply that the structural alignment problem is NP-complete. On the basis of the argument that a true optimal solution is not biologically meaningful due to the experimental error inherent in protein structure determination, an approximate polynomial-time algorithm for structural alignment that produces a family of "optimal" solutions within an approximation parameter for a given scoring function has been developed.Kolodny R, Linial N. (2004). Approximate protein structural alignment in polynomial time "PNAS" 101(33): 12201-12206.] However, at $O(n^\{10\}/epsilon^6)$ for a globular protein of "n" residues, the algorithm is still too computationally expensive for practical use. As a consequence, practical algorithms that converge to the global solutions of the alignment, given a scoring function, do not exist. Most algorithms are, therefore, heuristic, but algorithms that guarantee the convergence to at least local maximizers of the scoring functions, and are practical, have been developed.Martinez L, Andreani, R, Martinez, JM. (2007). Convergent algorithms for protein structural alignment "BMC Bioinformatics" 8:306.]

Representation of structures

Protein structures have to be represented in some coordinate-independent space to make them comparable. This is typically achieved by constructing a sequence-to-sequence matrix or series of matrices that encompass comparative metrics: rather than absolute distances relative to a fixed coordinate space. An intuitive representation is the distance matrix, which is a two-dimensional matrix containing all pairwise distances between some subset of the atoms in each structure (such as the alpha carbons). The matrix increases in dimensionality as the number of structures to be simultaneously aligned increases. Reducing the protein to a coarse metric such as secondary structure elements (SSEs) or structural fragments can also produce sensible alignments, despite the loss of information from discarding distances, as noise is also discarded.Mount DM. (2004). "Bioinformatics: Sequence and Genome Analysis" 2nd ed. Cold Spring Harbor Laboratory Press: Cold Spring Harbor, NY.] Choosing a representation to facilitate computation is critical to developing an efficient alignment mechanism.

Methods

Structural alignment techniques have been used in comparing individual structures or sets of structures as well as in the production of "all-to-all" comparison databases that measure the divergence between every pair of structures present in the Protein Data Bank (PDB). Such databases are used to classify proteins by their fold.

DALI

A common and popular structural alignment method is the DALI, or distance alignment matrix method, which breaks the input structures into hexapeptide fragments and calculates a distance matrix by evaluating the contact patterns between successive fragments.Holm L, Sander C (1996). Mapping the protein universe. "Science" 273: 595-603.] Secondary structure features that involve residues that are contiguous in sequence appear on the matrix's main diagonal; other diagonals in the matrix reflect spatial contacts between residues that are not near each other in the sequence. When these diagonals are parallel to the main diagonal, the features they represent are parallel; when they are perpendicular, their features are antiparallel. This representation is memory-intensive because the features in the square matrix are symmetrical (and thus redundant) about the main diagonal.

When two proteins' distance matrices share the same or similar features in approximately the same positions, they can be said to have similar folds with similar-length loops connecting their secondary structure elements. DALI's actual alignment process requires a similarity search after the two proteins' distance matrices are built; this is normally conducted via a series of overlapping submatrices of size 6x6. Submatrix matches are then reassembled into a final alignment via a standard score-maximization algorithm - the original version of DALI used a Monte Carlo simulation to maximize a structural similarity score that is a function of the distances between putative corresponding atoms. In particular, more distant atoms within corresponding features are exponentially downweighted to reduce the effects of noise introduced by loop mobility, helix torsions, and other minor structural variations. Because DALI relies on an all-to-all distance matrix, it can account for the possibility that structurally aligned features might appear in different orders within the two sequences being compared.

The DALI method has also been used to construct a database known as FSSP (Fold classification based on Structure-Structure alignment of Proteins, or Families of Structurally Similar Proteins) in which all known protein structures are aligned with each other to determine their structural neighbors and fold classification. There is an EBI-maintained [http://www.ebi.ac.uk/dali/ searchable database] based on DALI as well as a [http://ekhidna.biocenter.helsinki.fi/dali_lite/downloads/download.html downloadable program] and [http://ekhidna.biocenter.helsinki.fi/dali/start web search] based on a standalone version known as DaliLite.

AP

The SSAP (Sequential Structure Alignment Program) method uses double dynamic programming to produce a structural alignment based on atom-to-atom vectors in structure space. Instead of the alpha carbons typically used in structural alignment, SSAP constructs its vectors from the beta carbons for all residues except glycine, a method which thus takes into account the rotameric state of each residue as well as its location along the backbone. SSAP works by first constructing a series of inter-residue distance vectors between each residue and its nearest non-contiguous neighbors on each protein. A series of matrices are then constructed containing the vector differences between neighbors for each pair of residues for which vectors were constructed. Dynamic programming applied to each resulting matrix determines a series of optimal local alignments which are then summed into a "summary" matrix to which dynamic programming is applied again to determine the overall structural alignment.

SSAP originally produced only pairwise alignments but has since been extended to multiple alignments as well.Taylor WR, Flores TP, Orengo CA. (1994). Multiple protein structure alignment. "Protein Sci" 3(10):1858-70.] It has been applied in an all-to-all fashion to produce a hierarchical fold classification scheme known as CATH (Class, Architecture, Topology, Homology),Orengo CA, Michie AD, Jones S, Jones DT, Swindells MB, Thornton JM. (1997) CATH: A hierarchical classification of protein domain structures. "Structure" 5(8): 1093-1108.] which has been used to construct the [http://www.cathdb.info/latest/index.html CATH Protein Structure Classification] database.

Combinatorial extension

The combinatorial extension (CE) method is similar to DALI in that it too breaks each structure in the query set into a series of fragments that it then attempts to reassemble into a complete alignment. A series of pairwise combinations of fragments called aligned fragment pairs, or AFPs, are used to define a similarity matrix through which an optimal path is generated to identify the final alignment. Only AFPs that meet given criteria for local similarity are included in the matrix as a means of reducing the necessary search space and thereby increasing efficiency.Shindyalov IN, Bourne PE (1998) Protein structure alignment by incremental combinatorial extension (CE) of the optimal path. "Protein Eng" 11(9) 739-747.] A number of similarity metrics are possible; the original definition of the CE method included only structural superpositions and inter-residue distances but has since been expanded to include local environmental properties such as secondary structure, solvent exposure, hydrogen-bonding patterns, and dihedral angles.

An alignment path is calculated as the optimal path through the similarity matrix by linearly progressing through the sequences and extending the alignment with the next possible high-scoring AFP pair. The initial AFP pair that nucleates the alignment can occur at any point in the sequence matrix. Extensions then proceed with the next AFP that meets given distance criteria restricting the alignment to low gap sizes. The size of each AFP and the maximum gap size are required input parameters but are usually set to empirically determined values of 8 and 30 respectively. Like DALI and SSAP, CE has been used to construct an all-to-all fold classification [http://cl.sdsc.edu/ database] from the known protein structures in the PDB.

MAMMOTH

MAtching Molecular Models Obtained from Theory. MAMMOTH-based structure alignment methods decomposes the protein structure into short peptides (heptapeptides) which are compared with the heptapeptides of another protein. Similarity score between two heptapeptides is calculated using a unit-vector RMS (URMS) method. Kedem, K., Chew, L., and Elber, R. 1999. Unit-vector RMS (URMS) as a tool to analyze molecular dynamics trajectories. Proteins 37: 554–564 ] These scores are stored in a similarity matrix, and with a hybrid (local-global) dynamic programming the optimal residue alignment is calculated. Protein similarity scores calculated with MAMMOTH is derived from the likelihood of obtaining a given structural alignment by chance. Ortiz, A. R., C. E. Strauss, and O. Olmea (2002, November). Mammoth (matching molecular models obtained from theory): An automated method for model comparison. Protein Sci 11 (11), 2606-2621.] This method has been optimized for speed and accuracy, and is suited for large-scale structural genomics studies. MAMMOTH is used by Rosetta@home.

MAMMOTH-mult is an extension of the MAMMOTH algorithm to be used to align related family of protein structures. This algorithm is very fast and produces consistent and high quality structural alignments. Lupyan, D., A. Leo-Macias, and A. R. Ortiz (2005, August). A new progressive-iterative algorithm for multiple structure alignment. Bioinformatics 21 (15), 3255-3263.] Multiple structural alignments calculated with MAMMOTH-mult produces structurally-implied sequence alignments that can be further used for multiple-template homology modeling, HMM-based protein structure prediction, and profile-type PSI-BLAST searches.

RAPIDO

Rapid Alignment of Proteins In terms of DOmains. RAPIDO Mosca, Schneider TR. (2008) RAPIDO: a web server for the alignment of protein structures in the presence of conformational changes, Nucleic Acids Research, doi: 10.1093/nar/gkn197 [http://nar.oxfordjournals.org/cgi/content/abstract/gkn197?ijkey=xfzxsZlvgO3xFZz&keytype=ref Open Access] [http://webapps.embl-hamburg.de/rapido RAPIDO server] ] is a web server for the 3D alignment of crystal structures of different protein molecules, in the presence of conformational changes. Similar to what CE does as a first step, RAPIDO identifies fragments that are structurally similar in the two proteins using an approach based on difference distance matrices. The Matching Fragment Pairs (MFPs) are then represented as nodes in a graph which are chained together to form an alignment by means of an algorithm for the identification of the longest path on a DAG (Directed Acyclic Graph). The final step of refinement is performed to improve the quality of the alignment. After aligning the two structures the server applies a genetic algorithm for the identification of conformationally invariant regions Schneider. (2002) A genetic algorithm for the identification of conformationally invariant regions in protein molecules. Acta Crystallogr D Biol Crystallogr vol. 58 (Pt 2) pp. 195-208] . These regions correspond to groups of atoms whose interatomic distances are constant (within a defined tolerance). In doing so RAPIDO takes into account the variation in the reliability of atomic coordinates by employing weighting-functions based on the refined B-values. The regions identified as conformationally invariant by RAPIDO represent reliable sets of atoms for the superposition of the two structures that can be used for a detailed analysis of changes in the conformation. In addition to the functionalities provided by existing tools, RAPIDO can identify structurally equivalent regions even when these consist of fragments that are distant in terms of sequence and separated by other movable domains.

Recent developments

Improvements in structural alignment methods constitute an active area of research, and new or modified methods are often proposed that are claimed to offer advantages over the older and more widely distributed techniques. A recent example, TM-align, uses a novel method for weighting its distance matrix, to which standard dynamic programming is then applied.Zhang Y, Skolnick J. (2005) TM-align: A protein structure alignment algorithm based on TM-score. "Nucleic Acids Research" 33: 2302-2309.] Zhang Y, Skolnick J. (2004) Scoring function for automated assessment of protein structure template quality. "Proteins" 57: 702-710.] The weighting is proposed to accelerate the convergence of dynamic programming and correct for effects arising from alignment lengths. In a benchmarking study, TM-align has been reported to improve in both speed and accuracy over DALI and CE.

Beneath common sequential structure alignment tools, also non-sequential approaches have been developed in the recent time. Some examples are GANGSTA+ Guerler A, Knapp E.W. (2008) Novel protein folds and their nonsequential structural analogs. "Protein Science" 17.] and TopoFit Valentin A. Ilyin, Alexej Abyzov, and Chesley M.Leslin, Structural alignment of proteins by a novel TOPOFIT method, as a superimposition of common volumes at a topomax point. (preprint) Protein Science (2004), 13:1865-1874] . The three dimensional alignment results (sequential and non-sequential) of an all-against-all protein database calculation is available for browsing at http://gangsta.chemie.fu-berlin.de.

RNA structural alignment

Structural alignment techniques have traditionally been applied exclusively to proteins, as the primary biological macromolecules that assume characteristic three-dimensional structures. However, large RNA molecules also form characteristic tertiary structures, which are mediated primarily by hydrogen bonds formed between base pairs as well as base stacking. Functionally similar noncoding RNA molecules can be especially difficult to extract from genomics data because structure is more strongly conserved than sequence in RNA as well as in proteins,Torarinsson E, Sawera M, Havgaard JH, Fredholm M, Gorodkin J. (2006). Torarinsson E, Sawera M, Havgaard JH, Fredholm M, Gorodkin J. "Genome Res" 16(7):885-9.] and the more limited alphabet of RNA decreases the information content of any given nucleotide at any given position.

A recent method for pairwise structural alignment of RNA sequences with low sequence identity has been published and implemented in the program [http://foldalign.kvl.dk/ FOLDALIGN] .Havgaard JH, Lyngso RB, Stormo GD, Gorodkin J. (2005). Pairwise local structural alignment of RNA sequences with sequence similarity less than 40%. "Bioinformatics" 21(9):1815-24.] However, this method is not truly analogous to protein structural alignment techniques because it computationally predicts the structures of the RNA input sequences rather than requiring experimentally determined structures as input. Although computational prediction of the protein folding process has not been particularly successful to date, RNA structures without pseudoknots can often be sensibly predicted using free energy-based scoring methods that account for base pairing and stacking.Mathews DH, Turner DH. (2006). Prediction of RNA secondary structure by free energy minimization. "Curr Opin Struct Biol" 16(3):270-8.]

Software

Choosing a software tool for structural alignment can be a challenge due to the large variety of available packages that differ significantly in methodology and reliability. Due to its integration with other European Bioinformatics Institute web-based tools, the [http://www.ebi.ac.uk/dali/ EBI DALI] DaliLite webserver has an advantage in the production of single structural alignments for researchers interested in using the alignments to guide experimental work (rather than studying alignment methods themselves). Another useful EBI method is the [http://www.ebi.ac.uk/msd-srv/ssm/ssmstart.html Secondary Structure Matcher] , which relies on the presence of at least two secondary structure elements. A more complete list of currently available and freely distributed structural alignment software can be found in structural alignment software.

See also

* Multiple sequence alignment
* Sequence alignment software
* Sequence alignment
* Structural Classification of Proteins

References

Further reading

* Bourne PE, Shindyalov IN. (2003): "Structure Comparison and Alignment". In: Bourne, P.E., Weissig, H. (Eds): "Structural Bioinformatics". Hoboken NJ: Wiley-Liss. ISBN 0-471-20200-2
* Yuan X, Bystroff C.(2004) "Non-sequential Structure-based Alignments Reveal Topology-independent Core Packing Arrangements in Proteins", Bioinformatics. Nov 5, 2004
* Jung J, Lee B. (2000). Protein structure alignment using environmental profiles. "Protein Eng" 13:535-543.
* Ye Y, Godzik A. (2005). Multiple flexible structure alignment using partial order graphs "Bioinformatics" 21(10): 2362-2369 [http://bioinformatics.oxfordjournals.org/cgi/content/abstract/21/10/2362 Abstract]
* Sippl M, Wiederstein M (2008). A note on difficult structure alignment problems. "Bioinformatics" 24(3): 426-427 [http://bioinformatics.oxfordjournals.org/cgi/content/full/24/3/426?ijkey=oWkOpf10zxhKaF2&keytype=ref Full Text]