Geometrical core

Geometrical core (core) is a maximal set of alignment positions such that Cα atoms in these positions are disposed similarly in ALL input protein chains.

  

Alignment (example):

Distance threshold (Å)
Minimal core size (#aa's)
Bron – Kerbosch algorithm timeout (secs)
Alternative core new atoms (%)
Max number of cores on output (0 for all)
Core identifier for chain superimposition (0 for the main core)


Definitions

Input alignment

Amino acids (aa's) from one alignment position are considered to be corresponding to each other.

Sequence name must indicate PDB file, chain [and model], see example .

Positions with gaps or residues missed in the PDB file are not considered.

Similarity mesuare

Cα atoms A1, A2 ..., An of protein A are disposed similarly to the corresponding Cα atoms B1, B2 ..., Bn of protein B if for each i,jn the following holds: abs(|Ai, Aj| – |Bi, Bj|) ≤ d. Here |X,Y| is for the distance between atoms X and Y. The parameter d is called 'Distance treshold'.

Similarity for a number of proteins is defined in an analogous way.

Geometrical core

Geometrical core is a maximal set of alignment positions such that Cα atoms in these positions are disposed similarly in ALL input protein chain.

Many cores can may exist. The largest of them is called the "main core".

Other (alternative) cores can intersect or not intersect with the main core or with each other.

If an alternative core has the percent of new atoms with respect to the main core (and already accepted alternative cores) over the threshold, then it is accepted for output.

Algorithm

PDB files are downloaded from the PDB databank.

Each input sequences is aligned to the corresponding sequence obtained from the ATOM section of the protein chain in the PDB file. Discrepancies are controlled and may be a reason of algorithm rejection.

Core search is reduced to finding maximal cliques in a certain graph. Graph vertices are alignment positions and graph edges connect pairs of vertices that are similarly disposed. The Bron–Kerbosh algorithm is used. If its working time exceeds the threshold, then the Bron–Kerbosh algorithm is stopped and a fast heuristic algorithm is used.

 


Algorithm: Sergei Spirin, Andrei Alexeevski, Boris Nagaev
Programming: Boris Nagaev (computation), Sergei Spirin (web-interface)
Contact: sas@belozersky.msu.ru

The work was partly supported by the Russian Foundation for Basic Research, grants 09–04–92743, 09–04–10-07-00685

© S&S 2009-2012