nuget
CD-HIT 的并行 LSH 分桶索引
CDHitLSH
00 Remarks
这里不再像 LSH.FindSimilarItems() 那样把全部的相似序列对都物化出来， 而是只建立「波段 -> 桶索引」的数据结构，然后在贪婪聚类的时候按需查询：
- 原实现会生成 Σ C(桶大小, 2) 个相似序列对。在泛基因组这类高度冗余的数据集上面 （同一个基因在上百个菌株之中都存在），相似对的数量可以达到数十亿条， 需要消耗数十 GB 的内存并且产生大量的锁竞争；
- 而实际上贪婪聚类只会用到「代表序列的、且还没有被归簇的邻居」， 所以完全可以推迟到聚类的时候再按需计算，中间不需要保存任何相似序列对。
另外，分桶索引只占用 3 个与序列数量成正比的数组（每个波段一套）， 相比原来「桶字典 + 每个桶一个 List 对象」的内存占用要低很多。
01 Syntax
SMRUCC.genomics.Analysis.SequenceAlignment.CDHitLSH
02 Methods
| Name | Overloads | Summary |
|---|---|---|
| BuildBuckets | 1 | 并行计算每一个 LSH 波段上面的分桶索引 |
| SignatureSimilarity | 1 | 计算两个 min-hash 签名之间的相似度 |
| validateSignatures | 1 | 检查所有的签名数据都是完整的（长度足够、非空） |
03 Members
BuildBuckets(
SequenceItem(), Int32, Int32, Int32)并行计算每一个 LSH 波段上面的分桶索引
Parameters
| Name | Type | Description |
|---|---|---|
minHash | SequenceItem() | 序列集合的 min-hash 签名（下标即为序列的下标） |
workers | Int32 | 并行的工作线程数量 |
Num_Bands | Int32 | LSH波段数 |
Rows_Per_Band | Int32 | 每个波段的行数 |
SignatureSimilarity(
UInt32(), UInt32())计算两个 min-hash 签名之间的相似度
Remarks
与 LSH.CalculateSimilarity 的算法完全一致
Parameters
| Name | Type | Description |
|---|---|---|
sig1 | UInt32() | - |
sig2 | UInt32() | - |
validateSignatures(
SequenceItem(), Int32)检查所有的签名数据都是完整的（长度足够、非空）