Efficient algorithm for finding the non-overlapping set of two very large sets of strings generated by permutation

Question

I am looking for the most efficient algorithm for comparing large set of strings that are representing possible amino acid substitutions at various positions of a 9mer peptide. As a toy example, the matrix M1
1 2 3
A 1 1 1
B 1 1 0
C 0 1 0
defines the set of three-letter strings which have an A, B, or C at positions 1, 2, and 3 when a “1” exists in the corresponding row in the matrix (set1).
Matrices in which one or more “1”s are replaced by “0” define subsets of set1. For example a set2 comprising the strings “ABA”, “ACA” can be defined by a matrix M2
1 2 3
A 1 0 1
B 0 1 0
C 0 1 0

As a non-mathematician, my straightforward approach was to compute set1 and set2, and then looking for members in set1 that do not have a match in set2.
However, I have become curious whether more efficient ways might exist to achieve this aim. I.e., could it be done by first performing an operation with M1 and M2 to generate a matrix M3 (or or a small set of matrices M3. M4,...) that define(s) the non-overlapping strings?
Note: In cases like the example above, a single 3x3 matrix as M3 is probably not sufficient.

Matt Timmermans · Accepted Answer · 2024-08-04 01:49:47Z

0

If I understand correctly, then each column of the matrix indicates the possible elements at each position in the string. So the first matrix in you question could be written as a regular expression like [AB][ABC][A].

The subset you give would be written [A][BC][A].

Unfortunately, it isn't generally possible to write the result of subtracting one matrix's set from another's as a single matrix.

You can write the result as n or fewer non-overlapping matrices, though: One for the set of strings with the first new character at position 0, one for the set of strings with the first new character at position 1, etc.

So, for example: [AB][ABC][A] - [A][BC][A] = [B][ABC][A] + [A][A][A]

There is no third term in this result because both of the sets in the subtraction have [A] in the 3rd position.

answered Aug 4, 2024 at 1:49

Matt Timmermans

60.9k3 gold badges57 silver badges106 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Efficient algorithm for finding the non-overlapping set of two very large sets of strings generated by permutation

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related