Clusters: contacts, cluster sizes, and binding#
This page explains what polyphys.analyze.clusters computes from one
frame of positions or contacts, how the cluster sizes are found, what the
pair-separation density is, and how the binding statistics of two-patch
binders are defined. The kernels work on one frame; reading frames is the
caller’s job. BindingStats accumulates
per-frame binding counts, and threshold_sweep()
recounts the saved distance matrices of a whole over a grid of cutoffs and cis
thresholds.
Notation#
- \(n\)
The number of particles in the group,
n_particles.- \(r_c\)
The contact cutoff,
cutoff, in the caller’s length unit. Two particles are in direct contact when their center-to-center distance is at most \(r_c\) (or below it, withinclusive=False).- \(A\)
The direct-contact matrix,
direct_contacts, boolean and \(n \times n\): \(A_{ij}\) is true when \(i\) and \(j\) are in direct contact. It is symmetric with a true diagonal. It is the adjacency matrix of the contact graph, whose vertices are the particles and whose edges are the direct contacts; \(E\) is the number of edges,n_contacts.- cluster
A connected component of the contact graph: a maximal set of particles joined by chains of direct contacts. Its size is its number of particles.
- \(C\)
The contact matrix,
contact_matrix: \(C_{ij}\) is true when \(i\) and \(j\) are in the same cluster. It is the transitive closure of \(A\).- bonds
The number of direct contacts of one particle, its degree in the contact graph, from \(0\) to \(n - 1\).
- genomic distance
For two monomers of one chain, the number of backbone bonds between them: \(|i - j|\) on a linear chain and \(\min(|i - j|,\, N - |i - j|)\) on a ring of \(N\) monomers.
- \(\vec R\), \(R\)
The separation vector of one pair of monomers and its length, \(R = |\vec R|\).
- \(P(\vec R)\), \(\bar P(R)\)
The probability density of \(\vec R\) over the chain’s configurations, \(\int P\, d^3R = 1\), and its average over the directions of \(\vec R\).
- patch, binder
A binder is a protein with two binding sites, its patches; binder \(k\) owns patches \(2k\) and \(2k + 1\). A binder is free when neither patch touches a monomer, dangling when one does, and bridging when both do. A bridge joins two monomers; it is cis when their genomic distance is at most
cis_thresholdbonds and trans when it is larger.
From positions to clusters#
A frame goes through four steps:
import numpy as np
from polyphys.analyze import clusters
dist = clusters.pair_distances(positions, box=[0.0, 0.0, 2 * lz])
direct = clusters.find_direct_contacts(dist, cutoff=d_large + d_crowd)
bonds_hist = clusters.count_bonds(direct) # [d]: particles with d bonds
cluster_hist = clusters.count_clusters(direct) # [s]: clusters of size s
pair_distances() applies the minimum image
in every direction whose box length is positive and finite, so a pair that
straddles a periodic boundary of wrapped coordinates gets its true
separation. In the cylindrical projects only the axial direction is
periodic.
find_direct_contacts() is the contact
criterion of Sevick, Monson, and Ottino (1988). The cutoff is a project
constant. In the foci projects it is the sum of a large monomer’s and a
crowder’s diameter: the largest separation at which no crowder fits between
the two, so that depletion holds them together.
The clusters are the connected components of the contact graph, found by
scipy.sparse.csgraph.connected_components()
(cluster_labels()). Finding the components
by depth-first search costs time and space proportional to \(n + E\)
(Hopcroft and Tarjan, 1973); converting the dense matrix to a sparse graph
first costs \(O(n^2)\), so a frame costs \(O(n^2)\) in all. The research code
merged pairs of matrix columns in Python, \(O(n^3)\), and its single pass
could stop before the closure was reached: on the 7-node graph with edges
(0, 6), (1, 6), (2, 3), (3, 4), (4, 6) it reported clusters of sizes 1, 1, 5,
and 7, fourteen particles out of seven. That graph is a regression test.
count_clusters() histograms the component
sizes with two calls to numpy.bincount(). The research code read the
sizes off the eigenvalues of \(C\), which is \(O(n^3)\) and correct only when
\(C\) is exactly block all-ones. Two conventions to note:
The histogram is indexed by the size itself and has length \(n + 1\); index 0 is always 0. The research code’s index 0 held the number of zero eigenvalues, which the analysis stage dropped before averaging.
Labels from
cluster_labelsare0, ..., n_clusters - 1, in an order SciPy does not specify. Comparelabels[i] == labels[j], never the label values.
The pair-separation density#
For a tagged pair of monomers, the probe saves the time series of \(R\).
pair_distance_histograms() bins the series
of every pair on one grid, from 0 to the first multiple of bin_size at or
above r_max. Pass the same r_max for every whole of a project, chosen
from the system (the largest separation the box allows), not from the data:
a grid set by each whole’s own maximum gives wholes different numbers of
bins, and an average over wholes is then taken over different sets of
wholes in different bins. A separation beyond the grid raises rather than
being dropped, since a dropped frame would break the normalization below.
pair_separation_density() turns the
counts \(H_k\) of one pair, out of \(N_f\) frames, into an estimate of
\(\bar P(R)\). In spherical coordinates the scalar separation has density
\(P(R) = 4\pi R^2 \bar P(R)\); the factor \(4\pi R^2\) is the Jacobian and
nothing else. Integrating \(P(\vec R)\) over the shell between the edges
\(R_k\) and \(R_{k+1}\), of volume \(\Delta V_k = \tfrac{4\pi}{3}(R_{k+1}^3 -
R_k^3)\), gives the probability of the bin, so
\(\bar P\) has units of one over the length unit cubed, and \(-k_B T \ln \bar P(R)\) is the free energy of the pair at separation \(R\) up to a constant. For an ideal chain of \(n\) Kuhn segments of length \(b\), \(P(\vec R) = (3 / 2\pi n b^2)^{3/2} \exp(-3R^2 / 2 n b^2)\) (Rubinstein and Colby, 2003, Chapter 2); because the estimate carries no free constant, it can be laid over that reference directly. The estimate itself assumes no chain model and no geometry: the accessible volume of a confinement shapes \(\bar P\), not its definition. The exact shell volume is used; the midpoint shell \(4\pi R_c^2 \Delta r\) is 25% too small in the first bin.
This is a probability density over the chain’s configurations, not the
radial distribution function \(g(r)\) of liquid-state theory, whose reference
state, two independent uniform points in the container, is not defined
here. For spatial densities of particles in the confinement, see
polyphys.analyze.density and the Density page.
Binding statistics#
The probe saves a monomer-patch contact matrix per frame, with the monomers
in backbone order along the rows and the two patches of binder \(k\) in
columns \(2k\) and \(2k + 1\). binding_statistics()
returns a FrameBinding with eight
counts and the bridged pairs; BindingStats
accumulates frames and the loop-length histogram:
A recipe, not a doctest: trajectory, n_mon, cutoff, and
dist_monomer_patch, the monomer-patch distances of the current frame,
shape (n_monomers, n_patches), come from the caller’s own frame reader.
from polyphys.analyze import clusters
stats = clusters.BindingStats(n_monomers=n_mon, topology='ring',
cis_threshold=3)
for frame in trajectory:
stats.update(clusters.find_direct_contacts(dist_monomer_patch, cutoff))
series = stats.as_dict() # eight (n_frames,) arrays
loops = stats.loop_length_histogram # [d]: bridged pairs at d bonds
The counting rules, kept from the research code so that its numbers are reproduced:
The patch and binder counts use the contacts as given, so a patch marked on two adjacent monomers (a cutoff artifact) is one engaged patch.
The bridged pairs use the contacts after
enforce_single_patch_contact(), which keeps the lowest-index monomer of each patch, so each bridging binder joins exactly two monomers.Cis and trans count distinct monomer pairs: two binders bridging the same pair count once, and a binder whose two patches hold one monomer is bridging but bridges no pair.
In
binder_contacts(), which links binders on the same or neighboring monomers for cluster counting, every binder is a cluster of at least size 1, bound or not.
Names changed from the research code’s hns_binding dictionary:
Research code |
|
|---|---|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Genomic distances are in bonds everywhere in the module. The research
code’s foci_info returned the number of monomers between a pair, one less;
foci_pair_info() returns bonds and takes
the topology, so a linear chain no longer gets the ring’s shorter way round.
The threshold sweep#
The binding criterion has two parameters, the cutoff and the cis threshold,
and the research code chose them with a sweep that PolyPhys reproduces:
threshold_sweep() takes the float64
monomer-to-patch distance matrices that
BinderStatistics stores when the study’s
BinderSpec.store_distances is on, shape (n_frames, n_monomers, n_patches), and recounts every frame at every (cutoff, cis_threshold)
pair of a grid:
cutoffs = np.round(0.535 + 0.01 * np.arange(16), 3) # 0.535, ..., 0.685
counts, loops = clusters.threshold_sweep(
np.load('N200...ens1-nucleoid-distMatTMonHnsPatch.npy'),
cutoffs, [2, 4], 'ring', inclusive=True)
counts # one row per (cutoff, cis_threshold): eight frame means
loops # (n_rows, n_lengths): the frame-averaged loop-length histogram
pd.concat([counts[['cutoff', 'cis_threshold']], pd.DataFrame(loops)], axis=1)
counts has the columns cutoff, cis_threshold, and the eight
FrameBinding attribute names, each a
mean over the frames; its rows follow the cutoffs as given, with the cis
thresholds inside each cutoff, and no row is repeated. loops has one row
per row of counts, so the last line rebuilds the research
loopLengthHistMon table; the cis threshold does not enter the histogram,
so the rows of one cutoff are equal. Each frame is counted once per cutoff
and its bridged pairs are split once per cis threshold, since only the
cis-trans split depends on the threshold.
Three things to know before comparing a sweep with other numbers:
inclusiveis a required keyword. The research sweep compared strictly,dist < cutoff, while the H-NS study specs count withinclusive=Trueat 0.685 (the probe guide, “Choosing the cutoff”). A strict sweep’s row at 0.685 omits the pairs at exactly the cutoff, so only an inclusive sweep reproduces the series thatBinderStatisticssaved, and only at the spec’s cutoff and cis threshold.The research grid,
np.arange(0.535, 0.685 + 0.01, 0.01), ran one step past its end to 0.695 because of float round-off, so its tables hold seventeen cutoffs; the example above builds the grid from a count and stops at 0.685.The frame means treat the frames as exchangeable counts and are not uncertainties. An error bar on a swept count needs the per-frame series of
BindingStatsandblock_average().
The research script wrote two CSVs per whole,
*-choice_of_threshold-bindingStat.csv and
*-choice_of_threshold-loopLengthHistMon.csv, each rebuilt from lists that
were never reset between cutoffs, so every table repeated the rows of the
earlier cutoffs. The sweep returns each row once; the metadata columns the
script added (dcrowd, phi_c_bulk, nhns, whole, ensemble_id) are
the whole’s parser attributes, which the caller attaches.
References#
E. M. Sevick, P. A. Monson, and J. M. Ottino, “Monte Carlo calculations of cluster statistics in continuum models of composite morphology”, J. Chem. Phys. 88, 1198-1206 (1988). https://doi.org/10.1063/1.454720
J. Hopcroft and R. Tarjan, “Algorithm 447: efficient algorithms for graph manipulation”, Commun. ACM 16, 372-378 (1973). https://doi.org/10.1145/362248.362272
M. Rubinstein and R. H. Colby, Polymer Physics (Oxford University Press, 2003), Chapter 2.