寻找9mer肽氨基酸替换字符串集非重叠部分的高效算法

核心思路 #

直接生成所有序列再求差集在9mer场景下完全不可行——每个位置最多有20种氨基酸，集合大小会指数级膨胀。我们可以通过矩阵运算直接定义set1 \ set2（属于set1但不属于set2的序列）的集合，无需生成完整序列。

set1 \ set2等价于：满足set1的所有位置规则，但至少有一个位置不满足set2的规则的序列。我们可以把这个逻辑拆分为多个子集合的并集，每个子集合对应“在某一个特定位置违反set2规则，其余位置都符合set1规则”的序列，每个子集合都能用单独的矩阵定义。

具体步骤 #

针对每个位置k（1到9），执行以下操作：

1. 找出该位置中，**在M1中为1（属于set1允许的氨基酸）但在M2中为0（不属于set2允许的氨基酸）**的氨基酸集合。
2. 如果这个集合为空，跳过该位置（没有序列在这个位置违反set2规则）。
3. 否则构建矩阵M_k：
   • 位置k：仅将上述筛选出的氨基酸设为1，其余为0；
   • 其他所有位置i≠k：直接沿用M1中该位置的1/0（即完全遵循set1的规则）。

所有非空M_k对应的集合的并集，就是set1 \ set2。

示例验证 #

用你提供的M1和M2验证：

原矩阵 #

M1：

M2：

拆分构建差集矩阵 #

1. 位置1：M1允许A/B，M2仅允许A → 筛选出B。构建矩阵M3：

该矩阵定义的序列：BAA、BAB、BAC（属于set1但不属于set2）。

2. 位置2：M1允许A/B/C，M2仅允许B/C → 筛选出A。构建矩阵M4：

该矩阵定义的序列：AAA（属于set1但不属于set2）。

3. 位置3：M1仅允许A，M2也允许A → 无符合条件的氨基酸，跳过。

M3和M4的并集正好是set1 \ set2的所有序列，与直接计算的结果一致。

为什么需要多个矩阵 #

因为set1 \ set2是“至少一个位置违反M2规则”的序列集合，这是逻辑或的关系，而单个矩阵只能表达“所有位置同时满足某规则”的逻辑与关系，因此无法用单个矩阵覆盖所有情况，必须用多个矩阵的并集来定义。

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