current clustering use > 60 hours to run on 80,000 sequenes.
What clustering does in SBOLExplorer — and can a hash replace it?
Role of clustering
The clusters map (which parts are similar to which) is produced by cluster.update_clusters() (the slow vsearch cluster_fast step) and used in two places:
Rank de-duplication — search.py create_bindings:
if subject in cluster_duplicates:
_score /= 2.0 # near-duplicate of an already-seen part -> halve its score
elif subject in clusters:
cluster_duplicates.update(clusters[subject])
Purpose: when you search "GFP", stop 50 near-identical GFP variants from flooding the top results — demote the near-duplicates so results are more diverse.
"Find similar parts" (SIMILAR) — lets a user ask "show me parts similar to this one," served from the precomputed clusters.
Correcting one assumption
It's not excluding identical sequences — it demotes sequences that are 80% similar (--id 0.8), i.e. near-duplicates / variants, not just exact copies. This distinction is what decides whether a hash can replace it.
So:
If you only need exact de-duplication → a plain hash wins; clustering can be dropped.
If you need to collapse variants (the current 0.8 behavior) → a plain hash can't do it.
Your instinct points at a real technique: similarity hashing
There are hash-based methods for near-duplicate grouping:
MinHash / LSH (Locality-Sensitive Hashing) approximate sequence similarity using hashes, grouping near-duplicates at near-hash speed — orders of magnitude faster than vsearch's all-vs-all cluster_fast, and naturally incremental (a new sequence just gets hashed into buckets).
Recommendation
The multi-hour clustering bottleneck can very likely be removed:
Decide the requirement — does rank de-dup need "exactly identical" or "near-identical variants"?
Exact only → plain hash, drop cluster_fast from indexing (hours → milliseconds).
Near-identical → MinHash/LSH, keeps variant-grouping but fast and incremental.
The "find similar" (SIMILAR) feature can instead be served on-demand at query time with vsearch --usearch_global (one-vs-all, seconds), rather than precomputing an all-vs-all clustering of the whole corpus offline.
One line
Clustering currently does two things: demote near-duplicates (80% similar) in ranking, and power "find similar parts." Exact duplicates are handled instantly by a plain hash; near-duplicate grouping can be done at near-hash speed and incrementally with MinHash/LSH instead of the multi-hour cluster_fast. Your hours-long bottleneck is very likely removable with hashing — it depends on whether you need "exact" or "approximate."
Exact clustering / dedup → plain hash. Hash the full sequence string (e.g. SHA-1); identical sequences collide into the same bucket. Exact, O(n), trivial. This replaces the dedup role cleanly.
"Similar" → MinHash + LSH. Sketch each sequence's k-mer set into a MinHash, index with MinHashLSH/MinHashLSHForest (e.g. the datasketch library). At query time you retrieve approximate nearest neighbors by Jaccard in ~constant time instead of running an all-vs-all alignment.
Two important caveats:
MinHash gives you distances, not clusters. To reproduce the part → {similar parts} dict you still need a grouping layer on top — either LSH banding to bucket candidates, or connected-components/greedy thresholding on the similarity graph. MinHash replaces the expensive pairwise-similarity step, not the grouping step.
Jaccard/Mash distance ≠ alignment identity. uclust's --id is alignment-based over the aligned region. MinHash Jaccard is alignment-free over k-mer sets, so it:
penalizes length asymmetry (a short part 100%-contained in a long one gets low Jaccard). If containment matters here, use containment MinHash rather than plain Jaccard.
won't exactly match a given uclust_identity threshold — you'll need to recalibrate k and the threshold empirically.
current clustering use > 60 hours to run on 80,000 sequenes.
What clustering does in SBOLExplorer — and can a hash replace it?
Role of clustering
The clusters map (which parts are similar to which) is produced by cluster.update_clusters() (the slow vsearch cluster_fast step) and used in two places:
Rank de-duplication — search.py create_bindings:
if subject in cluster_duplicates:
_score /= 2.0 # near-duplicate of an already-seen part -> halve its score
elif subject in clusters:
cluster_duplicates.update(clusters[subject])
Purpose: when you search "GFP", stop 50 near-identical GFP variants from flooding the top results — demote the near-duplicates so results are more diverse.
"Find similar parts" (SIMILAR) — lets a user ask "show me parts similar to this one," served from the precomputed clusters.
Correcting one assumption
It's not excluding identical sequences — it demotes sequences that are 80% similar (--id 0.8), i.e. near-duplicates / variants, not just exact copies. This distinction is what decides whether a hash can replace it.
So:
If you only need exact de-duplication → a plain hash wins; clustering can be dropped.
If you need to collapse variants (the current 0.8 behavior) → a plain hash can't do it.
Your instinct points at a real technique: similarity hashing
There are hash-based methods for near-duplicate grouping:
MinHash / LSH (Locality-Sensitive Hashing) approximate sequence similarity using hashes, grouping near-duplicates at near-hash speed — orders of magnitude faster than vsearch's all-vs-all cluster_fast, and naturally incremental (a new sequence just gets hashed into buckets).
Recommendation
The multi-hour clustering bottleneck can very likely be removed:
Decide the requirement — does rank de-dup need "exactly identical" or "near-identical variants"?
Exact only → plain hash, drop cluster_fast from indexing (hours → milliseconds).
Near-identical → MinHash/LSH, keeps variant-grouping but fast and incremental.
The "find similar" (SIMILAR) feature can instead be served on-demand at query time with vsearch --usearch_global (one-vs-all, seconds), rather than precomputing an all-vs-all clustering of the whole corpus offline.
One line
Clustering currently does two things: demote near-duplicates (80% similar) in ranking, and power "find similar parts." Exact duplicates are handled instantly by a plain hash; near-duplicate grouping can be done at near-hash speed and incrementally with MinHash/LSH instead of the multi-hour cluster_fast. Your hours-long bottleneck is very likely removable with hashing — it depends on whether you need "exact" or "approximate."
Exact clustering / dedup → plain hash. Hash the full sequence string (e.g. SHA-1); identical sequences collide into the same bucket. Exact, O(n), trivial. This replaces the dedup role cleanly.
"Similar" → MinHash + LSH. Sketch each sequence's k-mer set into a MinHash, index with MinHashLSH/MinHashLSHForest (e.g. the datasketch library). At query time you retrieve approximate nearest neighbors by Jaccard in ~constant time instead of running an all-vs-all alignment.
Two important caveats:
MinHash gives you distances, not clusters. To reproduce the part → {similar parts} dict you still need a grouping layer on top — either LSH banding to bucket candidates, or connected-components/greedy thresholding on the similarity graph. MinHash replaces the expensive pairwise-similarity step, not the grouping step.
Jaccard/Mash distance ≠ alignment identity. uclust's --id is alignment-based over the aligned region. MinHash Jaccard is alignment-free over k-mer sets, so it:
penalizes length asymmetry (a short part 100%-contained in a long one gets low Jaccard). If containment matters here, use containment MinHash rather than plain Jaccard.
won't exactly match a given uclust_identity threshold — you'll need to recalibrate k and the threshold empirically.