Rosetta Core
2014.35

Enumerates the automorphisms of a residue, which are basically chemical symmetries that affect RMSD calculations. More...
#include <automorphism.hh>
Public Member Functions  
AutomorphismIterator (ResidueType const &restype, bool includeH=false)  
Including H will lead to many, many more automorphisms! More...  
AutomorphismIterator (ResidueType const &restype, ResidueType const &restype2, bool includeH=false)  
The mapping returned will be from restype to restype2 Including H will lead to many, many more automorphisms! More...  
virtual  ~AutomorphismIterator () 
utility::vector1< Size >  next () 
Returns the next automorphism for this residue type as a vector that maps "old" atom indices to "new" atom indices. Returns an empty vector when no more automorphisms remain. More...  
Private Member Functions  
bool  can_pair (Size i, Size j) 
Are atoms i and j potentially interchangeable? More...  
bool  edges_match (Size i) 
Does the current mapping preserve all edges? More...  
bool  bonded (Size i, Size j) 
Are atoms i and j bonded to each other on Restype1? More...  
bool  bonded2 (Size i, Size j) 
Are atoms i and j bonded to each other on Restype2? More...  
Private Attributes  
ResidueType const &  restype_ 
ResidueType const &  restype2_ 
Size  natoms_ 
utility::vector1< Size >  curr_ 
curr_[i] = current partner for atom i More...  
utility::vector1< Size > const  empty_list_ 
Enumerates the automorphisms of a residue, which are basically chemical symmetries that affect RMSD calculations.
Common automorphisms include flipping a phenyl ring (think Phe chi2) or rotating a methyl group (or CF3, if you don't care about H). However, they can be much more complicated than that, and some cannot be imitated by rotation about a bond. Examples include labeling a CF3 clockwise vs. counterclockwise, or swapping the CF3 branches of C(CF3)2R. See the ligand of PDB 1PQC for a reasonably complex example.
Formally, a graph automorphism is an isomorphism of that graph with itself: given a graph G(V,E) and a mapping M that relabels the vertices according to M(v) > v', then M is an automorphism iff (M(u),M(v)) is an edge if and only if (u,v) is an edge. If the vertices are "colored" (in our case, have atom types), it must also be true that M(v) and v have the same color, for all v in V.
Thus you can relabel a phenyl ring
2 3 6 5 6 3 1 4 or 1 4 but not 1 4 6 5 2 3 2 5
because in the last case, there are new bonds 63 and 25, and missing bonds 65 and 23.
See also: OpenEye's OEChem library and its OERMSD() function.

inline 
Including H will lead to many, many more automorphisms!
References curr_, core::chemical::ResidueType::natoms(), natoms_, core::chemical::ResidueType::nheavyatoms(), and restype_.

inline 
The mapping returned will be from restype to restype2 Including H will lead to many, many more automorphisms!
References curr_, core::chemical::ResidueType::natoms(), natoms_, core::chemical::ResidueType::nheavyatoms(), restype2_, restype_, and runtime_assert.

inlinevirtual 
Are atoms i and j bonded to each other on Restype1?
References core::chemical::ResidueType::path_distance(), and restype_.
Are atoms i and j bonded to each other on Restype2?
References core::chemical::ResidueType::path_distance(), and restype2_.
Referenced by edges_match().
Are atoms i and j potentially interchangeable?
We want this check to be fast but also to eliminate as many potential pairings as possible. We currently check (1) atom types and (2) number of neighbors. We could potentially also check atom types of neighbors, but that costs a set comparison or two array sorts, so we don't right now.
References core::chemical::ResidueType::atom(), core::chemical::Atom::atom_type_index(), core::chemical::Atom::element_type(), core::chemical::ResidueType::name3(), core::chemical::ResidueType::nbrs(), restype2_, and restype_.
Referenced by next().
Does the current mapping preserve all edges?
That is, if (i,j) is an edge, is (curr_[i],curr_[j]) also an edge? Checks all edges (i,j) where j < i, for the supplied i. (Edges with j > i can't be checked becaues curr_[j] isn't valid yet.)
References bonded2(), curr_, core::sequence::end, core::chemical::ResidueType::nbrs(), and restype_.
Referenced by next().
utility::vector1< Size > core::chemical::AutomorphismIterator::next  (  ) 
Returns the next automorphism for this residue type as a vector that maps "old" atom indices to "new" atom indices. Returns an empty vector when no more automorphisms remain.
First automorphism is the identity, [1 2 3 4 ... N] The algorithm works its way through the list of atoms one at a time, for each one trying to pair it with every other possible atom (including itself) that isn't already paired with some earlier atom. To be paired, the atoms need only be of the same chemical type; for efficiency though, we also check that they have the same number of neighbors. We also check that all the edges between the current atom and previously paired atoms also exist between their paired counterparts (a condition for true automorphisms). If we get to a point where we can't find a partner for some atom, we know some earlier pairing is wrong, so we backtrack and try something else. This algorithm would be more natural to represent recursively, keeping state on the stack, but by "flattening" it like this we can use the backtracking machinery to "resume" our search on the next call to next(), thereby iterating over all the possible automorphisms. The vector curr_[] thus takes the place of the stack, and used[] serves to prevent two different atoms from being paired with the same partner simultaneously.
References can_pair(), curr_, edges_match(), empty_list_, and natoms_.

private 
curr_[i] = current partner for atom i
Referenced by AutomorphismIterator(), edges_match(), and next().

private 
Referenced by next().

private 
Referenced by AutomorphismIterator(), and next().

private 
Referenced by AutomorphismIterator(), bonded2(), and can_pair().

private 
Referenced by AutomorphismIterator(), bonded(), can_pair(), and edges_match().