meshi.geometry
Class DistanceMatrix

java.lang.Object
  meshi.util.MeshiProgram
      meshi.geometry.DistanceMatrix

All Implemented Interfaces:

Updateable

Direct Known Subclasses:

DistanceMatrixBondedOnly, DistanceMatrixCaOnly, DistanceMatrixNoImageAtoms, DistanceMatrixWhichUpdateOnlyMovingAtoms, OldDistanceMatrix

public class DistanceMatrix
extends MeshiProgram
implements Updateable

Where all the headache of distances is handled.
Almost any measurable feature of a molecule is related to distances between pairs of meshi.molecularElements.atoms. Thus, The calculation of distances (and their inverse and derivatives) are typically a computational bottleneck in structural biology applications. In all applications that we are aware of (Please, enlighten us if you know better) distance calculation is done as part of the procedures that use it (say, as part of the van-der-Waals energy calculation). As a result the distance between two atoms may be calculated more then once. For example the distance between two atoms may be calculated both during angle and torsion angle energies calculations. In Meshi we tried to encapsulate all distance related issues in few classes: Distance, its subclasses and this one.

The motivation behind this class is twofold: first, to keep all the headache of cutoff distances (see below) in a single place. Second, to arrange all the distances of a molecular system in a single data structure so that no distance is calculated more than once in a single energy evaluation.

Distance cutoff
Calculating and storing all the distances of a molecular system requires O(n^2) time and storage, where n is the number of atoms. Heuristic algorithms reduces it to O(n), under certain assumptions. The heuristic algorithms (see references below) relays on three characteristics of energy functions and energy based simulations:

1. Atoms have a characteristic minimal distance from other atoms. Thus, the distance matrix is typically dominated by large distances.
2. Energy functions typically decay with distance and become negligible when the atoms are far apart.
   This implies that even if the energy function is formally defined over all distances, distances above some threshold can be considered "infinite" and having no energy contribution.
3. During most of an energy based simulation (e.g. MD, minimization, MC etc.) the atom movements are rather slow, and the distance matrix changes very little between consecutive simulation steps.
   This implies that most of the atom pairs that are "infinitely" distant in a given simulation step will remain so in the next step.

The current implementation requires O(n^2) storage and O(n) CPU time. Future implementations are intended to be more efficient.

The first step of the algorithm is to separate the set of distances into two groups:

1. bonded distances - these are distances between atoms that are not likely to be too far apart at any time and thus, algorithms based on distance cutoffs are not applicable to them. Typically these are atoms separated by up to three or four covalent bonds. The number of these distances is O(n) so they do not add to the computational complexity.
2. unbonded distances - these are distances between atoms that may or may not be close in space.

by two predefined points: rMax & rmax+buffer

1. 0 < distance <= rMax
   It is assumed that all non zero interactions occure within this distance range.
   The algorithm garenties that if a pair of atoms have a distance within this range it is included in the nonbonded list.
2. rMax < distance <= rMax + buffer
   Some of the atom pairs with a distance within this range are included in the nonbonded list.
3. rMax < distance
   These atom pairs are not included in the nonbonded list
The number of atom-pairs with inter-atomic distances in the first two regions is O(n). These atom-pairs are stored in a list called the non-bonded-list. The only O(n^2) task is to test for each of the O(n^2) atom-pairs currently in the third region whether it moved to the first two. This is where our assumption that changes in the inter-atomic distances are slow enters. Consider a pair of atoms A1 and A2 that were in the coordinates C1(S) and C2(S) at some step S of the simulation such that the distance between them D(C1(S),C2(S)) > rMax+buffer. D(C1(S+T),C2(S+T)) the distance between these atoms at some later step S+T may be smaller or equal to rMax only if at least for one of the atoms D(C(S),C(S+T)) > buffer/2. This condition is tested in O(n) and assuming slow atoms movements should, for most atoms fail. Only when this condition is satisfied for one of the proteins We should check all it's distances from other atoms again with again O(n) complexity.

Nested Class Summary

class	DistanceMatrix.Indicator
private class	DistanceMatrix.RowIterator

Field Summary

protected DistanceList	bondedList Atom pairs with inter-atomic distances that are always relatively small.
protected int	bondedListDepth
protected double	buffer
protected static double	bufferOneThirdSqr (buffer/3)^2
protected boolean	debug
static int	DEFAULT_BONDED_LIST_DEPTH
static double	DEFAULT_BUFFER
static double	DEFAULT_RMAX
protected static double	edge
protected java.util.ArrayList<DistanceList>	energyTermsDistanceLists List of DistanceLists Every DistanceList contains distances needed for one EnergyTerm, selected by its filter For example: - Distances of good hydrogen bonds candidate that were added in the current update opperation - Applicable distances between nonBonded C-N candidate that were added in the current update opperation
protected Grid	grid
private DistanceMatrix.Indicator	indicatorToUpdateHB
protected MatrixRow[]	matrix Internal data structure.
MolecularSystem	molecularSystem The list of all atoms in the molecular system.
private int	newConstant
private boolean	nonBondedFlag
protected DistanceList	nonBondedList Atom pairs with inter-atomic distances below rMax (and some of the pairs below rMax+buffer).
protected int	numberOfUpdates
protected static double	rMax Maximal distance for nonzero interactions.
protected static double	rMax2
protected static double	rMaxPlusBuffer rMax+buffer
protected static double	rMaxPlusBuffer2 (rMax+buffer)^2
static Terminator	terminator

Fields inherited from class meshi.util.MeshiProgram

commandLine, name

Constructor Summary

DistanceMatrix(MolecularSystem molecularSystem)


DistanceMatrix(MolecularSystem molecularSystem, double rMax, double buffer, double edge, int bondedListDepth)


Method Summary

DistanceList	bondedList()
double	buffer()
void	DebugOFF() Exit DistanceMatrix debug mode.
void	debugON() Enter DistanceMatrix debug mode.
static double	DEFAULT_EDGE(double rMax, double buffer)
Distance	distance(Atom atom1, Atom atom2) Returns the Distance object of the parameters.
Distance	distance(AtomPair atomPair)
Distance	distance(int atom1Number, int atom2Number) Returns the Distance object of the parameters.
void	doNotUpdateNonBondedList()
java.util.ArrayList<DistanceList>	energyTermsDistanceLists()
static AtomList	getBonded(Atom atom, int depth)
static void	getBonded(Atom atom, int depth, AtomList out, int rootNumber)
static DistanceList	getBondedList(MolecularSystem molecularSystem, int depth, MatrixRow[] matrix)
DistanceMatrix.Indicator	indicatorToUpdateHB()
DistanceList	nonBondedList() Returns the non-bonded-list.
int	nonBondedListSize() Returns the bonded list
double	radius()
private void	reset()
static double	rMax()
static double	rMax2()
static double	rMaxPlusBuffer()
static double	rMaxPlusBuffer2()
java.util.Iterator	rowIterator()
MatrixRow	rowNumber(int index)
java.lang.String	toString()
protected void	update()
void	update(int numberOfUpdates) Updates the distance matrix.

Methods inherited from class meshi.util.MeshiProgram

about, debug, get2ndString, getb, getB, getd, getD, getFlag, getFlagedArgument, geti, getI, getOrderedArgument, getS, getS, initRandom, initRandom, initRandom, printGlobalTable, randomNumberGenerator, seed, tableGet, tableIncludes, tableSet, verbose

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Field Detail

terminator

public static final Terminator terminator

DEFAULT_RMAX

public static final double DEFAULT_RMAX

See Also:

Constant Field Values

DEFAULT_BUFFER

public static final double DEFAULT_BUFFER

See Also:

Constant Field Values

DEFAULT_BONDED_LIST_DEPTH

public static final int DEFAULT_BONDED_LIST_DEPTH

See Also:

Constant Field Values

indicatorToUpdateHB

private DistanceMatrix.Indicator indicatorToUpdateHB

molecularSystem

public final MolecularSystem molecularSystem

The list of all atoms in the molecular system.

matrix

protected MatrixRow[] matrix

Internal data structure.

grid

protected Grid grid

rMax

protected static double rMax

Maximal distance for nonzero interactions.

rMax2

protected static double rMax2

edge

protected static double edge

rMaxPlusBuffer

protected static double rMaxPlusBuffer

rMax+buffer

rMaxPlusBuffer2

protected static double rMaxPlusBuffer2

(rMax+buffer)^2

buffer

protected double buffer

bufferOneThirdSqr

protected static double bufferOneThirdSqr

(buffer/3)^2

nonBondedList

protected DistanceList nonBondedList

Atom pairs with inter-atomic distances below rMax (and some of the pairs below rMax+buffer).

energyTermsDistanceLists

protected java.util.ArrayList<DistanceList> energyTermsDistanceLists

List of DistanceLists Every DistanceList contains distances needed for one EnergyTerm, selected by its filter For example: - Distances of good hydrogen bonds candidate that were added in the current update opperation - Applicable distances between nonBonded C-N candidate that were added in the current update opperation

bondedList

protected DistanceList bondedList

Atom pairs with inter-atomic distances that are always relatively small.

newConstant

private int newConstant

nonBondedFlag

private boolean nonBondedFlag

bondedListDepth

protected int bondedListDepth

numberOfUpdates

protected int numberOfUpdates

debug

protected boolean debug

Constructor Detail

DistanceMatrix

public DistanceMatrix(MolecularSystem molecularSystem)

DistanceMatrix

public DistanceMatrix(MolecularSystem molecularSystem,
                      double rMax,
                      double buffer,
                      double edge,
                      int bondedListDepth)

Method Detail

DEFAULT_EDGE

public static final double DEFAULT_EDGE(double rMax,
                                        double buffer)

energyTermsDistanceLists

public java.util.ArrayList<DistanceList> energyTermsDistanceLists()

debugON

public void debugON()

Enter DistanceMatrix debug mode.

DebugOFF

public void DebugOFF()

Exit DistanceMatrix debug mode.

reset

private void reset()

update

public void update(int numberOfUpdates)
            throws UpdateableException

Updates the distance matrix.

Specified by:

update in interface Updateable

Throws:

UpdateableException

update

protected void update()
               throws UpdateableException

Throws:

UpdateableException

rowNumber

public MatrixRow rowNumber(int index)

nonBondedList

public DistanceList nonBondedList()

Returns the non-bonded-list.

bondedList

public DistanceList bondedList()

distance

public Distance distance(Atom atom1,
                         Atom atom2)

Returns the Distance object of the parameters.

distance

public Distance distance(AtomPair atomPair)

distance

public Distance distance(int atom1Number,
                         int atom2Number)

Returns the Distance object of the parameters.

radius

public double radius()

toString

public java.lang.String toString()

Overrides:

toString in class MeshiProgram

nonBondedListSize

public int nonBondedListSize()

Returns the bonded list

getBondedList

public static DistanceList getBondedList(MolecularSystem molecularSystem,
                                         int depth,
                                         MatrixRow[] matrix)

getBonded

public static AtomList getBonded(Atom atom,
                                 int depth)

getBonded

public static void getBonded(Atom atom,
                             int depth,
                             AtomList out,
                             int rootNumber)

doNotUpdateNonBondedList

public void doNotUpdateNonBondedList()

rMax

public static double rMax()

rMax2

public static double rMax2()

buffer

public double buffer()

rMaxPlusBuffer2

public static double rMaxPlusBuffer2()

rMaxPlusBuffer

public static double rMaxPlusBuffer()

indicatorToUpdateHB

public DistanceMatrix.Indicator indicatorToUpdateHB()

rowIterator

public java.util.Iterator rowIterator()