# Structure Alignment (pele.mindist)¶

Tools for finding the best alignment between two structures. (a.k.a. minimum distance routines, mindist, minpermdist, etc.) When trying to find path between two minima it is important to ensure that the starting points are as close together as possible given the symmetries of the system. Common symmetries that need to be accounted for are global translational invariance, global rotational invariance, global inversion symmetry, and permutational invariance.

Translation and inversion symmetries are trivial to deal with. Given either rotational or permutational symmetries it is trivial to find the optimum alignment. When you have both, a solution cannot be found analytically without going through all N-factorial options, a ludicrously slow option. Instead we solve it approximately and stochastically.

All mindist routines that are used throughout pele should have the same signature:

`distance x1new, x2new = compute_mindist(x1, x2)`

Where it is important that x1new is the same as x1. x2new is x2 after being put into best alignment with x1. This signature is expected wherever mindist routines are used and is expected in BaseSystem.get_mindist(). Often compute_mindist is a class that has overloaded __call__ as is the case with, e.g.:

```compute_mindist = MinPermDistAtomicCluster(permlist=[range(natoms)])
distance x1new, x2new = compute_mindist(x1, x2)```

## Rotational alignment¶

Find the optimal rotation for two sets of coordinates (i.e. perform a rms fit)

 findrotation(coords1, coords2[, align_com]) Return the quaternion which aligns XB with XA findrotation_kabsch(coords1, coords2[, ...]) Kabsch, Wolfgang, (1976) “A solution of the best rotation to relate two sets of vectors”, Acta Crystallographica 32:922 findrotation_kearsley(coords1, coords2[, ...]) Return the quaternion which aligns XB with XA

## Permutational aligment¶

Finding the best alignment can be mapped onto the Assignment Problem and solved very quickly using the Hungarian (shortest augmenting path) algorithm.

 optimize_permutations(X1, X2[, permlist, ...]) return the best alignment of the structures X1 and X2 after optimizing permutations find_best_permutation(X1, X2[, permlist, ...]) find the permutation of the atoms which minimizes the distance |X1-X2|

## Rotational + permutational alignment¶

This cannot be solved exactly in a reasonable amount of time (The time scales as natoms factorial). Instead it’s solved iteratively by iterating random rotation -> permutational alignment -> rotational alignment. This generally produces a good alignment, but not necessarily the optimal

 MinPermDistCluster([niter, verbose, tol, ...]) Minimize the distance between two clusters. ExactMatchCluster([tol, accuracy, ...]) Deterministic check if 2 clusters are a perfect match StandardClusterAlignment(coords1, coords2[, ...]) class to iterate over standard alignments for atomic clusters

For atomic cluster, specialized wrapper exist.

 MinPermDistAtomicCluster([permlist, can_invert]) minpermdist for atomic cluster (3 carthesian coordinates per site) ExactMatchAtomicCluster([permlist, can_invert]) minpermdist for atomic cluster (3 carthesian coordinates per site)

See the angleaxis module for angleaxis minpermdist routines

## Periodic Boundary Conditions¶

This is generally a much harder problem than those discussed above. Currently we have no general mindist routine, but we do have a test to check if the structures are identical

 ExactMatchPeriodic(measure[, accuracy]) Deterministic check if 2 structures are a perfect match assume there are permutable atoms, because if there are not then the problem is trivial.

## Customizing minpermdist - minpermdist policies¶

 TransformPolicy interface for possible transformations on a set of coordinates MeasurePolicy interface for possible measurements on a set of coordinates

## Utilities¶

 PointGroupOrderCluster(exact_match) Determines the point group order of a cluster