Genomic Distance Clusters

Group samples into single-linkage components using a supplied genomic-distance threshold; connected membership does not establish transmission.

Description

Build connected sample clusters from a supplied symmetric distance matrix and an inclusive pairwise threshold.

A genomic-distance matrix summarizes pairwise differences under a chosen sequence-comparison method. A threshold can turn it into an undirected graph: samples are nodes, and a pair is linked when its distance is no greater than the threshold. Connected components collect nodes linked by any path.^[1]

Path connectivity permits chaining. If A is close to B and B is close to C, all three join one component even when A and C are farther apart than the threshold. This is not a rule requiring every pair within a cluster to be close.

Genomic Distance Clusters reports zero-based component indexes in sample order and the number of components. It uses an existing distance matrix without aligning sequences or inferring transmission.

When to group samples by threshold connectivity

Use the tool with a small, consistently defined distance matrix and an explicit threshold. Retain the comparison method and alignment basis so the distances and resulting groups remain interpretable.

Identify connected components of a pairwise-close graph.
Explore sensitivity to a chosen threshold.
Check whether chaining explains a large cluster.

How to enter a distance matrix and build components

Enter 1 to 128 distinct Sample ids and an equally sized square Distance matrix in the same sample order.
Use finite nonnegative entries, an exactly zero diagonal, and exact symmetry.
Enter nonnegative Maximum distance in the matrix’s unit.
Run the tool and pair each Cluster index with its sample ID.

The implementation initializes every index as unassigned. In input order it starts a new component at the first unassigned sample, then performs a breadth-first traversal of pairs whose distance is ≤ maximumDistance. It labels all reachable samples with the same index and continues until every sample is assigned.

json

{
  "input": {
    "sampleIds": [
      "A",
      "B",
      "C"
    ],
    "distanceMatrix": [
      [
        0,
        1,
        5
      ],
      [
        1,
        0,
        6
      ],
      [
        5,
        6,
        0
      ]
    ],
    "maximumDistance": 2
  },
  "output": {
    "clusterIndexes": [
      0,
      0,
      1
    ],
    "clusterCount": 2
  }
}

A single sample forms one component. Threshold zero can still join distinct samples with zero distance. Invalid dimensions, duplicate IDs, asymmetric entries, negative values, or a nonzero diagonal produce errors.

Limitations and interpretation

The tool does not compute sequence distances, verify alignment quality, or require a mathematical triangle inequality.
Connected components do not establish direct transmission, direction, ancestry, epidemiological linkage, or a named lineage.
Cluster labels depend on sample order; they are local indexes rather than stable cross-dataset identifiers.
The threshold is supplied, and no biological cutoff, uncertainty analysis, or complete-linkage diameter bound is inferred.

Alternative or Complementary methods

Use sequence-comparison or mutation-signature methods before interpreting supplied distances. Syntax validation checks the spelling of an existing lineage label; it cannot name these graph components.

References

Connected components: graph connectivity and breadth-first traversal — NetworkX developers

Similar or alternative tools

Clade Signature Support
Compare observed mutation labels with supplied candidate signatures rather than pairwise graph connectivity.
Lineage Format Audit
Check a supplied Pango-style label’s syntax without assigning a lineage to samples.