我正在寻找最有效的算法来比较代表 9mer 肽各个位置可能的氨基酸取代的大量字符串。
作为一个玩具示例，矩阵 M1
1 2 3
1 1 1
B 1 1 0
C 0 1 0
定义当矩阵 (set1) 中相应行中存在“1”时，在位置 1、2 和 3 处具有 A、B 或 C 的三字母字符串的集合。
其中一个或多个“1”被“0”替换的矩阵定义了 set1 的子集。例如，包含字符串“ABA”、“ACA”的集合2可以由矩阵M2定义
1 2 3
一个 1 0 1
B 0 1 0
C 0 1 0
作为一名非数学家，我的直接方法是计算 set1 和 set2，然后查找 set1 中与 set2 中不匹配的成员。
然而，我很好奇是否存在更有效的方法来实现这一目标。即，是否可以通过首先对 M1 和 M2 执行运算来生成定义非重叠字符串的矩阵 M3（或一小组矩阵 M3.M4，...）来完成？
注意：在类似上面示例的情况下，单个 3x3 矩阵作为 M3 可能不够。
如果我理解正确的话，那么矩阵的每一列都表示字符串中每个位置可能的元素。 因此，您问题中的第一个矩阵可以写成正则表达式，如 [AB][ABC][A]。
您给出的子集将写为 [A][BC][A]。
不幸的是，通常不可能将一个矩阵集合减去另一个矩阵集合的结果写为单个矩阵。
不过，您可以将结果写为 n 或更少的非重叠矩阵：一个用于第一个新字符位于位置 0 的字符串集合，一个用于第一个新字符位于位置 1 的字符串集合，等等。
例如： [AB][ABC][A] - [A][BC][A] = [B][ABC][A] + [A][A][A]
此结果中没有第三项，因为减法中的两个集合的第三个位置都有 [A]。