superpose - structural alignment based on secondary structure matching and is based on the Secondary Structure Matching (SSM) advanced graph-matching algorithm. It is part of the CCP4 package and was written by Eugene Krissinel of the European Bioinformatics Institute, Cambridge, UK.
"While high sequence similarity almost always implies structural similarity, the opposite is not true. It is therefore expected that three-dimensional alignment will provide more significant clues to protein function and properties than sequence alignment alone".
Most similarity measures are based on the evaluation of the size of common substructures, for example the length of alignment (the longer, the better), and a measure of the distance between them, such as r.m.s.d. (the lower, the better).
The graph-theoretical approach typically includes three major steps:
- graph representation of the objects in question;
- matching the graphs representing the objects; and
- evaluating the common subgraphs found in order to form conclusions about similarity.
Several approaches to protein structure alignment have been explored over the past decade. The techniques used include:
- comparison of distance matrices (DALI);
- analysis of differences in vector distance plots;
- minimization of the soap-bubble surface area between two protein backbones;
- dynamic programming on pairwise distances between the proteins' residues;
- secondary-structure elements (SSEs);
- three-dimensional clustering;
- graph theory;
- combinatorial extension of alignment path (CE);
- vector alignment of SSEs (VAST);
- depth-first recursive search on SSE (DEJAVU); and
- many others.
Most details of protein fold may be expressed in terms of just two types of SSEs, namely helices (including what type of helix) and strands.
Usually the connectivity of SSEs is significant; however, there are situations where it may or should be neglected (e.g. comparison of mutated or engineered proteins, or geometry of active sites). This is the case I am interested in. That is, one can have three-dimensional SSE graphs that are geometrically identical yet have a difference in connectivity between the SSEs. Flexible connectivity is handled in the following ways:
- Connectivity of SSEs is neglected;
- "Soft" connectivity: The general order of matched SSEs along their protein chains is the same in both structures, but any number of missing or unmatched SSEs between the matched ones is allowed; and
- "Strict" connectivity: Matched SSEs follow the same order along their protein chains and may be separated only by an equal number of matched or unmatched SSEs in both structures.
- Rouvray et al., address the problems of structure comparison and recognition by the graph-theoretical approach.
Nalign is the number of residues that align with each other,
N2 are the input structures, and
R0 is an empirical parameter (chose at 3 Å) that measure the relative significance of
Q reaches 1 only for identical structures (
Nalign = N1 = N2 and
RMSD = 0), and decreases to zero with decreasing similarity (increasing
RMSD or/and decreasing
Nalign. Despite the fact that the Q score represents a very basic measure that does not take into account many factors related to the quality of alignment (the number of gaps and their size, sequence identity, etc.), we found that maximization of the Q score produces good results.
The higher the Q score the "better", in general, the alignment.
Sequence Identity (SI)
Nm = Nalign / min(N1,N2)
Nm is the normalized alignment length.
The sequence identity is defined as a fraction of identical residues in the total number of (structurally) aligned residues:
SI = Nident / Nalign
SI <20% is a solid indication of low structural similarity.
superpose foo_1st.pdb [-s CID1] foo_2nd.pdb [-s CID2] [foo_out.pdb]
[-s CID1/2] are optional selection strings in MMDB convention, and
[foo_out.pdb] is optional output file.
- Simple example:
superpose unbound.pdb bound.pdb fitted.pdb
- wikipedia:Structural alignment
- wikipedia:Root mean square deviation (bioinformatics)
- wikipedia:Quaternion — used to optimise RMSD calculations
- wikipedia:Kabsch algorithm — an algorithm used to minimize the RMSD by first finding the best rotation
- Secondary Structure Matching (SSM) — superpose is based off of this algorithm. Uses RMSD.
- DALI — distance alignment matrix method (server, download)
- Combinatorial Extension (CE)
- Cealign — plugin for PyMOL based on CE. By Shindyalov and Bourne.
- SuperPose — a protein superposition server. Uses RMSD.
- PROMOTIF algorithm (Hutchinson & Thornton, 1996) — aids in calculating SSEs
- CONTACT bricking algorithm (e.g., Tadeusz Skarzynski in CCP4 suite) — computes various types of contacts in protein structures.
- NCONT — analyses contacts between subsets of atoms in a PDB file.
- Global Distance Test (GDT) — A different structure comparison measure
- Template Modeling Score (TM-Score) — A different structure comparison measure
- Longest Continuous Segment (LCS) — A different structure comparison measure
- Krissinel E, Henrick K (2004). "Secondary-structure matching (SSM), a new tool for fast protein structure alignment in three dimensions". Acta Cryst, D60:2256-2268.
- Holm L, Sander C (1993). J Mol Biol, 233:123-138.
- Orengo CA, Taylor WR (1996). Methods Enzymol, 266:617-635.
- Falicov A, Cohen FE (1996). J Mol Biol, 258:871-892.
- Subbiah S, Laurents DV, Levitt M (1993). Curr Biol, 3:141-148.
- Gerstein M, Levitt M (1998). Protein Sci, 7:445-456.
- Gerstein M, Levitt M (1996). Proceedings of the Fourth International Conference on Intelligent Systems for Molecular Biology, pp. 59-67. Menlo Park, California: AAAI Press.
- Singh AP, Brutlag DL (1997). Proceedings of the International Conference on Intelligent Systems for Molecular Biology ISMB-97, pp. 284-293. Halkidiki, Greece: AAAI Press.
- Vriend G, Sander C (1991). Proteins, 11:52-58.
- Mizuguchi K, Go N (1995). Protein Eng, 8:353-362.
- Mitchell EM, Artymiuk PJ, Rice DW, Willett PJ (1990). Mol Biol, 212:151-166.
- Alexandrov NN (1996). Protein Eng, pp.727-732.
- Grindley HM, Artymiuk PJ, Rice DW, Willett PJ (1993). Mol Biol, 229:707-721.
- Shindyalov IN, Bourne PE (1998). Protein Eng, 11:739-747.
- Gibrat J-F, Madej T, Bryant SH (1996). Curr Opin Struct Biol, 6:377-385.
- Kleywegt GJ, Jones TA (1997). Methods Enzymol, 277:525-545.
- Zuker M, Somorjai RL (1989). Bull Math Biol, 51:55-78.
- Taylor W, Orengo CJ (1989). Mol Biol, 208:1-22.
- Godzik A, Skolnick J (1994). Comput Appl Biosci, 10:587-596.
- Russell RB, Barton GJ (1992). Proteins, 14:309-323.
- Sali A, Blundell TJ (1990). Mol Biol, 212:403-428.
- Barakat DW, Dean PMJ (1991). Comput Aided Mol Des, 5:107-117.
- Leluk J, Konieczny L, Roterman I (2003). Bioinformatics, 19:117-124.
- Jung J, Lee B (2000). Protein Eng, 13:535-543.
- Kato H, Takahashi YJ (2001). Chem Softw, 7:161-170.
- Chotia C, Lesk AM (1986). EMBO J, 5:823-826.
- Hubbard TJP, Blundell TL (1987). Protein Eng, 1:159-171.
- Flores TP, Orengo CA, Moss DC, Thornton JM (1993). Protein Sci, 2:1811-1826.
- Russell RB, Barton GJ (1994). J Mol Biol, 244:332-350.
- Rouvray DH, Balaban AT, Wilson RJ, Beineke LW (1979). Editors. Applications of Graph Theory, pp. 177-221. NewYork: Academic Press.
- Lesk AM (1986). Acta Cryst A42, 110-113.
- Kabsch W (1976). "A solution for the best rotation to relate two sets of vectors". Acta Crystallographica 32:922–923.
- Holm L, Kaariainen S, Rosenstrom P, Schenkel A. (2008) Searching protein structure databases with DaliLite v.3". Bioinformatics, 24:2780-2781.
- Jia Y, Dewey TG, Shindyalov IN, Bourne PE (2004). "A new scoring function and associated statistical significance for structure alignment by CE". J Comput Biol, 11(5):787-799. PMID: 15700402.
- Pekurovsky D, Shindyalov IN, Bourne PE (2004). "A case study of high-throughput biological data processing on parallel platforms". Bioinformatics, 20(12):1940-1947. PMID: 15044237.
- Shindyalov IN, Bourne PE (2000). "An alternative view of protein fold space". Proteins, 38(3):247-60. PMID: [http://www.ncbi.nlm.nih.gov/pubmed/10713986 10713986
- Armougom F, Moretti S, Keduas V, Notredame C (2006). "The iRMSD: a local measure of sequence alignment accuracy using structural information." Bioinformatics, 22(14):e35-9.
- Damm KL, Carlson HA (2006). "Gaussian-weighted RMSD superposition of proteins: a structural comparison for flexible proteins and predicted protein structures." Biophys J, 90(12):4558-73.
- Kneller GR (2005). "Comment on ``Using quaternions to calculate RMSD" [J. Comp. Chem. 25, 1849 (2004)]." J Comput Chem, 26(15):1660-2.
- Theobald DL (2005). "Rapid calculation of RMSDs using a quaternion-based characteristic polynomial." Acta Crystallogr A, 61(Pt 4):478-80.
- Maiorov VN, Crippen GM (1994). "Significance of root-mean-square deviation in comparing three-dimensional structures of globular proteins." J Mol Biol, 235(2):625-34.