需要算法帮助

Question

我有一组序列(例如10000个序列),并产生表示每两个序列之间成对相似性的矩阵(10000×10000).

现在的目标是从大集合中检索子集(例如1000个序列),并确保该子集中每两个序列之间的成对相似性在一个范围内(例如50%~85%).

有没有快速算法呢？

Answer 1

您可以将其转换为图论问题：

1. 每个序列都是一个节点
2. 如果两个节点的相似度在给定范围内，则它们之间存在边
3. 您的目标是找到最大的连通分量（如果您的相似关系是传递的......）或最大的集团（......如果不是）。