需要算法帮助

Question

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

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

是否有任何快速算法可以做到这一点？

Answer 1

您可以将其转化为图论问题:

1. 每个序列都是一个节点
2. 如果两个节点的相似度在给定范围内，则它们之间有一条边
3. 你的目标是找到最大的connected component (如果你的相似关系是传递的......)或大 clique (...如果不是)。