FAST++ Paper Atlas · 1993

Distance-matrix structural comparison

Liisa Holm and Chris Sander, J. Mol. Biol. 233, 123–138 (1993)

Start from internal Cα distance matrices and follow how DALI finds six-residue contact patterns, reduces candidates, and assembles structural alignments through multiple Monte Carlo trajectories.

teaching-model

The City Distance Map: recognizing a district regardless of map orientation

This is a teaching analogy, not a story from the paper. Two model cities face different directions. Instead of rotating them first, an investigator compares patterns of distances between landmarks.

  1. Chapter 1: turn each 3D city into a distance table

    The investigator measures every landmark pair and fills a symmetric grid. Moving or rotating the whole city leaves the numbers unchanged.

    Decoded paper language: DALI represents a structure through its internal Cα–Cα distance matrix, avoiding a required initial superposition.

    Holm & Sander 1993, pp. 123–126.

  2. Chapter 2: compare small district contact patterns

    Rather than compare the entire grid at once, the investigator finds similar local blocks in the two cities and keeps candidates worth assembling.

    Decoded paper language: The method compares six-residue-by-six-residue elementary contact patterns, then reduces heavily overlapping patterns and the candidate pair list.

    Holm & Sander 1993, pp. 125–126.

  3. Chapter 3: distance deviations need weighting

    A two-meter discrepancy need not mean the same thing for neighboring houses and distant towers, so the investigator does not weight every deviation equally.

    Decoded paper language: DALI's elastic score uses relative distance deviations and an envelope that downweights long-range pairs.

    Holm & Sander 1993, p. 126, eq. (3).

  4. Chapter 4: multiple crews explore assemblies stochastically

    Several crews start from different candidates and add or remove district matches. They sometimes accept a temporarily worse proposal to avoid becoming trapped too early.

    Decoded paper language: The paper uses multiple Monte Carlo trajectories to assemble, prune, and refine residue equivalences.

    Holm & Sander 1993, pp. 126–127, Methods 2(d).

  5. Chapter 5: districts may even change order

    If district order differs, the investigator can still recognize similar layouts under relaxed rules instead of being bound to one forward-only route.

    Decoded paper language: Original DALI search can relax sequence order to represent arbitrary gaps, chain reversal, and segment permutation, unlike monotone-path methods.

    Holm & Sander 1993, pp. 126–127.

A five-stop plain-language map of DALI

The core thread is simple: turn each structure into a rotation-invariant internal-distance map, then assemble an alignment from similar patterns.

  1. 1. Each cell stores one internal Cα distance

    Cell i,j stores the distance between residues i and j within one structure.

    Keep only this: It describes internal shape, not global orientation.

    Holm & Sander 1993, pp. 123–126.

  2. 2. Find candidates from six-by-six contact patterns

    Local blocks are compared first, then overlapping candidates are reduced to avoid confronting every combination at once.

    Keep only this: A small block is a candidate building block, not a complete alignment.

    Holm & Sander 1993, pp. 125–126.

  3. 3. Score patterns elastically

    Relative distance deviations and an envelope avoid penalizing relationships at different scales identically.

    Keep only this: DALI compares a network of internal relationships.

    Holm & Sander 1993, p. 126.

  4. 4. Assemble candidates with Monte Carlo search

    Search repeatedly adds, removes, or adjusts matches. Multiple trajectories explore different starts before better solutions are refined.

    Keep only this: Stochastic proposals are a way to explore a huge search space, not mere guessing.

    Holm & Sander 1993, pp. 126–127.

  5. 5. Separate the original method from this site's small lab

    The site lab shows 6×6 internal-distance differences but does not reproduce the reduced matrix, elastic score, or full Monte Carlo alignment.

    Keep only this: Seeing one concept is not the same as reproducing all of DALI.

Check understanding

  1. What happens to the internal distance matrix after rotating the whole protein?

    • It stays the same
    • Every distance doubles
    • The matrix becomes a vector

    Rigid rotation preserves every pairwise distance.

  2. What is a contact pattern in the workflow?

    • A local candidate used to assemble an alignment
    • A final biological-function conclusion
    • A rotation matrix

    Local patterns narrow the candidate space and still require later assembly.

  3. Is the site's 6×6 difference map a complete DALI output?

    • No; it is a teaching slice
    • Yes; it is the original elastic score
    • Yes, missing only color

    The lab intentionally exposes only the distance-map intuition and labels what remains unimplemented.

Completion task: Use three sentences to explain why distance matrices ignore rotation, what contact patterns do, and what Monte Carlo search explores.

paper-fact

Representation: a pose-invariant 2D map of 3D structure

Cell i,j of matrix D stores the Euclidean distance between two Cα atoms in one protein. If the structure itself does not deform, rotating or translating the whole chain leaves D unchanged.

When two distance maps are compared, similar substructures appear as blocks with small distance differences. Near-diagonal regions describe local backbone geometry, while short off-diagonal distances reveal tertiary contacts.

Dᵢⱼ = ‖rᵢ − rⱼ‖₂

rᵢ and rⱼ are Cα coordinates in one structure. D is symmetric and Dᵢᵢ = 0.

Holm & Sander 1993, pp. 123–125, Figs. 1–2.

paper-fact

Step 1: reducing overlapping hexapeptides into contact patterns

The paper systematically compares hexapeptide-by-hexapeptide blocks across two distance matrices. Because neighboring candidates overlap heavily, repeated similar hexapeptides along the main diagonal are merged into longer segments and then reduced to contact patterns between segments.

The candidate pair list progresses from short-range to longer-range contacts. Fast filters such as row and column distance sums reject grossly incompatible patterns before only higher-scoring candidates proceed.

Holm & Sander 1993, p. 126, Methods 2(c).

paper-fact

Scoring: relative distance deviations rather than RMSD alone

The elastic score uses the relative deviation between two matched internal distances. d* is their average; θᴱ is set to 0.20, and the envelope w(r)=exp(−r²/a²), with a=20 Å, downweights long-range pairs.

This prevents gradual geometric distortion from being treated exactly like the same absolute penalty in every cell. The lab displays intuitive |Dᴬ−Dᴮ| values, not the original elastic score.

φᴱ(i,j) = [θᴱ − |dᴬᵢⱼ − dᴮᵢⱼ| / d*ᵢⱼ] · w(d*ᵢⱼ),  i ≠ j

For i=j the paper sets φᴱ=θᴱ. This is a pairwise contribution between already equivalent elements in an alignment.

Holm & Sander 1993, p. 126, eq. (3).

paper-fact

How the paper evaluated the method

The authors ran an all-against-all comparison of 225 representative protein structures, totaling 25,200 pairs, with every pair below 30% sequence identity. The search allowed segment shuffling and reversal.

The paper reports an overall classification consistent with visual classifications and demonstrates similar folds with different topology, structural families, and unexpected structural relationships. These are the authors' 1993 results, not a benchmark reproduced by this site.

Holm & Sander 1993, abstract and pp. 129–136.

Worked example: rotation does not change a contact pattern

Take six consecutive points from synthetic trace A and copy the same segment into B. B may be globally rotated and translated, then locally deformed or intentionally sampled from the wrong start.

  1. Six points form a symmetric 6×6 matrix with 15 unique pair distances after removing the diagonal and symmetric duplicates.
  2. First compare the rigid-motion case. The coordinates appear far apart, yet all 15 internal distances in A and B agree.
  3. Then use a shifted candidate or local deformation. Select difference cells to see which corresponding 3D internal relationships diverge.

The site summarizes the block with mean |Dᴬ−Dᴮ|: it approaches zero for a matching fragment under rigid motion and rises after a shift or deformation. This summary is not DALI's original similarity score.

Glossary

Distance matrix
A square matrix of all residue-pair distances within one structure.
Contact pattern
A small distance-matrix block representing the relationship between two local segments.
Reduced distance matrix
A reduced representation that merges heavily overlapping hexapeptide patterns into segments and keeps representative intra- and inter-segment contacts.
Monte Carlo search
Repeated exploration of alternative alignments through stochastic proposals.

Interactive lab

Interactive lab loads when JavaScript is available.

Sources and limits

  • The lab uses synthetic Cα-like traces without side chains, ligands, real-PDB noise, or multi-domain flexibility.
  • The 6×6 block difference is not a reproducible reduced distance matrix, original elastic score, or Monte Carlo alignment.
  • The 225-structure results are author-reported; this site has not rerun the same dataset and parameters.