This is an old revision of this page, as edited by Zoicon5 (talk | contribs) at 17:43, 19 July 2004 (→Representation of structures). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.
Revision as of 17:43, 19 July 2004 by Zoicon5 (talk | contribs) (→Representation of structures)(diff) ← Previous revision | Latest revision (diff) | Newer revision → (diff)Protein structural alignment is a form of alignment which tries to establish equivalences between two or more protein structures based on their fold. 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 in the so called "twilight zone" and "midnight zone" of homology (biology), where relationships between proteins can't be detected by sequence alignment methods. The method can therefore be used to establish evolutionary relationships between proteins that share no or nearly no common primary structure. This is especially important in the light of structural genomics and proteomics projects. The result of a structural alignment of two proteins is a superposition of their atomic coordinate sets with a minimal root mean square deviation (RMSD) between the two structures.
Algorithms
Up to now there is no definitive algorithmic solution to structural alignment. It could be shown that the alignment problem is NP-hard. All current algorithms employ heuristic methods. Therefor different algorithms may not produce exactly the same results for the same alignment problem.
Representation of structures
Protein structures have to be represented in some coordinate independent space to make them comparable. One possible representation is the so-called distance matrix, which is a two-dimensional matrix containing all pairwise distance between all Cα atoms of the protein backbone. This can also be represented as a set of overlapping sub-matrices spanning only fragments of the protein. Another possible representation is the reduction of the protein structure to the level of secondary structure elements (SSEs), which can be represented as vectors, and can carry additional information about relationships to other SSEs, as well as about certain biophysical properties.
Comparison and Optimization
In the case of distance matrix representation, the comparison algorithm breaks down the distance matrices into regions of overlap, which are then again combined if there is overlap between adjacent fragments, thereby extending the alignment. If the SSE representation is chosen, there are several possibilities. One can search for the maximum ensemble of equivalent SSE pairs using algorithms to solve the maximum clique problem from graph theory. Other approaches employ dynamic programming or combinatorial simulated annealing.
Packages
Several tools for single and multiple structural alignments are available on the web:
- CE (Combinatorial Extension of the optimum path): http://cl.sdsc.edu/ce.html
- DALI (Distance Matrix Alignment): http://www.ebi.ac.uk/dali/
- HOMSTRAD (Homologous Structure Alignment Database): http://www-cryst.bioc.cam.ac.uk/~homstrad/
- SARF2 (Spatial Arrangement of Backbone Fragments): http://123d.ncifcrf.gov/sarf2.html
- SSAP (Sequential Structure Alignment Program): http://www.biochem.ucl.ac.uk/cgi-bin/cath/GetSsapRasmol.pl
See also
References
- Bourne, P.E & Shindyalov, I.N. (2003): Structure Comparison and Alignment. In: Bourne, P.E., Weissig, H. (Eds): Structural Bioinformatics. Hoboken NJ: Wiley-Liss. ISBN 0-471-20200-2