Enumerates the automorphisms of a residue, which are basically chemical symmetries that affect RMSD calculations. More...

#include <automorphism.hh>

Inheritance diagram for core::chemical::AutomorphismIterator:

[legend]

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_

Detailed Description

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 re-label 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 6-3 and 2-5, and missing bonds 6-5 and 2-3.

See also: OpenEye's OEChem library and its OERMSD() function.

Constructor & Destructor Documentation

core::chemical::AutomorphismIterator::AutomorphismIterator	(	ResidueType const &	restype,
		bool	includeH = `false`
	)

inline

Including H will lead to many, many more automorphisms!

References curr_, core::chemical::ResidueType::natoms(), natoms_, core::chemical::ResidueType::nheavyatoms(), and restype_.

core::chemical::AutomorphismIterator::AutomorphismIterator	(	ResidueType const &	restype,
		ResidueType const &	restype2,
		bool	includeH = `false`
	)

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_, and restype_.

virtual core::chemical::AutomorphismIterator::~AutomorphismIterator ( )

inlinevirtual

Member Function Documentation

bool core::chemical::AutomorphismIterator::bonded	(	Size	i,
		Size	j
	)

inlineprivate

Are atoms i and j bonded to each other on Restype1?

References core::chemical::ResidueType::path_distance(), and restype_.

bool core::chemical::AutomorphismIterator::bonded2	(	Size	i,
		Size	j
	)

inlineprivate

Are atoms i and j bonded to each other on Restype2?

References core::chemical::ResidueType::path_distance(), and restype2_.

Referenced by edges_match().

bool core::chemical::AutomorphismIterator::can_pair	(	Size	i,
		Size	j
	)

inlineprivate

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().

bool core::chemical::AutomorphismIterator::edges_match ( Size i )

inlineprivate

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_.