# index.html.md

# relag

**relag** is a Python binding for the `relag` Rust crate. It provides fast,
SIMD-accelerated tools for working with datasets generated by a *Random Generative
Process* (RGP) — datasets where items share latent structure (e.g. protein families, molecules)
that makes naive random splits leak information between train and test.

This is the human-readable doc, but we also have a LLM doc so you favorite chatbot or agent can read the documentation.
We follow the [llms.txt](https://llmstxt.org) standard, which means you can access the llm doc index with
<a href="./llms.txt">llms.txt</a> or the full documentation in one document with <a href="./llms-full.txt">llms-full.txt</a>.

Happy programming!

## Modules

* [relag.utils](api/utils.md)
  * [`BitFingerprint`](api/utils.md#relag.utils.BitFingerprint)
  * [`RealFingerprint`](api/utils.md#relag.utils.RealFingerprint)
  * [`Vector`](api/utils.md#relag.utils.Vector)
  * [`PdbStructure`](api/utils.md#relag.utils.PdbStructure)
  * [`read_fasta()`](api/utils.md#relag.utils.read_fasta)
  * [`largest_cluster()`](api/utils.md#relag.utils.largest_cluster)
  * [`SWPattern`](api/utils.md#relag.utils.SWPattern)
  * [`SWPatternSet`](api/utils.md#relag.utils.SWPatternSet)
  * [`SWSequence`](api/utils.md#relag.utils.SWSequence)
  * [`SWWord`](api/utils.md#relag.utils.SWWord)
* [relag.kernels](api/kernels.md)
  * [Kernel variant selector](api/kernels.md#module-relag.kernels)
  * [relag.kernels.alignments](api/kernels.md#relag-kernels-alignments)
  * [relag.kernels.molecules](api/kernels.md#relag-kernels-molecules)
  * [relag.kernels.structures](api/kernels.md#relag-kernels-structures)
  * [relag.kernels.protspam](api/kernels.md#relag-kernels-protspam)
  * [relag.kernels.vectors](api/kernels.md#relag-kernels-vectors)
* [relag.core](api/core.md)
  * [Graph construction](api/core.md#graph-construction)
  * [HNSW approximate nearest neighbours](api/core.md#hnsw-approximate-nearest-neighbours)
  * [Graph algorithms](api/core.md#graph-algorithms)
  * [Exact search](api/core.md#exact-search)


# core.html.md

# relag.core

## Graph construction

### *class* relag.core.EdgeStore(node_count: int, edges: Sequence[tuple[int, int, float]])

Bases: `object`

A compact, flat list of weighted directed edges between integer node IDs.

`EdgeStore` is the central data carrier in relag: it is produced by
`exact_edges` and `HNSWState.edges`, consumed by `CsrGraph`, and can be
persisted to disk for later reuse.

Each edge is a triple `(src, dst, weight)` where `src` and `dst` are
zero-based node indices in `[0, node_count)` and `weight` is a `float32`
value.

Example:

```default
from relag.core import EdgeStore

store = EdgeStore(node_count=3, edges=[(0, 1, 0.9), (1, 2, 0.7)])
print(len(store))     # 2
print(store[0])       # (0, 1, 0.9)
for src, dst, w in store:
    print(src, dst, w)

# numpy-style boolean masking: keep only the edges where mask[i] is True
store[[True, False]]   # EdgeStore with only (0, 1, 0.9)
```

#### edges() → list[tuple[int, int, float]]

Return all edges as a list of `(src, dst, weight)` triples.

#### graph(inweight_type: [INWeightType](#relag.core.INWeightType) = INWeightType.Distance) → [CsrGraph](#relag.core.CsrGraph)

Build a `CsrGraph` from this edge store.

* **Parameters:**
  **inweight_type** – How to convert the raw edge weights to similarity-like weights.
  See `INWeightType`. Pass `INWeightType.Unweighted` to ignore
  weights entirely (every edge gets weight `1.0`). Defaults to
  `INWeightType.Distance`, meaning weights are assumed to be a distance
  measurement, and are converted to similarities.
* **Returns:**
  A `CsrGraph` backed by this edge list.

#### *static* load(path: str) → [EdgeStore](#relag.core.EdgeStore)

Load an EdgeStore that was previously saved with `EdgeStore.save`. It infers the format
from the extension of the path, `.edgelist` or `.edgestr`.

**Version compatibility (binary format only):** The binary `.edgestr` format is versioned
to the exact package version. A file saved with a different package version will fail to
load with a version mismatch error. There is no forward or backward compatibility. The text
`.edgelist` format is not versioned and may be portable across versions.

* **Parameters:**
  **path** – Path to the file produced by `save`.
* **Returns:**
  The deserialized `EdgeStore`.
* **Raises:**
  **IOError** – If the file cannot be read, the format is invalid, or (for `.edgestr` files)
      the saved version does not match the running package version.

#### node_count() → int

Return the total number of nodes this store was created with.

#### save(path: str) → None

Serialize this EdgeStore to disk. It supports two file formats: `text` with
`.edgelist` extension or `binary` with `.edgestr` extension. Binary is usually 2x
more space efficient at the cost of not being human-readable.

**Version compatibility (binary format only):** The binary `.edgestr` format is versioned
to the exact package version and is not forward or backward compatible. A file saved with
a different package version will fail to load with a version mismatch error. The text
`.edgelist` format has no version stamp and may be portable across versions.

* **Parameters:**
  **path** – Destination file path.
* **Raises:**
  **IOError** – On any I/O failure.

Example:

```default
from relag.core import EdgeStore

store = EdgeStore(node_count=3, edges=[(0, 1, 0.9), (1, 2, 0.7)])
store.save("my/path/myedges.edgelist") # Text format
store.save("my/path/myedges.edgestr")  # Bin format
```

#### return *: [EdgeStore](#relag.core.EdgeStore)*

### *class* relag.core.CsrGraph(edges: [EdgeStore](#relag.core.EdgeStore), inweight_type: [INWeightType](#relag.core.INWeightType) = INWeightType.Distance)

Bases: `object`

Compressed Sparse Row graph built from an `EdgeStore`. A CSR graph is compact, and highly
efficient for traversal, exploiting cache structure and maximizing cache hits. However, it is
immutable, so adding a new node or edge require building the full graph again.

`CsrGraph` is an immutable adjacency structure. Because of its property of being very
efficient for traversal, it is used by graph algorithms such as `partition` and
`connected_components`.

Properties:
: - `n`: Number of nodes.
  - `m`: Sum of all edge weights (or total edge count when `inweight_type=INWeightType.Unweighted`).

Example:

```default
from relag.core import EdgeStore, CsrGraph

store = EdgeStore(4, [(0,1,0.9),(1,2,0.8),(2,3,0.6)])
g = CsrGraph(store)
print(g.n)               # 4
print(g.neighbors(1))    # [(0, 0.9), (2, 0.8)]
print(g.strength(1))     # 1.7
```

#### m

Total weight (each edge counted once)

#### n

Number of nodes

#### neighbors(v: int) → list[tuple[int, float]]

Return the neighbors of node `v` as a list of `(node_id, weight)` pairs.

* **Parameters:**
  **v** – Zero-based node index.

#### strength(v: int) → float

Return the strength (weighted degree) of node `v`.

When the graph is unweighted this equals the degree (number of neighbors).

* **Parameters:**
  **v** – Zero-based node index.

#### subgraph(nodes: Sequence[int]) → tuple[[CsrGraph](#relag.core.CsrGraph), dict[int, int]]

Extract a subgraph composed of a subset of nodes.

New node ids are assigned contiguously in the order `nodes` is given.

All edges pointing outside the subgraph are ignores.

* **Parameters:**
  **nodes** – Node ids to keep, in the desired new order.
* **Returns:**
  A tuple `(subgraph, mapping)` where `mapping` is a dict from old node id
  to new node id.

Example:

```default
sub, mapping = g.subgraph([2, 0, 3])
print(sub.n)      # 3
print(mapping)    # {0: 1, 2: 0, 3: 2}
```

#### edges *: [EdgeStore](#relag.core.EdgeStore)*

#### inweight_type *: [INWeightType](#relag.core.INWeightType)*

#### return *: [CsrGraph](#relag.core.CsrGraph)*

## HNSW approximate nearest neighbours

### *class* relag.core.HNSWConfig(proximity_threshold: float = 0.0, ef_construction: int = 64, m: int = 16, m_max: int = 16, m_max0: int = 32, m_l: float = 0.36, ef_init: int = 1, extend_candidates: bool = False, keep_pruned_connections: bool = True, keep_all_edges: bool = True, cache_capacity: int = 2000000, cache_shards: int = 64, n_threads: int = 0, shuffle: bool = False, use_heuristic: bool = True, strict_ef: bool = False, threshold_based_neighbourhood: bool = False)

Bases: `object`

Configuration for the HNSW approximate nearest-neighbour index.

All parameters have sensible defaults; in most cases you only need to `ef_construction`, and
`proximity_threshold`.

**Parameters:**

- `proximity_threshold`  *(float)* — Distance threshold under which a connection is established in the proximity graph.
- `ef_construction`  *(int)* — Candidate list size during build. Default `64`.
- `m`  *(int)* — Bidirectional links per node at layers > 0.
  Higher = better recall, more memory, slower build. Typical: 8–64.
- `m_max`  *(int)* — Maximum connections per node at layers > 0. Usually equal to `m`.
- `m_max0`  *(int)* — Maximum connections at layer 0. Usually `2 * m`.
- `m_l`  *(float)* — Level generation factor. Usually `0.36 ≈ 1 / ln(m)`.
- `ef_init`  *(int)* — Candidate list size during initial-layer insertion. Almost always 1 for
  a greedy search.
- `extend_candidates`  *(bool)* — Use neighbors of neighbors as candidates, making search more exhaustive.
- `keep_pruned_connections`  *(bool)* — Retain discarded candidates to fill up to `m` connections when not enough connections are found.
- `keep_all_edges`  *(bool)* — Record every below-threshold distance computed during build into
  the proximity graph returned by `edges()`. Default `True`. Setting it to `False` makes
  `edges()` return `None`, but removes a per-hit locked hashmap insert from the hot path.
  Worth doing when the proximity graph is not required.
- `cache_capacity`  *(int)* — Maximum cached kernel scores. Increasing it increase the memory
  footprint, but also cache hits, which can improve runtime performances for computationally expensive kernels.
  Set to `0` to disable the cache entirely — every distance is recomputed directly, which is
  faster for cheap kernels (e.g. `TanimotoBit`/`TanimotoReal`) where cache overhead exceeds the
  cost of the kernel itself.
- `cache_shards`  *(int)* — Number of cache shards (reduces lock contention).
- `n_threads`  *(int)* — Threads used during build. `0` = all available cores.
- `shuffle`  *(bool)* — Shuffle insertion order before building. Can create a less biased
  graph, but reduces cache hits, which increases runtime.
- `use_heuristic`  *(bool)* — Use the heuristic neighbour-selection from the paper (recommended).
- `strict_ef`  *(bool)* — If `True`, enforces the result set size to exactly `ef` during search. Empirically, setting this to `False` can improve runtime performance, as it allows halving `ef_construction` without sacrificing accuracy.
- `threshold_based_neighbourhood`  *(bool)* — Select a minimum of `m` neighbors like the classic algorithm, but doesn’t bound the neighbourhood size as all candidates that are closer than the threshold are kept.

#### cache_capacity *: int*

#### cache_shards *: int*

#### dict() → dict

Return the configuration as a plain Python dict.

#### ef_construction *: int*

#### ef_init *: int*

#### extend_candidates *: bool*

#### keep_all_edges *: bool*

#### keep_pruned_connections *: bool*

#### m *: int*

#### m_l *: float*

#### m_max *: int*

#### m_max0 *: int*

#### n_threads *: int*

#### proximity_threshold *: float*

#### shuffle *: bool*

#### strict_ef *: bool*

#### threshold_based_neighbourhood *: bool*

#### use_heuristic *: bool*

#### return *: [HNSWConfig](#relag.core.HNSWConfig)*

### *class* relag.core.HNSWState(variant: [kernels.KernelVariant](kernels.md#relag.kernels.KernelVariant), data: Any, \*args: Any, proximity_threshold: float = 0.0, ef_construction: int = 64, m: int = 16, m_max: int = 16, m_max0: int = 32, m_l: float = 0.36, ef_init: int = 1, extend_candidates: bool = False, keep_pruned_connections: bool = True, keep_all_edges: bool = True, cache_capacity: int = 2000000, cache_shards: int = 64, n_threads: int = 0, shuffle: bool = False, use_heuristic: bool = True, strict_ef: bool = False, threshold_based_neighbourhood: bool = False, \*\*kwargs: Any)

Bases: `object`

Stateful Hierarchical Navigable Small World (HNSW) approximate nearest-neighbour index. This
class is used to build and search in the index, whereas `HNSWIndex` is a read-only *internal*
representation of the index used for saving / loading / structure exploration.

`HNSWState` wraps the dataset and the graph index together. The typical
workflow is:

1. Construct with the data and a `KernelVariant`.
2. Call `build()` to insert all items and form the graph.
3. Call `search()` to query, or `edges()` to extract the proximity graph
   for downstream clustering / splitting.

HNSW parameters (`proximity_threshold`, `ef_construction`, …) are the same as `HNSWConfig`
and can be passed directly to the constructor as keyword arguments.

`data` may be any Python iterable — a `list`, a `tuple`, a generator, anything with
`__iter__`. It’s drained one item at a time into the constructor’s own Rust-owned copy,
so a generator never needs to be fully materialized into a Python-side list first — both
copies never need to coexist at once. That matters when a single item’s Python
representation is large enough that two full-dataset copies wouldn’t fit in memory
together. When `data` supports `len()` (a `list`/`tuple`), that’s used to
pre-size the Rust-owned copy exactly; it doesn’t change how `data` is walked.

* **Parameters:**
  * **variant** – Kernel to use (e.g.  `KernelVariant.AlignmentGlobal`, `KernelVariant.AlignmentLocal`, `KernelVariant.TanimotoBit`, *etc*).
  * **data** – The dataset — a list of items matching the kernel type (e.g. `list[str]` or
    `list[np.ndarray]`), or any other Python iterable of such items (e.g. a generator).
  * **proximity_threshold, ef_construction, m, m_max, m_max0, m_l, ef_init, extend_candidates,** – keep_pruned_connections, keep_all_edges, cache_capacity, cache_shards,
    n_threads, shuffle, use_heuristic, strict_ef,
    threshold_based_neighbourhood: See `HNSWConfig` for descriptions.

Properties:
: config (HNSWConfig): The config in use.
  index (HNSWIndex): A snapshot of the current graph structure.

Example:

```default
from relag import HNSWState, KernelVariant

seqs = ["MKTAYIAK", "MKTAYIAKQR", "ACDEFGHIKLM", "MKTAYIAKQRQIS"]
state = HNSWState(KernelVariant.AlignmentGlobal, seqs, proximity_threshold=0.3, ef_construction=64)
state.build()
results = state.search(["MKTAYIAK"], k=2)
# results[0] -> [(0, 1.0), (1, 0.88)]

store = state.edges()        # EdgeStore for graph-based splitting
state.save("index.hnsw")
state2 = HNSWState.load(KernelVariant.AlignmentGlobal, "index.hnsw", seqs)
```

#### build(progress: bool = True) → None

Build the HNSW index by inserting all data items.

Must be called before `search` or `edges`. Calling `build` a second
time raises a `RuntimeError`; construct a new `HNSWState` instead.

* **Parameters:**
  **progress** – Display a progress bar. Defaults to `True`.
* **Raises:**
  **RuntimeError** – If the index has already been built.

#### config

Config used to initiate this object.

#### edges() → Optional[[EdgeStore](#relag.core.EdgeStore)]

Extract the proximity graph as an `EdgeStore`.

Returns all edges found during `build`. All distance measurements below the
`proximity_threshold`.

* **Returns:**
  An `EdgeStore` with `node_count = dataset_size`, or `None` if the index was built
  with `keep_all_edges=False`.

#### extend_build(data: Any, progress: bool = True) → None

Extend an already-built index with more data: appended to the dataset, then
inserted into the graph. Existing nodes and edges are untouched.

`data` accepts any Python iterable, same as the constructor (see `HNSWState`’s
class docstring) – drained one item at a time so a generator never needs to be
fully materialized into a Python-side list first.

* **Parameters:**
  * **data** – The new items to add (same type as the original dataset).
  * **progress** – Display a progress bar. Defaults to `True`.
* **Raises:**
  **RuntimeError** – If `build` has not been called yet.

Example:

```default
from relag import HNSWState, KernelVariant

seqs = ["MKTAYIAK", "MKTAYIAKQR", "ACDEFGHIKLM"]
state = HNSWState(KernelVariant.AlignmentGlobal, seqs, proximity_threshold=0.3)
state.build()

more_seqs = ["MKTAYIAKQRQIS", "ACDEFGHIKLMNP"]
state.extend_build(more_seqs)
state.index.dataset_size  # 5

results = state.search(["MKTAYIAKQRQIS"], k=2)
# results[0] -> [(3, 0.0), (1, 0.23)] -- found itself among the new items
```

#### get_layer(layer_idx: int = 0, directed: bool = False, weights: bool = True, progress: bool = True) → [EdgeStore](#relag.core.EdgeStore)

Return the adjacency lists for a specific HNSW layer.

* **Parameters:**
  **layer_idx** – Zero-based layer index (0 = base layer with most nodes).
* **Returns:**
  A list of length `dataset_size` where element `i` is the list of
  neighbour IDs of node `i` at this layer. Node IDs are their index in the original dataset.
* **Raises:**
  **IndexError** – If `layer_idx` is out of range.

Edges of one HNSW layer, as an `EdgeStore`.

* **Parameters:**
  * **layer_idx** – Zero-based layer index (0 = base layer with most nodes).
  * **directed** – If `True`, every edge is returned exactly as internally
    recorded – an undirected connection contributes one entry per
    endpoint, i.e. `(x, y)` is distinct from `(y, x)`. If
    `False` (default), edges are canonicalized and deduplicated,
    so each undirected pair appears exactly once.
  * **weights** – If `True` (default), each edge’s weight is its real
    distance, computed on the fly since not stored in the hierarchical graph.
    If `False`, every edge gets weight
    `1.0` – much cheaper when the real distance isn’t needed.
  * **progress** – Display a progress bar while distances are computed.
    Only meaningful when `weights=True`. Defaults to `False`.
* **Returns:**
  An `EdgeStore` with `node_count = dataset_size`.
* **Raises:**
  **IndexError** – If `layer_idx` is out of range.

#### index

HNSWIndex snapshot.

#### is_built

Whether `build` has been called on this index.

#### *static* load(variant: [kernels.KernelVariant](kernels.md#relag.kernels.KernelVariant), path: str, data: Any, \*args: Any, \*\*kwargs: Any) → [HNSWState](#relag.core.HNSWState)

Load an HNSWState form a binary file saved with `HNSWState.save`.

**Version compatibility:** The binary format is versioned to the exact package version.
A file saved with a different package version (older or newer) will fail to load with
a version mismatch error. There is no forward or backward compatibility guarantee during
the unstable pre-0.1.0 phase.

`data` accepts any Python iterable, same as the constructor (see `HNSWState`’s
class docstring) — including a generator re-reading a cache file.

* **Parameters:**
  * **variant** – Must match the kernel used during the original build.
  * **path** – Path to the saved file.
  * **data** – The original dataset (required to re-attach the kernel).
* **Returns:**
  The restored `HNSWState`, ready to call `search` or `edges` if the index was built.
* **Raises:**
  **RuntimeError** – If the file cannot be read, the format is invalid, or the saved
      version does not match the running package version.

#### save(path: str) → None

Serialize the full state (index + config) to a binary file.

The saved file can be loaded back with `HNSWState.load`. The original
data must be provided again at load time (it is not embedded in the file).

**Version compatibility:** The binary format is versioned to the exact package version.
A file saved with a different package version (older or newer) will fail to load with
a version mismatch error. There is no forward or backward compatibility guarantee during
the unstable pre-0.1.0 phase.

* **Parameters:**
  **path** – Destination file path.
* **Raises:**
  **RuntimeError** – On serialisation or I/O failure.

#### search(queries: Any, k: int = 1, ef: int = 64, threads: int = 0, progress: bool = True) → list[list[tuple[int, float]]]

Search the index for approximate nearest neighbours.

For each query item, returns the `k` most similar items in the dataset,
sorted by descending similarity. The quality of the approximation is
controlled by `ef`: larger values explore more candidates and improve
recall at the cost of speed.

* **Parameters:**
  * **queries** – List of query items (same type as the indexed data).
  * **k** – Number of nearest neighbours to return per query. Defaults to `1`.
  * **ef** – Size of the dynamic candidate list during search. Must be ≥ `k`.
    Defaults to `64`.
  * **threads** – Number of parallel threads. `0` = all available cores.
  * **progress** – Display a progress bar. Defaults to `True`.
* **Returns:**
  A list of length `len(queries)`. Each element is a sorted list of
  up to `k` tuples `(dataset_index, similarity_score)`.
* **Raises:**
  **RuntimeError** – If `build` has not been called yet.

#### variant *: [KernelVariant](kernels.md#relag.kernels.KernelVariant)*

#### data *: Any*

#### args *: Any*

#### proximity_threshold *: float*

#### ef_construction *: int*

#### m *: int*

#### m_max *: int*

#### m_max0 *: int*

#### m_l *: float*

#### ef_init *: int*

#### extend_candidates *: bool*

#### keep_pruned_connections *: bool*

#### keep_all_edges *: bool*

#### cache_capacity *: int*

#### cache_shards *: int*

#### n_threads *: int*

#### shuffle *: bool*

#### use_heuristic *: bool*

#### strict_ef *: bool*

#### threshold_based_neighbourhood *: bool*

#### kwargs *: Any*

#### return *: [HNSWState](#relag.core.HNSWState)*

### *class* relag.core.HNSWIndex

Bases: `object`

Read-only snapshot of the HNSW graph structure after a build.

Obtained via `HNSWState.index`. Primarily useful for inspection,
serialisation, and debugging; normal users interact with `HNSWState`
instead.

Properties:
: dataset_size (int): Number of items indexed.
  layers (list): Nested multi-layer adjacency list `layers[layer][node] = [neighbor_ids]`.
  entry_point (tuple | None): `(layer, node_id)` of the global entry point, or `None` if empty.
  max_layers (int): Number of layers in the hierarchy.
  proximity_edges (list): List of `((src, dst), score)` for proximity-threshold edges.
  config (HNSWConfig): The config used to build this index.

#### config

#### dataset_size

#### entry_point

#### layers

Nested multi-layer adjacency list, layers[layer][node] = [neighbor_ids]. Layers
above 0 may be stored sparsely internally (most nodes aren’t present at those
layers); this densifies them into the full node-id-indexed shape on access.

#### *static* load(path: str) → [HNSWIndex](#relag.core.HNSWIndex)

Load an index previously saved with `HNSWIndex.save`.

**Version compatibility:** The binary format is versioned to the exact package version.
A file saved with a different package version (older or newer) will fail to load with
a version mismatch error. There is no forward or backward compatibility guarantee during
the unstable pre-0.1.0 phase.

* **Parameters:**
  **path** – Path to the saved file.
* **Returns:**
  The deserialised `HNSWIndex`.
* **Raises:**
  **RuntimeError** – If the file cannot be read, the format is invalid, or the saved
      version does not match the running package version.

#### max_layers

#### proximity_edges

#### save(path: str) → None

Save the object to a binary representation (e.g.  *.hnsw* file).

The binary format is versioned to the exact package version and is not
forward or backward compatible. A file saved with version X can only be
loaded by the exact same version X. Files saved with a different version
will fail to load with a version mismatch error.

* **Parameters:**
  **path** – Destination file path (recommended with a .hnsw extension)
* **Raises:**
  **RuntimeError** – On serialisation or I/O failure.

## Graph algorithms

### *class* relag.core.INWeightType

Bases: `object`

How to convert a raw `EdgeStore` weight into the similarity-like edge weight
used internally by `CsrGraph` and the Leiden algorithm.

- `Similarity` — the raw weight is already a similarity; used as-is.
- `Distance` — the raw weight is a distance in `[0, ∞)`; mapped to
  `1 / (1 + w)` so closer nodes get a higher weight.
- `SimilarityComplement` — the raw weight is `1 - similarity`; mapped
  back to a similarity via `1 - w`.
- `Unweighted` — the raw weight is ignored; every edge weight is set to `1.0`.

#### Distance *= INWeightType.Distance*

#### Similarity *= INWeightType.Similarity*

#### SimilarityComplement *= INWeightType.SimilarityComplement*

#### Unweighted *= INWeightType.Unweighted*

### *class* relag.core.LeidenObjective

Bases: `object`

Objective function used by the Leiden community-detection algorithm.

- `Modularity` — Maximise Newman-Girvan modularity. Good default for most graphs.
- `CPM` — Constant Potts Model. Finds communities of a fixed internal density.

#### CPM *= LeidenObjective.CPM*

#### Modularity *= LeidenObjective.Modularity*

### relag.core.find_communities(graph: [CsrGraph](#relag.core.CsrGraph), gamma: float = 1.0, beta: float = 0.01, n_iterations: int = 2, objective: [LeidenObjective](#relag.core.LeidenObjective) = LeidenObjective.Modularity) → list[int]

Detect communities in a graph with the Leiden algorithm.

The Leiden algorithm is an improvement over Louvain that guarantees
well-connected communities. Use the returned cluster labels with
`partition` to produce train/test splits that consider community boundaries.

* **Parameters:**
  * **graph** – The graph to partition into communities.
  * **gamma** – Resolution parameter. Higher values produce more, smaller communities.
    For `Modularity`, typical range is 0.5–2.0; default `1.0`.
    For `CPM`, it represents the minimum internal edge density.
  * **beta** – Randomness parameter controlling the refinement phase.
    Smaller values yield more deterministic results. Default `0.01`.
  * **n_iterations** – Number of optimisation passes. More iterations improve
    quality at the cost of runtime.
  * **objective** – `LeidenObjective.Modularity` (default) or `LeidenObjective.CPM`.
* **Returns:**
  A list of length `graph.n` where element `i` is the cluster ID of node `i`.
  Cluster IDs are arbitrary non-negative integers.

Example:

```default
from relag.core import CsrGraph, EdgeStore, find_communities, LeidenObjective, INWeightType

store = EdgeStore(4, [(0,1,0.9),(1,2,0.8),(2,3,0.6)])
g = CsrGraph(store, inweight_type=INWeightType.Similarity)
clusters = find_communities(g, gamma=1.0, n_iterations=20) # e.g. [0, 1, 2, 3]
```

### relag.core.find_components(graph: [CsrGraph](#relag.core.CsrGraph)) → list[int]

Finds the connected components of a graph.

Runs a standard BFS/union-find over the graph and assigns each node to
its component.

* **Parameters:**
  **graph** – The graph to find components.
* **Returns:**
  A list of length `graph.n` where element `i` is the component ID of
  node `i`. IDs are arbitrary non-negative integers.

Example:

```default
from relag.core import EdgeStore, find_components

store = EdgeStore(6, [(0,1,0.9),(1,2,0.8),(3,4,0.7),(4,5,0.6)])
g = store.graph()
clusters = find_components(g) # [0, 0, 0, 1, 1, 1]
```

### relag.core.partition(clusters: Sequence[int], graph: [CsrGraph](#relag.core.CsrGraph), test_ratio: float = 0.2, seed: Optional[int] = None, post_filtering: bool = False) → tuple[list[int], list[int]]

Split a clustered dataset into train and test index sets along clusters

Clusters are kept intact — no cluster is split across train and test.
The function greedily and randomly assigns whole clusters to the test set until the test size
is larger than `test_ratio`, then assigns the rest to train.

This is the key function for leakage-free dataset splitting: run
`find_communities`, `find_components`, or your own clustering, then call `partition`
to obtain indices you can use to slice your data arrays.

* **Parameters:**
  * **clusters** – A list of cluster IDs, one per data point (as returned by
    `find_communities` or `connected_components`). Length must
    equal the number of nodes in `graph`.
  * **graph** – The graph used to derive community structure. Its node count
    must match `len(clusters)`.
  * **test_ratio** – Target fraction of data points to place in the test set.
    The actual fraction may differ slightly because clusters
    are indivisible. Defaults to `0.2`.
  * **seed** – Optional integer seed for reproducible cluster shuffling.
    Pass `None` for a random assignment.
  * **post_filtering** – If `True`, remove train nodes that share an edge with
    any test node (stricter leakage prevention at the
    cost of a smaller train set). Use only when clusters are found from
    communities (`find_communities`). It won’t have any effect when used with
    `connected_components` as this prevents inter-cluster connections.
* **Returns:**
  A tuple `(train_indices, test_indices)` of zero-based data-point indices.
* **Raises:**
  **ValueError** – If `clusters` length does not match `graph.n`, or if
      `test_ratio` is not in `(0, 1)`.

Example:

```default
from relag.core import (
    EdgeStore, CsrGraph, find_communities, partition, INWeightType
)

store = EdgeStore(6, [(0,1,0.9),(1,2,0.8),(3,4,0.7),(4,5,0.6)])
g = CsrGraph(store, inweight_type=INWeightType.Similarity)
clusters = find_communities(g) # or connected_components(g)
train_idx, test_idx = partition(clusters, g, test_ratio=0.3, seed=42)
```

## Exact search

### relag.core.exact_edges(variant: [kernels.KernelVariant](kernels.md#relag.kernels.KernelVariant), data: Any, proximity_threshold: float = 0.5, n_threads: int = 0, progress: bool = True, \*args: Any, \*\*kwargs: Any) → [EdgeStore](#relag.core.EdgeStore)

Compute all pairs of data points whose similarity exceeds a threshold (exact, brute-force).

Evaluates every unordered pair `(i, j)` with `i < j` and records an edge
when `kernel(data[i], data[j]) <= proximity_threshold`. This is O(n²) in the number
of data points; prefer the approximate\`\`HNSWState\`\` for large datasets.

Extra positional and keyword arguments are forwarded to the kernel constructor.

* **Parameters:**
  * **variant** – Which kernel to use (`KernelVariant.AlignmentGlobal` or
    `KernelVariant.AlignmentLocal`).
  * **data** – Sequence of data items (e.g. `list[str]` for protein sequences).
  * **proximity_threshold** – Maximum distance for an edge to be recorded.
  * **n_threads** – Number of parallel threads. `0` uses all available cores.
  * **progress** – Show a progress bar. Defaults to `True`.
* **Returns:**
  An `EdgeStore` containing all edges whose distance ≤ `proximity_threshold`.

Example:

```default
from relag import KernelVariant, exact_edges

seqs = ["MKTAYIAK", "MKTAYIAKQR", "ACDEFGHIKLM"]
store = exact_edges(KernelVariant.AlignmentGlobal, seqs, proximity_threshold=0.5)
print(len(store))   # number of similar pairs
```

### relag.core.exact_nearest_neighbors(variant: [kernels.KernelVariant](kernels.md#relag.kernels.KernelVariant), queries: Any, references: Any, k: int, threads: int = 0, progress: bool = True, \*args: Any, \*\*kwargs: Any) → list[list[tuple[int, float]]]

Find the k nearest neighbors of each query in a reference set (exact, brute-force).

For every query item, scores it against every reference item using the
chosen kernel and returns the top-k references sorted by ascending
distance. Complexity is O(n_queries × n_references); prefer
`HNSWState.search` for approximate nearest neighbors with large datasets.

Extra positional and keyword arguments are forwarded to the kernel constructor.

* **Parameters:**
  * **variant** – Which kernel to use (`KernelVariant.AlignmentGlobal` or
    `KernelVariant.AlignmentsLocal`).
  * **queries** – Sequence of query items.
  * **references** – Sequence of reference items to search over. List of items of the same type of the selected kernel variant.
  * **k** – Number of nearest neighbors to return per query. List of items of the same type of the selected kernel variant.
  * **threads** – Number of parallel threads. `0` uses all available cores.
  * **progress** – Show a progress bar. Defaults to `True`.
* **Returns:**
  A list of length `len(queries)`. Each element is a list of up to `k`
  tuples `(reference_index, similarity_score)` sorted by ascending distance.

Example:

```default
from relag import KernelVariant, exact_nearest_neighbors

queries = ["MKTAYIAK"]
refs    = ["MKTAYIAKQR", "ACDEFGHIKLM", "MKTAYIAKQRQ"]
results = exact_nearest_neighbors(
    KernelVariant.AlignmentGlobal, queries, refs, k=2
)
# results[0] -> [(0, 0.20), (2, 0.27)]
```


# kernels.html.md

# relag.kernels

## Kernel variant selector

### *class* relag.kernels.KernelVariant

Bases: `object`

#### AlignmentGlobal *= KernelVariant.AlignmentGlobal*

#### AlignmentLocal *= KernelVariant.AlignmentLocal*

#### Cosine *= KernelVariant.Cosine*

#### L1 *= KernelVariant.L1*

#### L2 *= KernelVariant.L2*

#### ProtSpam *= KernelVariant.ProtSpam*

#### Structure *= KernelVariant.Structure*

#### TanimotoBit *= KernelVariant.TanimotoBit*

#### TanimotoReal *= KernelVariant.TanimotoReal*

### relag.kernels.zip_kernel(variant: [KernelVariant](#relag.kernels.KernelVariant), data1: Any, data2: Any, n_threads: int = 0, progress: bool = True, \*args: Any, \*\*kwargs: Any) → list[float]

Compute pairwise kernel scores between two equal-length sequences of data items in parallel.

Evaluates `kernel(data1[i], data2[i])` for each index `i` and returns the scores
as a flat `list[float]` of length `len(data1)`.

Extra positional and keyword arguments are forwarded to the kernel constructor.

* **Parameters:**
  * **variant** – Which kernel to use.
  * **data1** – First sequence of items.
  * **data2** – Second sequence of items. Must have the same length as `data1`.
  * **n_threads** – Number of parallel threads. `0` uses all available cores.
  * **progress** – Show a progress bar. Defaults to `True`.
* **Returns:**
  A `list[float]` of length `len(data1)` where `result[i] = kernel(data1[i], data2[i])`.
* **Raises:**
  **ValueError** – If `data1` and `data2` have different lengths.

Example:

```default
from relag import KernelVariant
from relag.kernels import zip_kernel

seqs1 = ["MKTAYIAK", "ACDEFGHIKLM"]
seqs2 = ["MKTAYIAKQR", "ACDEF"]
scores = zip_kernel(KernelVariant.AlignmentGlobal, seqs1, seqs2)
# scores[i] == kernel(seqs1[i], seqs2[i])
```

## relag.kernels.alignments

Protein or Nucleotide sequence aligners and their configuration enums.

<a id="module-relag.kernels.alignments"></a>

### *class* relag.kernels.alignments.GlobalAligner(gap_open: int = 11, gap_extend: int = 1, matrix: [ScoringMatrix](#relag.kernels.alignments.ScoringMatrix) = ScoringMatrix.Blosum62, identity_mode: [GlobalIdentityMode](#relag.kernels.alignments.GlobalIdentityMode) = GlobalIdentityMode.MaxLength, vectorization: [VectorizationStrategy](#relag.kernels.alignments.VectorizationStrategy) = VectorizationStrategy.Scan, width: [DatatypeWidth](#relag.kernels.alignments.DatatypeWidth) = DatatypeWidth.Sat)

Bases: `object`

Needleman–Wunsch global sequence aligner returning a normalised identity score.

Wraps the parasail SIMD alignment library. The identity score is computed as
the number of identical aligned positions divided by the denominator selected
by `identity_mode`.

`GlobalAligner` is used as a kernel in `HNSWState`, `exact_edges`, and
`exact_nearest_neighbors` via `KernelVariant.AlignmentGlobal`.

* **Parameters:**
  * **gap_open** – Affine gap-open penalty (positive integer, subtracted). Default `11`.
  * **gap_extend** – Affine gap-extend penalty (positive integer, subtracted). Default `1`.
  * **matrix** – Amino-acid substitution matrix. Default `ScoringMatrix.Blosum62`.
  * **identity_mode** – Normalisation denominator. Default `GlobalIdentityMode.MaxLength`.
  * **vectorization** – SIMD layout. Default `VectorizationStrategy.Scan`.
  * **width** – Integer precision. Default `DatatypeWidth.Sat`.

Example:

```default
from relag.kernels.alignments import GlobalAligner

aligner = GlobalAligner(gap_open=11, gap_extend=1)
score = aligner.call("MKTAYIAK", "MKTAYIAKQR")
score = aligner("MKTAYIAK", "MKTAYIAKQR") # Alternative
# score in [0.0, 1.0]
```

#### call(ref_sample: str, query: str) → float

Compute the global alignment identity between two sequences.

* **Parameters:**
  * **ref_sample** – Reference sequence (single-letter amino acid codes or nucleotides).
  * **query** – Query sequence.
* **Returns:**
  Identity score in `[0.0, 1.0]`.

### *class* relag.kernels.alignments.LocalAligner(gap_open: int = 11, gap_extend: int = 1, min_coverage: float = 0.800000011920929, cov_mode: [CoverageMode](#relag.kernels.alignments.CoverageMode) = CoverageMode.BothQueryTarget, matrix: [ScoringMatrix](#relag.kernels.alignments.ScoringMatrix) = ScoringMatrix.Blosum62, identity_mode: [LocalIdentityMode](#relag.kernels.alignments.LocalIdentityMode) = LocalIdentityMode.AlignmentLength, vectorization: [VectorizationStrategy](#relag.kernels.alignments.VectorizationStrategy) = VectorizationStrategy.Striped, width: [DatatypeWidth](#relag.kernels.alignments.DatatypeWidth) = DatatypeWidth.Sat)

Bases: `object`

Smith–Waterman local sequence aligner returning a normalised identity score.

Like `GlobalAligner` but aligns only the most similar sub-region of each
sequence. Pairs that do not meet the `min_coverage` criterion after alignment
receive a score of `0.0`.

`LocalAligner` is used as a kernel via `KernelVariant.AlignmentLocal`.

* **Parameters:**
  * **gap_open** – Affine gap-open penalty. Default `11`.
  * **gap_extend** – Affine gap-extend penalty. Default `1`.
  * **min_coverage** – Minimum fraction of sequence covered by the local alignment
    (per `cov_mode`) for the pair to be accepted. Default `0.8`.
  * **cov_mode** – Which sequence(s) must meet `min_coverage`. Default
    `CoverageMode.BothQueryTarget`.
  * **matrix** – Substitution matrix. Default `ScoringMatrix.Blosum62`.
  * **identity_mode** – Normalisation denominator. Default `LocalIdentityMode.AlignmentLength`.
  * **vectorization** – SIMD layout. Default `VectorizationStrategy.Striped`.
  * **width** – Integer precision. Default `DatatypeWidth.Sat`.

Example:

```default
from relag.kernels.alignments import LocalAligner, CoverageMode

aligner = LocalAligner(min_coverage=0.5, cov_mode=CoverageMode.Query)
score = aligner.call("ACDEFGHIKLM", "CDEFGHI")
score = aligner("ACDEFGHIKLM", "CDEFGHI") # Alternative
```

#### call(ref_sample: str, query: str) → float

Compute the local alignment identity between two sequences.

* **Parameters:**
  * **ref_sample** – Reference alignments sequence (single-letter amino acid codes).
  * **query** – Query alignments sequence.
* **Returns:**
  Identity score in `[0.0, 1.0]`, or `1.0` if the coverage filter fails.

### *class* relag.kernels.alignments.ScoringMatrix

Bases: `object`

#### Blosum100 *= ScoringMatrix.Blosum100*

#### Blosum30 *= ScoringMatrix.Blosum30*

#### Blosum35 *= ScoringMatrix.Blosum35*

#### Blosum40 *= ScoringMatrix.Blosum40*

#### Blosum45 *= ScoringMatrix.Blosum45*

#### Blosum50 *= ScoringMatrix.Blosum50*

#### Blosum55 *= ScoringMatrix.Blosum55*

#### Blosum60 *= ScoringMatrix.Blosum60*

#### Blosum62 *= ScoringMatrix.Blosum62*

#### Blosum65 *= ScoringMatrix.Blosum65*

#### Blosum70 *= ScoringMatrix.Blosum70*

#### Blosum75 *= ScoringMatrix.Blosum75*

#### Blosum80 *= ScoringMatrix.Blosum80*

#### Blosum85 *= ScoringMatrix.Blosum85*

#### Blosum90 *= ScoringMatrix.Blosum90*

#### Blosum95 *= ScoringMatrix.Blosum95*

#### Dnafull *= ScoringMatrix.Dnafull*

#### Identity *= ScoringMatrix.Identity*

#### Nuc44 *= ScoringMatrix.Nuc44*

#### Pam10 *= ScoringMatrix.Pam10*

#### Pam100 *= ScoringMatrix.Pam100*

#### Pam110 *= ScoringMatrix.Pam110*

#### Pam120 *= ScoringMatrix.Pam120*

#### Pam130 *= ScoringMatrix.Pam130*

#### Pam140 *= ScoringMatrix.Pam140*

#### Pam150 *= ScoringMatrix.Pam150*

#### Pam160 *= ScoringMatrix.Pam160*

#### Pam170 *= ScoringMatrix.Pam170*

#### Pam180 *= ScoringMatrix.Pam180*

#### Pam190 *= ScoringMatrix.Pam190*

#### Pam20 *= ScoringMatrix.Pam20*

#### Pam200 *= ScoringMatrix.Pam200*

#### Pam210 *= ScoringMatrix.Pam210*

#### Pam220 *= ScoringMatrix.Pam220*

#### Pam230 *= ScoringMatrix.Pam230*

#### Pam240 *= ScoringMatrix.Pam240*

#### Pam250 *= ScoringMatrix.Pam250*

#### Pam260 *= ScoringMatrix.Pam260*

#### Pam270 *= ScoringMatrix.Pam270*

#### Pam280 *= ScoringMatrix.Pam280*

#### Pam290 *= ScoringMatrix.Pam290*

#### Pam30 *= ScoringMatrix.Pam30*

#### Pam300 *= ScoringMatrix.Pam300*

#### Pam310 *= ScoringMatrix.Pam310*

#### Pam320 *= ScoringMatrix.Pam320*

#### Pam330 *= ScoringMatrix.Pam330*

#### Pam340 *= ScoringMatrix.Pam340*

#### Pam350 *= ScoringMatrix.Pam350*

#### Pam360 *= ScoringMatrix.Pam360*

#### Pam370 *= ScoringMatrix.Pam370*

#### Pam380 *= ScoringMatrix.Pam380*

#### Pam390 *= ScoringMatrix.Pam390*

#### Pam40 *= ScoringMatrix.Pam40*

#### Pam400 *= ScoringMatrix.Pam400*

#### Pam410 *= ScoringMatrix.Pam410*

#### Pam420 *= ScoringMatrix.Pam420*

#### Pam430 *= ScoringMatrix.Pam430*

#### Pam440 *= ScoringMatrix.Pam440*

#### Pam450 *= ScoringMatrix.Pam450*

#### Pam460 *= ScoringMatrix.Pam460*

#### Pam470 *= ScoringMatrix.Pam470*

#### Pam480 *= ScoringMatrix.Pam480*

#### Pam490 *= ScoringMatrix.Pam490*

#### Pam50 *= ScoringMatrix.Pam50*

#### Pam500 *= ScoringMatrix.Pam500*

#### Pam60 *= ScoringMatrix.Pam60*

#### Pam70 *= ScoringMatrix.Pam70*

#### Pam80 *= ScoringMatrix.Pam80*

#### Pam90 *= ScoringMatrix.Pam90*

### *class* relag.kernels.alignments.GlobalIdentityMode

Bases: `object`

Denominator used to normalise a global-alignments identity score.

After counting identical aligned positions the raw count is divided by:

- `AlignmentLength`: the total length of the alignment (including gaps).
- `MaxSeqLength`: the length of the longer of the two sequences.
- `MinSeqLength`: the length of the shorter of the two sequences.
- `MaxLength` (default): same as `MaxSeqLength` — recommended for RGP datasets.

#### AlignmentLength *= GlobalIdentityMode.AlignmentLength*

#### MaxLength *= GlobalIdentityMode.MaxLength*

#### MaxSeqLength *= GlobalIdentityMode.MaxSeqLength*

#### MinSeqLength *= GlobalIdentityMode.MinSeqLength*

### *class* relag.kernels.alignments.VectorizationStrategy

Bases: `object`

SIMD vectorization layout used by the parasail alignment engine.

- `Striped` (default for local): interleaved layout, best for short sequences.
- `Scan`: sequential scan layout, often faster for long sequences or global alignment.
- `Diag`: diagonal layout; niche use-case, rarely needed.

In practice the default per-aligner is a good choice; change only if profiling
shows a bottleneck.

#### Diag *= VectorizationStrategy.Diag*

#### Scan *= VectorizationStrategy.Scan*

#### Striped *= VectorizationStrategy.Striped*

### *class* relag.kernels.alignments.DatatypeWidth

Bases: `object`

Integer precision used for alignment score accumulation.

- `Short` (8-bit), `Half` (16-bit), `Full` (32-bit), `Long` (64-bit):
  fixed-width integers — lower width is faster but can overflow on long sequences.
- `Sat` (default): 8-bit saturating arithmetic; If it saturates, silently restart with 16-bit.

#### Full *= DatatypeWidth.Full*

#### Half *= DatatypeWidth.Half*

#### Long *= DatatypeWidth.Long*

#### Sat *= DatatypeWidth.Sat*

#### Short *= DatatypeWidth.Short*

### *class* relag.kernels.alignments.CoverageMode

Bases: `object`

Coverage filter applied before accepting a local alignment as valid.

A pair is scored only when the alignment covers enough of the sequences
as specified by the mode and `min_coverage` threshold:

- `BothQueryTarget` (default): both query and target must meet `min_coverage`.
- `Target`: only the target must meet `min_coverage`.
- `Query`: only the query must meet `min_coverage`.
- `LengthRatio`: the shorter / longer length ratio must meet `min_coverage`.
- `ShorterSeq`: coverage computed relative to the shorter sequence.

#### BothQueryTarget *= CoverageMode.BothQueryTarget*

#### LengthRatio *= CoverageMode.LengthRatio*

#### Query *= CoverageMode.Query*

#### ShorterSeq *= CoverageMode.ShorterSeq*

#### Target *= CoverageMode.Target*

### *class* relag.kernels.alignments.LocalIdentityMode

Bases: `object`

Denominator used to normalise a local-alignment identity score.

- `AlignmentLength` (default): divide by the length of the local alignment.
- `MinSeqLength`: divide by the shorter sequence length.

#### AlignmentLength *= LocalIdentityMode.AlignmentLength*

#### MinSeqLength *= LocalIdentityMode.MinSeqLength*

## relag.kernels.molecules

Molecules Tanimoto kernels.

<a id="module-relag.kernels.molecules"></a>

### *class* relag.kernels.molecules.TanimotoBit

Bases: `object`

Tanimoto distance kernel for binary (bit) molecular fingerprints.

Measures structural dissimilarity between two molecules as the complement of
the Jaccard index over their feature sets. A distance of 0 means the two
fingerprints are identical; 1 means they share no features at all.

Formula: `1 - |A ∩ B| / |A ∪ B|`

This kernel is the standard choice when working with `ExplicitBitVect`
fingerprints such as Morgan, RDKit, or MACCS keys.

Example:

```default
from rdkit.Chem import MolFromSmiles, rdFingerprintGenerator
from relag.utils import BitFingerprint
from relag.kernels.molecules import TanimotoBit

mfpgen = rdFingerprintGenerator.GetMorganGenerator(fpSize=1024, radius=2)
benzene    = BitFingerprint(mfpgen.GetFingerprint(MolFromSmiles("c1ccccc1")))
naphthalene = BitFingerprint(mfpgen.GetFingerprint(MolFromSmiles("c1ccc2ccccc2c1")))
acetic_acid = BitFingerprint(mfpgen.GetFingerprint(MolFromSmiles("CC(=O)O")))

k = TanimotoBit()
print(k(benzene, naphthalene))  # low  — structurally similar
print(k(benzene, acetic_acid))  # high — structurally dissimilar
```

#### call(a: [utils.BitFingerprint](utils.md#relag.utils.BitFingerprint), b: [utils.BitFingerprint](utils.md#relag.utils.BitFingerprint)) → float

Compute the Tanimoto distance between two `BitFingerprint` objects.

* **Parameters:**
  * **a** – First fingerprint.
  * **b** – Second fingerprint.
* **Returns:**
  Distance in `[0.0, 1.0]`. `0.0` means identical feature sets,
  `1.0` means fully disjoint.

Example:

```default
from relag.utils import BitFingerprint
from relag.kernels.molecules import TanimotoBit

fp1 = BitFingerprint.from_list([True, False, True, True])
fp2 = BitFingerprint.from_list([True, True,  True, False])
k = TanimotoBit()
assert k.call(fp1, fp2) == k(fp1, fp2)  # both forms are equivalent
# intersection={0,2}=2, union={0,1,2,3}=4 → distance = 0.5
```

### *class* relag.kernels.molecules.TanimotoReal

Bases: `object`

Tanimoto distance kernel for real-valued (count) molecular fingerprints.

Generalises the binary Tanimoto to continuous feature vectors using the
dot-product formulation. A distance of 0 means the two fingerprints are
proportional; values approach 1 as the vectors become orthogonal.

Formula: `1 - dot(a, b) / (||a||² + ||b||² - dot(a, b))`

This kernel is the standard choice when working with count fingerprints
such as those returned by `GetCountFingerprint` (Morgan counts, etc.).

Example:

```default
from rdkit.Chem import MolFromSmiles, rdFingerprintGenerator
from relag.utils import RealFingerprint
from relag.kernels.molecules import TanimotoReal

mfpgen = rdFingerprintGenerator.GetMorganGenerator(fpSize=1024, radius=2)
benzene     = RealFingerprint(mfpgen.GetCountFingerprint(MolFromSmiles("c1ccccc1")))
naphthalene = RealFingerprint(mfpgen.GetCountFingerprint(MolFromSmiles("c1ccc2ccccc2c1")))
acetic_acid = RealFingerprint(mfpgen.GetCountFingerprint(MolFromSmiles("CC(=O)O")))

k = TanimotoReal()
print(k(benzene, naphthalene))  # low  — structurally similar
print(k(benzene, acetic_acid))  # high — structurally dissimilar
```

#### call(a: [utils.RealFingerprint](utils.md#relag.utils.RealFingerprint), b: [utils.RealFingerprint](utils.md#relag.utils.RealFingerprint)) → float

Compute the Tanimoto distance between two `RealFingerprint` objects.

* **Parameters:**
  * **a** – First fingerprint.
  * **b** – Second fingerprint.
* **Returns:**
  Distance in `[0.0, 1.0]`. `0.0` means identical (proportional)
  feature vectors, `1.0` means fully orthogonal.

Example:

```default
from relag.utils import RealFingerprint
from relag.kernels.molecules import TanimotoReal

fp1 = RealFingerprint.from_list([1.0, 0.0, 1.0])
fp2 = RealFingerprint.from_list([0.0, 1.0, 1.0])
k = TanimotoReal()
assert k.call(fp1, fp2) == k(fp1, fp2)  # both forms are equivalent
# dot=1, ||fp1||²=2, ||fp2||²=2 → distance = 1 - 1/(2+2-1) ≈ 0.667
```

## relag.kernels.structures

Protein structure kernels (USalign TM-score).

<a id="module-relag.kernels.structures"></a>

### *class* relag.kernels.structures.USAlignKernel(norm_mode: [NormMode](#relag.kernels.structures.NormMode) = NormMode.Min, fast: bool = True)

Bases: `object`

Protein structure comparison kernel using USalign TM-score.

Operates on pre-loaded `PdbStructure` objects (from `relag.utils`).
Returns `1.0 - TM-score` so that identical structures have distance 0
and unrelated structures have distance approaching 1.

Example:

```default
from relag.utils import PdbStructure
from relag.kernels.structures import USAlignKernel, NormMode

s1 = PdbStructure("1abc.pdb")
s2 = PdbStructure("1xyz.pdb")
k  = USAlignKernel()                  # default: NormMode.Min
d  = k(s1, s2)                         # float in [0, 1]
```

#### call(a: [utils.PdbStructure](utils.md#relag.utils.PdbStructure), b: [utils.PdbStructure](utils.md#relag.utils.PdbStructure)) → float

Compute the structure distance between two `PdbStructure` objects.

* **Parameters:**
  * **a** – First structure.
  * **b** – Second structure.
* **Returns:**
  Distance in `[0.0, 1.0]`. `0.0` means structurally identical,
  values near `1.0` indicate unrelated folds.

### *class* relag.kernels.structures.NormMode

Bases: `object`

TM-score normalization strategy.

USalign returns two scores per alignment:

- `TM1`: normalized by the length of the first structure (query).
- `TM2`: normalized by the length of the second structure (target).
- `Min` (default): `min(TM1, TM2)` — conservative, symmetric.
- `Query`: use `TM1` only.
- `Target`: use `TM2` only.

#### Min *= NormMode.Min*

#### Query *= NormMode.Query*

#### Target *= NormMode.Target*

## relag.kernels.protspam

ProtSpaM-style spaced-word kernel for protein sequences.

<a id="module-relag.kernels.protspam"></a>

### *class* relag.kernels.protspam.ProtSpamKernel(patterns: [utils.SWPatternSet](utils.md#relag.utils.SWPatternSet), significance_threshold: int = 0, distance: [ProtSpamDistance](#relag.kernels.protspam.ProtSpamDistance) = ProtSpamDistance.Evolutionary)

Bases: `object`

Distance between two `SWSequence`, ProtSpaM-style: for each pattern in a
shared `SWPatternSet`, match spaced words by key (grouping ties into “blocks”),
score the best-aligned spaced word pair within each matching block against
BLOSUM62, and pool mismatches at don’t-care positions into a mismatch rate.
Reports either that raw rate or a Kimura-corrected evolutionary distance, per
`distance`.

Every `SWSequence` passed to `call` must have been built from the same
`SWPatternSet` as this kernel’s `patterns()` (or an equal copy of it).

Example:

```default
from relag.kernels.protspam import ProtSpamKernel, ProtSpamDistance
from relag.utils import SWPatternSet, SWSequence

sequences = [
    "MKTAYIAKQRQISFVKSHFSRQLEERLGLIEVQAPILSRVGDGTQDNLSGAEK",
    "MKTAYIAKQRQISFVKSHFSRQLEERLGLIEVQAPILSRVGDGTQDNLSGAEA",
]

# A RasBhari-optimized pattern set, shared by every SWSequence and the kernel.
patterns = SWPatternSet(5, 6, 20)

swseqs = [SWSequence(s, patterns) for s in sequences]

kernel = ProtSpamKernel(patterns, distance=ProtSpamDistance.Evolutionary)
distance = kernel.call(swseqs[0], swseqs[1])
distance = kernel(swseqs[0], swseqs[1])  # equivalent -- kernel(a, b) syntax
assert distance >= 0.0
```

#### call(ref_sample: [utils.SWSequence](utils.md#relag.utils.SWSequence), query: [utils.SWSequence](utils.md#relag.utils.SWSequence)) → float

Compute the distance between `ref_sample` and `query`, per this kernel’s
`distance()` mode.

* **Parameters:**
  * **ref_sample** – Reference sequence. Must have been built from the same
    `SWPatternSet` as this kernel’s `patterns()`.
  * **query** – Query sequence. Same requirement.
* **Returns:**
  The distance – see `ProtSpamDistance`.

Panics:
: `ref_sample`/`query` must have been built from the same
  `SWPatternSet` as this kernel’s `patterns()`. If they weren’t, this
  can panic (index out of range, if the mismatched set has fewer patterns)
  or – more insidiously – silently compare the wrong patterns’ spaced
  words against each other with no panic at all, if the mismatched set
  merely has a different pattern at the same index.

#### distance() → [ProtSpamDistance](#relag.kernels.protspam.ProtSpamDistance)

Which value `call` reports.

#### patterns() → [utils.SWPatternSet](utils.md#relag.utils.SWPatternSet)

The shared pattern set spaced words are matched against.

#### significance_threshold() → int

Minimum BLOSUM62 score for a spaced-word match to be considered homologous.

### *class* relag.kernels.protspam.ProtSpamDistance

Bases: `object`

Which distance `ProtSpamKernel.call` reports.

- `MismatchRate`: the raw mismatch rate itself (fraction of don’t-care
  positions that mismatch, pooled across every pattern’s accepted spaced-word
  matches) – always in `[0, 1]`. `1.0` if no spaced word matched at all, or
  if every accepted match’s don’t-care positions mismatched outright.
- `Evolutionary`: the mismatch rate corrected into a distance via the Kimura
  two-parameter formula – in `[0, inf]`. `inf` if the mismatch rate is
  undefined (no match at all) or high enough (`> ~0.8541`) that the
  correction’s log argument is non-positive.

#### Evolutionary *= ProtSpamDistance.Evolutionary*

#### MismatchRate *= ProtSpamDistance.MismatchRate*

## relag.kernels.vectors

Vector distance kernels.

<a id="module-relag.kernels.vectors"></a>

### *class* relag.kernels.vectors.Cosine

Bases: `object`

Cosine distance: `1 - dot(a, b) / (||a|| * ||b||)`. `0.0` if either vector
is the zero vector.

Example:

```default
import numpy as np
from relag.kernels.vectors import Cosine

a = np.array([1.0, 0.0], dtype=np.float32)
b = np.array([0.0, 1.0], dtype=np.float32)
k = Cosine()
assert k.call(a, b) == k(a, b) == 1.0
```

#### call(a: numpy.typing.NDArray[numpy.float32], b: numpy.typing.NDArray[numpy.float32]) → float

Compute the cosine distance between two 1D `float32` numpy arrays.

Reads directly from each array’s buffer – no copy.

* **Parameters:**
  * **a** – First vector.
  * **b** – Second vector.
* **Returns:**
  Distance in `[0.0, 2.0]`. `0.0` means the same direction, `2.0`
  means exactly opposite directions.

### *class* relag.kernels.vectors.L1

Bases: `object`

Manhattan (L1) distance: `sum(|a_i - b_i|)`.

Example:

```default
import numpy as np
from relag.kernels.vectors import L1

a = np.array([1.0, 2.0, 3.0], dtype=np.float32)
b = np.array([4.0, 0.0, 3.0], dtype=np.float32)
k = L1()
assert k.call(a, b) == k(a, b) == 5.0
```

#### call(a: numpy.typing.NDArray[numpy.float32], b: numpy.typing.NDArray[numpy.float32]) → float

Compute the L1 distance between two 1D `float32` numpy arrays.

Reads directly from each array’s buffer – no copy.

* **Parameters:**
  * **a** – First vector.
  * **b** – Second vector.
* **Returns:**
  Distance in `[0.0, inf]`. `0.0` means identical vectors.

### *class* relag.kernels.vectors.L2

Bases: `object`

Euclidean (L2) distance: `sqrt(sum((a_i - b_i)²))`.

Example:

```default
import numpy as np
from relag.kernels.vectors import L2

a = np.array([0.0, 0.0], dtype=np.float32)
b = np.array([3.0, 4.0], dtype=np.float32)
k = L2()
assert k.call(a, b) == k(a, b) == 5.0
```

#### call(a: numpy.typing.NDArray[numpy.float32], b: numpy.typing.NDArray[numpy.float32]) → float

Compute the L2 distance between two 1D `float32` numpy arrays.

Reads directly from each array’s buffer – no copy.

* **Parameters:**
  * **a** – First vector.
  * **b** – Second vector.
* **Returns:**
  Distance in `[0.0, inf]`. `0.0` means identical vectors.


# utils.html.md

# relag.utils

### *class* relag.utils.BitFingerprint(fp: ExplicitBitVect)

Bases: `object`

Dense binary fingerprint backed by a dense bitset.

Each bit represents the presence or absence of a structural feature.
The primary source is an RDKit `ExplicitBitVect` (from `GetFingerprint`),
but plain Python lists and numpy arrays are also accepted.

`count` caches the popcount so Tanimoto computation avoids re-counting.

Example:

```default
from rdkit.Chem import rdFingerprintGenerator, MolFromSmiles
from relag.utils import BitFingerprint

mfpgen = rdFingerprintGenerator.GetMorganGenerator(fpSize=1024, radius=2)
mol = MolFromSmiles("c1ccccc1")
fp = BitFingerprint(mfpgen.GetFingerprint(mol))
print(fp.count(), len(fp))   # set bits, total bits
```

#### count() → int

Number of on bits (popcount).

#### *static* from_list(values: Sequence[bool]) → [BitFingerprint](#relag.utils.BitFingerprint)

Construct from a list of booleans (or 0/1 ints).

#### *static* from_np(arr: numpy.typing.NDArray[numpy.bool_]) → [BitFingerprint](#relag.utils.BitFingerprint)

Construct from a numpy boolean or uint8 array.

For uint8/bool dtypes, reads the array’s raw buffer directly – a zero-copy
view into memory numpy already owns – and sets bits from it in one pass, with no
per-element Python object boxing. Any other dtype falls back to .tolist() +
from_list, which does box each element as an individual Python object along the
way; this covers arbitrary array-likes at the cost of that boxing.

#### *static* random(len: int, count: int) → [BitFingerprint](#relag.utils.BitFingerprint)

Create a fingerprint of `len` bits with exactly `count` bits set at random.

Useful for randomized testing.

* **Parameters:**
  * **len** – Total number of bits.
  * **count** – Number of bits to turn on. Must be `<= len`.
* **Raises:**
  **ValueError** – If `count > len`.

#### to_list() → list[bool]

Export as a list of booleans.

#### to_np() → numpy.typing.NDArray[numpy.bool_]

Export as a numpy bool array.

#### to_rdkit() → ExplicitBitVect

Export as an RDKit `ExplicitBitVect`.

#### fp *: ExplicitBitVect*

#### return *: [BitFingerprint](#relag.utils.BitFingerprint)*

### *class* relag.utils.RealFingerprint(fp: UIntSparseIntVect)

Bases: `object`

Dense real-valued fingerprint backed by a `Vec<f32>`.

Each element represents a feature count or continuous value. The primary
source is an RDKit `UIntSparseIntVect` (from `GetCountFingerprint`),
but plain Python lists and numpy arrays are also accepted.

`norm_sq` caches `||x||²` so Tanimoto computation avoids recomputing it.

Example:

```default
from rdkit.Chem import rdFingerprintGenerator, MolFromSmiles
from relag.utils import RealFingerprint
from relag.kernels.molecules import TanimotoReal

mfpgen = rdFingerprintGenerator.GetMorganGenerator(fpSize=1024, radius=2)
mol = MolFromSmiles("c1ccccc1")
fp = RealFingerprint(mfpgen.GetCountFingerprint(mol))
print(fp.norm_sq(), len(fp))
```

#### *static* from_list(values: Sequence[float]) → [RealFingerprint](#relag.utils.RealFingerprint)

Construct from a list of floats.

#### *static* from_np(arr: numpy.typing.NDArray[numpy.float32]) → [RealFingerprint](#relag.utils.RealFingerprint)

Construct from a numpy float32 or float64 array.

#### norm_sq() → float

Squared Euclidean norm of the feature vector (`||x||²`).

#### to_list() → list[float]

Export as a list of floats.

#### to_np() → numpy.typing.NDArray[numpy.float32]

Export as a numpy float32 array.

#### to_rdkit() → UIntSparseIntVect

Export as an RDKit `UIntSparseIntVect`, compatible with `GetCountFingerprint`.
Only non-zero elements are stored; the length equals `len(self)`.

#### fp *: UIntSparseIntVect*

#### return *: [RealFingerprint](#relag.utils.RealFingerprint)*

### *class* relag.utils.Vector(values: Any)

Bases: `object`

A dense `f32` vector, used by the `relag.kernels.vectors` kernels (`Cosine`,
`EluDot`, `L1`, `L2`). Backed by a plain `Vec<f32>` – unlike
`RealFingerprint`, there’s no precomputed cache.

Example:

```default
import numpy as np
from relag.utils import Vector

v = Vector(np.array([1.0, 2.0, 3.0], dtype=np.float32))
print(len(v))
```

#### *static* from_list(values: Sequence[float]) → [Vector](#relag.utils.Vector)

Construct from a list of floats.

#### *static* from_np(arr: Any) → [Vector](#relag.utils.Vector)

Construct from a numpy float32 array, reading its buffer directly. Falls back
to `.tolist()` for other dtypes.

#### to_list() → list[float]

Export as a list of floats.

#### to_np() → numpy.typing.NDArray[numpy.float32]

Export as a numpy float32 array.

#### values *: Any*

#### return *: [Vector](#relag.utils.Vector)*

### *class* relag.utils.PdbStructure(path: str)

Bases: `object`

A protein structure loaded from a PDB file and held in memory.

The structure is parsed once on construction and the coordinate arrays are
kept alive for the lifetime of the object. Cloning is cheap (reference-counted).

Example:

```default
from relag.utils import PdbStructure
s = PdbStructure("1abc.pdb")
```

#### path *: str*

#### return *: [PdbStructure](#relag.utils.PdbStructure)*

### relag.utils.read_fasta(path: str) → list[tuple[str, str]]

Parse a FASTA file and return all records as a list of `(header, sequence)` pairs.

The header string is the full description line without the leading `>`.
The sequence is the concatenation of all continuation lines for that record,
with whitespace stripped.

* **Parameters:**
  **path** – Path to the FASTA file.
* **Returns:**
  A list of `(header, sequence)` tuples, one per FASTA record.
* **Raises:**
  **IOError** – If the file cannot be opened or is not valid UTF-8.

Example:

```default
from relag.utils import read_fasta

records = read_fasta("proteins.fasta")
header, seq = records[0]
print(header)  # "sp|P12345|MYPR_HUMAN ..."
print(seq)     # "MKTAYIAKQRQISFVKSHFSRQ..."
```

### relag.utils.largest_cluster(clusters: Sequence[int]) → tuple[int, int]

Return the ID and size of the largest cluster.

Convenience helper — iterates over a cluster-label vector and finds the
most populous label.

* **Parameters:**
  **clusters** – A list of cluster IDs (e.g. from `connected_components` or
  `find_communities`).
* **Returns:**
  A tuple `(cluster_id, size)` for the largest cluster.

### *class* relag.utils.SWPattern(weight: int, dont_care: int)

Bases: `object`

A spaced-word pattern: a binary mask over length positions where a match position
(“1”) contributes a residue to the spaced word’s key and a don’t-care position (“0”)
is skipped when hashing but still compared for mismatches. Position 0 and the last
position are always match positions.

Example:

```default
from relag.utils import SWPattern

pat = SWPattern(6, 20)
assert len(pat) == 26
assert pat.weight() == 6
assert pat.dontcare() == 20
assert pat.is_match(0)
assert pat.is_match(25)

# Parse/render as a string of '1's (match) and '0's (don't-care)
pat2 = SWPattern.parse("10100101")
assert pat2.weight() == 4
assert str(pat2) == "10100101"
```

#### dontcare() → int

Number of don’t-care (“0”) positions.

#### is_match(pos: int) → bool

Whether `pos` is a match position. Never raises: an out-of-range `pos`
simply reads as `False`.

#### match_positions() → list[int]

Ascending indices of match (“1”) positions.

#### *static* parse(s: str) → [SWPattern](#relag.utils.SWPattern)

Parse a pattern from a string of `'1'``s (match) and ``'0'``s (don't-care),
the same format ``str()` produces.

* **Raises:**
  **ValueError** – If the string contains a character other than `'0'`/`'1'`,
      or doesn’t start and end with `'1'`.

#### weight() → int

Number of match (“1”) positions.

#### dont_care *: int*

#### return *: [SWPattern](#relag.utils.SWPattern)*

### *class* relag.utils.SWPatternSet(n: int, weight: int, dont_care: int)

Bases: `object`

A set of 

```
``
```

SWPattern\`\`s used together to compute spaced words for a sequence.

The default constructor builds a RasBhari-optimized set (recommended for real
use); use `SWPatternSet.random` for a cheap, unoptimized set, or
`SWPatternSet.from_patterns` to build one from hand-picked patterns.

Example:

```default
from relag.utils import SWPatternSet

# RasBhari-optimized (recommended)
patterns = SWPatternSet(5, 6, 20)
assert len(patterns) == 5

# Cheap, unoptimized baseline, refined by hand
random_patterns = SWPatternSet.random(5, 6, 20)
score_before = random_patterns.optimize(0)    # limit=0: score only, no changes
score_after = random_patterns.optimize(2000)
assert score_after <= score_before
```

#### *static* from_patterns(patterns: Sequence[[SWPattern](#relag.utils.SWPattern)]) → [SWPatternSet](#relag.utils.SWPatternSet)

Build a set from already-constructed patterns. Unlike `random`, there’s no uniqueness check – duplicate
patterns are allowed, though they add nothing (two identical patterns always
find exactly the same matches).

#### *static* load(path: str) → [SWPatternSet](#relag.utils.SWPatternSet)

Deserialize a set previously written by `save`.

* **Raises:**
  **IOError** – If `path` can’t be read, or its contents aren’t a valid pattern set.

#### optimize(limit: int) → float

Optimize this pattern set in place with RasBhari’s overlap-complexity hill
climbing: repeatedly picks a pattern round-robin, swaps one of its interior
match positions for a don’t-care position, and keeps the change only if it
strictly lowers the set’s total pairwise overlap-complexity score.

* **Parameters:**
  **limit** – Number of hill-climbing steps to run. Pass `0` to just compute
  and return the current score without changing anything.
* **Returns:**
  The achieved overlap-complexity score after optimizing (lower is better).

#### patterns() → list[[SWPattern](#relag.utils.SWPattern)]

The patterns in this set, in construction order.

#### *static* random(n: int, weight: int, dont_care: int) → [SWPatternSet](#relag.utils.SWPatternSet)

Build `n` distinct unoptimized random patterns of the given
`weight`/`dont_care`. Useful as a cheap baseline, or as the unoptimized
starting point `optimize` refines.

#### WARNING
Patterns are generated by rejection sampling on uniqueness, so this hangs
(never returns) if `n` isn’t well below the number of distinct patterns
possible for `weight`/`dont_care` (`C(weight + dont_care - 2, weight - 2)`).
This is sharpest at `weight == 2`: there are no interior positions to
vary at all, so every generated pattern is identical and any `n > 1`
hangs immediately.

#### save(path: str) → None

Serialize this set to `path`. Inverse of `load`.

* **Raises:**
  **IOError** – If `path` can’t be written.

#### *static* with_limit(n: int, weight: int, dont_care: int, limit: int) → [SWPatternSet](#relag.utils.SWPatternSet)

Same as the default constructor, but with an explicit hill-climbing step
budget instead of ProtSpaM’s default of 25,000.

#### n *: int*

#### weight *: int*

#### dont_care *: int*

#### return *: [SWPatternSet](#relag.utils.SWPatternSet)*

### *class* relag.utils.SWSequence(seq: str, patterns: [SWPatternSet](#relag.utils.SWPatternSet))

Bases: `object`

A sequence prepared for spaced-word comparison (ProtSpaM-style). Its residues are
pre-encoded as 5-bit amino-acid codes, and it holds the sorted spaced words for
every pattern in the `SWPatternSet` it was built with.

Two `SWSequence``s must be built from the same ``SWPatternSet` (or two equal
copies of it) to be compared meaningfully – see
`relag.kernels.protspam.ProtSpamKernel`, which is what actually compares two of
these.

Picklable: `pickle.dumps`/`pickle.loads` round-trip an `SWSequence` without
needing the original pattern set again (its encoded residues and sorted spaced
words are serialized directly).

Example:

```default
import pickle
from relag.utils import SWPatternSet, SWSequence

patterns = SWPatternSet(5, 6, 20)
seq = SWSequence("MKTAYIAKQRQISFVKSHFSRQ", patterns)
assert len(seq) == 22

restored = pickle.loads(pickle.dumps(seq))
assert restored.seq() == seq.seq()
```

#### pattern_count() → int

Number of patterns this sequence has spaced words for – the `len()` of the
`SWPatternSet` it was built with. Valid indices for `sorted_words` are
`0 .. pattern_count()`.

#### seq() → list[int]

Residues as 5-bit amino-acid codes, not raw ASCII – e.g. `'A'` reads back
as `0`, not `65`.

#### sorted_words(pattern_idx: int) → list[[SWWord](#relag.utils.SWWord)]

Sorted spaced words for `patterns.patterns()[pattern_idx]`, where
`patterns` is the set this sequence was built with. Empty if this sequence
is shorter than that pattern (no window fits).

* **Raises:**
  **IndexError** – If `pattern_idx` is out of range for the pattern set this
      sequence was built with.

#### patterns *: [SWPatternSet](#relag.utils.SWPatternSet)*

#### return *: [SWSequence](#relag.utils.SWSequence)*

### *class* relag.utils.SWWord

Bases: `object`

One complete spaced word: the residues at a pattern’s match positions.

Example:

```default
from relag.utils import SWPatternSet, SWSequence

patterns = SWPatternSet.random(1, 2, 1)  # single pattern, weight 2, dc 1 -> "101"
seq = SWSequence("ACDE", patterns)
words = seq.sorted_words(0)
assert all(words[i].key() <= words[i + 1].key() for i in range(len(words) - 1))
```

#### key() → int

The packed key: the pattern’s match-position residues, 5 bits each,
most-significant residue first.

#### pos() → int

Start position of this word’s window in the sequence it came from.