如何用R从成对亲缘关系矩阵中找出最大完全无关个体组？

这个问题本质等价于图论中的最大独立集问题：将每个个体视为图的节点，若两个个体亲缘关系值不为0，则在二者间连一条边；我们要找的最大完全无关组，就是图中两两无连接的最大节点集合。

实现步骤（基于igraph包） #

1. 安装并加载igraph包

install.packages("igraph")
library(igraph)

2. 处理亲缘矩阵，生成邻接矩阵
   构建邻接矩阵：当两个个体亲缘值不为0时（排除对角线的NA）标记为有边（值为1），否则为0。

# 基于你的示例矩阵处理
set.seed(420)
relatedness.matrix <- matrix(data = sample(x = c(0.5, 1, 0,0), size = 25, replace = TRUE), nrow = 5, ncol = 5)
relatedness.matrix[upper.tri(relatedness.matrix)] <- relatedness.matrix[lower.tri(relatedness.matrix)]
colnames(relatedness.matrix) <- letters[1:5]
rownames(relatedness.matrix) <- letters[1:5]
diag(relatedness.matrix) <- NA

# 生成邻接矩阵：亲缘值不为0则连边
adj_matrix <- ifelse(relatedness.matrix != 0, 1, 0)
diag(adj_matrix) <- 0  # 个体自身无连接

3. 构建图对象并求解最大独立集

# 从邻接矩阵创建无向图
g <- graph_from_adjacency_matrix(adj_matrix, mode = "undirected")

# 求解最大独立集
max_independent_set <- largest.independent.vertex.set(g)

# 提取结果中的个体名称
max_unrelated_group <- V(g)$name[max_independent_set]
print(max_unrelated_group)

示例结果验证 #

运行上述代码后，针对你的示例矩阵，输出会是规模为2的个体组（如["b", "e"]或["c", "d"]等），和你描述的可行解一致。

注意事项 #

• 39×39的矩阵规模下，igraph的求解函数可以高效处理（尽管最大独立集是NP-hard问题，但39个节点的计算量在R中完全可控）。
• 若存在多个规模相同的最大解，largest.independent.vertex.set会返回其中一个；如需获取所有最大解，可先用all.maximal.independent.vertex.sets得到所有极大独立集，再筛选出规模最大的集合。

内容的提问来源于stack exchange，提问作者Alex Krohn