我已经在R中进行了一段时间的系统发育分析，使用了类人猿、显灵和植物醇等类库。
在解决一个问题时，我找到了一个存在/不存在的data.frame，它指定感兴趣的基因是否属于某个组。
例如：
gene11 gene25 gene33 gene54 gene55 gene65 gene73 gene88
group_1 1 1 0 0 0 0 0 0
group_2 1 1 1 0 0 0 0 0
group_3 1 0 1 0 0 0 0 0
group_4 0 1 1 0 0 0 0 0
group_5 0 0 0 1 1 0 0 0
group_6 0 0 0 1 0 0 0 0
group_7 0 0 0 0 1 0 0 0
group_8 0 0 0 0 0 1 1 1
group_9 0 0 0 0 0 1 1 0
group_10 0 0 0 0 0 1 0 1
group_11 0 0 0 0 0 0 1 1
正如预期的那样，在处理生物实体的群体时，这些实体之间有许多联系方式：基因11、25和33组成一个群体，它们之间的关系也可以描述为较小的群体，描绘成对关系。
因此，这里有一件重要的事情：2组、5组和8组是与生物学相关的基因组，它们以前并不被称为相关组。
另一个较小的组，是由于这些相关组中显示的关系而产生的：组1与gene11和gene25相关，但是嵌套在更广泛（和相关）组2中的组。
同样的情况也适用于其他情况：GROMP-8描述了Gyn65、Geang3和GeN88之间的关系；关于这些基因的其他组（GROPSP9、GROP10、GROMP11）仅是描述在更广泛的组群8中的一部分的基因之间存在的成对关系的亚组。
先前已知的是，基因形成不相交群的簇，每个簇由其他（逐渐变小的）簇组成。我对捕获最大的不相交组感兴趣。
另一个用户（@shree）对问题做了明确的定义：
找到组的最小数目，以便所有其他组都是
至少其中一个组的子组。还有一个小组必须
至少2个基因，即连续两个1。同时假设，1,01,0是
1,1,1,0但0,1,1,1的子组不是1,1,1,0的子组。提前感谢大家！
最佳答案
这里有一种使用混合整数规划方法的方法我使用ompr进行数学建模，并使用glpk（免费开源）作为求解器。建模逻辑在代码中作为注释提供。
我认为这个问题可以用数学方法描述如下-
筛选dataframe以最小化行数，使所有列的总和为1。选定的行称为主组，其他每一行都应是主组的子组。一个列（基因）只能属于一个主群。在所有位置（列）处subgroup <= primary group时，任何未选中的行都是主组的子组因此，(0,0,1,1)是(0,1,1,1)的子群，但(1,0,1,1)不是(0,1,1,1)的子群。
library(dplyr)
library(ROI)
library(ROI.plugin.glpk)
library(ompr)
library(ompr.roi)
gene_mat <- as.matrix(df)
nr <- nrow(gene_mat)
nc <- ncol(gene_mat)
model <- MIPModel() %>%
# binary variable x[i] is 1 if row i is selected else 0
add_variable(x[i], i = 1:nr, type = "binary") %>%
# minimize total rows selected
set_objective(sum_expr(x[i], i = 1:nr), "min") %>%
# sum of columns of selected rows must be = 1
add_constraint(sum_expr(gene_mat[i,j]*x[i], i = 1:nr) == 1, j = 1:nc) %>%
solve_model(with_ROI(solver = "glpk"))
# get rows selected
group_rows <- model %>%
get_solution(x[i]) %>%
filter(value > 0) %>%
pull(i) %>%
print()
result <- df[group_rows, ]
gene11 gene25 gene33 gene54 gene55 gene65 gene73 gene88
group_2 1 1 1 0 0 0 0 0
group_5 0 0 0 1 1 0 0 0
group_8 0 0 0 0 0 1 1 1
重要提示-
上面的公式并不涉及
subgroup <= primary group，而是依赖于这样一个事实，即OP提到“事先已知的是，基因形成不相交群的簇”这意味着如下面所示的情况不存在于数据中，因为行1、3、4不形成不相交的组，即列3将属于不允许的2个主组。1 1 0 0 0
0 1 0 0 0
1 0 1 0 0 <- this row is not a subgroup of any row
0 0 1 1 1
无论如何，下面的代码将进行安全检查，以确保所有未选中的行都是只有一个主组的子组-
test <- lapply(group_rows, function(x) {
sweep(df, 2, as.numeric(df[x, ]), "<=") %>%
{which(rowSums(.) == ncol(df))}
})
# all is okay if below returns TRUE
length(Reduce(intersect, test)) == 0
数据-
df <- structure(list(
gene11 = c(1L, 1L, 1L, 0L, 0L, 0L, 0L, 0L, 0L,0L, 0L),
gene25 = c(1L, 1L, 0L, 1L, 0L, 0L, 0L, 0L, 0L, 0L, 0L),
gene33 = c(0L, 1L, 1L, 1L, 0L, 0L, 0L, 0L, 0L, 0L, 0L),
gene54 = c(0L, 0L, 0L, 0L, 1L, 1L, 0L, 0L, 0L, 0L, 0L),
gene55 = c(0L, 0L, 0L, 0L, 1L, 0L, 1L, 0L, 0L, 0L, 0L),
gene65 = c(0L, 0L, 0L, 0L, 0L, 0L, 0L, 1L, 1L, 1L, 0L),
gene73 = c(0L, 0L, 0L, 0L, 0L, 0L, 0L, 1L, 1L, 0L, 1L),
gene88 = c(0L, 0L, 0L, 0L, 0L, 0L, 0L, 1L, 0L, 1L, 1L)),
class = "data.frame",
row.names = c("group_1", "group_2", "group_3", "group_4",
"group_5", "group_6", "group_7", "group_8",
"group_9", "group_10", "group_11")
)