nuget
并查集辅助类，用于高效处理基因家族的聚类
UnionFind
01 Syntax
SMRUCC.genomics.Analysis.PanGenome.UnionFind
02 Methods
| Name | Overloads | Summary |
|---|---|---|
| AddElement | 1 | 添加元素 |
| AddElements | 1 | 批量添加元素（用于一次性初始化上百万个基因节点） |
| Find | 1 | 查找根节点 |
| UnionRange | 2 | 将一个直系同源分组（例如cd-hit的一个cluster）内的所有基因直接合并为同一个基因家族 |
| Union | 1 | 合并两个集合 |
| GetClusters | 1 | 提取聚类结果 |
03 Members
AddElement(
String)添加元素
Parameters
| Name | Type | Description |
|---|---|---|
element | String | - |
AddElements(
IEnumerable(Of String))批量添加元素（用于一次性初始化上百万个基因节点）
Parameters
| Name | Type | Description |
|---|---|---|
elements | IEnumerable(Of String) | - |
Find(
String)查找根节点
Remarks
这里使用迭代的方式做路径压缩，而不是递归： 在处理上百万个基因的时候，合并链可能会非常深，递归版本有栈溢出的风险。
Parameters
| Name | Type | Description |
|---|---|---|
element | String | - |
UnionRange(
IEnumerable(Of String))将一个直系同源分组（例如cd-hit的一个cluster）内的所有基因直接合并为同一个基因家族
Remarks
一个包含k个基因的分组只需要 k-1 次合并操作即可完成聚类， 不需要先生成 O(k^2) 个两两配对关系再逐个合并，可以节省大量的内存与计算时间。
注意：只有已经通过 UnionFind.AddElement() 注册过的基因才会参与合并， 未知的基因ID会被忽略掉（与BBH路径的行为保持一致）。
Parameters
| Name | Type | Description |
|---|---|---|
genes | IEnumerable(Of String) | 同一个分组内的基因ID列表 |
UnionRange(
String(), String())将一个直系同源分组（例如cd-hit的一个cluster）内的所有基因合并为同一个基因家族
Remarks
一个包含k个基因的分组只需要 k-1 次合并操作即可完成聚类， 不需要先生成 O(k^2) 个两两配对关系再逐个合并。
Parameters
| Name | Type | Description |
|---|---|---|
genes | String() | 分组内的基因ID，顺序与原始的两两配对枚举顺序保持一致 |
sources | String() | 每一个基因所属的比对来源（一般是replicon编号）。只有来源不同的基因之间才会被合并， 同一个来源之内的基因（旁系同源）不会被合并到同一个家族之中， 这样子可以和 OrthoGroupsHelper.BuildHomologyRelations() 的行为保持一致。 |
Union(
String, String)合并两个集合
Parameters
| Name | Type | Description |
|---|---|---|
referID | String | 推荐使用参考基因ID，这样子比较容易生成有意义的家族ID |
geneID | String | 待分析的基因组内的基因ID |
GetClusters
提取聚类结果
Returns
构建家族映射