Length of the longest common subsequence algorithm optimization
Systems and methods perform various optimizations of an LLCS algorithm for use in determining if a set of input sequences are similar to a query sequence. The optimizations include filtering out sequence from the set of input sequences where the estimated similarity of the sequence with the query sequence is below a threshold value. The remaining sequences can then be provided to an LLCS algorithm where the output of the LLCS algorithm is used in a similarity function to determine an actual similarity of an input sequence with a query sequence.
1. A method for determining similar sequences, the method comprising:
receiving a plurality of input sequences and a query sequence;
performing one or more filters that, for each input sequence in the plurality of input sequences, performs operations including:
determining an estimated similarity value for the input sequence and the query sequence, wherein the estimated similarity value is determined such that the estimated similarity value is greater than or equal to an actual similarity value;
including the input sequence in a set of remainder sequences in response to determining that the estimated similarity value is at or above a similarity threshold, wherein the set of remainder sequences is comprised of all of the input sequences in the plurality of input sequences having the estimated similarity value at or above the similarity threshold;
wherein the one or more filters include a histogram filter that performs operations including creating histograms for the query sequence and one or more of the input sequences in the plurality of input sequences, and wherein the histogram filter performs further operations including:
determining a first sum of a first histogram of the query sequence,
determining a second sum of a second histogram of the input sequence,
determining a third sum comprising a sum of a minimum from each bin of the first histogram and a corresponding bin of the second histogram,
wherein determining the estimated similarity value includes determining the estimated similarity value based, at least in part, on the first sum, the second sum, and the third sum; and
wherein the operations further include associating the estimated similarity value with the input sequence; and
determining a results set, said determining including, for each remainder sequence in the set of remainder sequences:
determining a length of the longest common subsequence (LLCS) of the remainder sequence and the query sequence,
determining a similarity value of the remainder sequence and the query sequence based, at least in part, on the LLCS, and
in response to determining that the similarity value is above the similarity threshold, including the remainder sequence in the results set.
2. The method of claim 1 , wherein the one or more filters include a size filter that performs operations including:
determining a size of the input sequence; and
determining a size of the query sequence;
wherein determining the estimated similarity value includes determining the estimated similarity value based, at least in part, on the size of the input sequence, the size of the query sequence, and a minimum of the size of the input sequence and the size of the query sequence.
3. The method of claim 1 , further comprising:
determining whether a number of sequences in the results set is equal to or greater than a result set size; and
in response to determining that the number of sequences in the results set is equal to or greater than the result set size, performing operations including:
determining a most similar sequence in a subset of sequences in the set of remainder sequences, the subset comprising remainder sequences for which an LLCS has not been determined,
in response to determining that the estimated similarity value of the most similar sequence is less than or equal to the similarity value of a least similar sequence in the results set, terminating determining the results set.
4. A system for determining similar sequences, the system comprising:
at least one electronic processor for executing at least one algorithm, wherein said system:
receives a plurality of input sequences and a query sequence;
performs one or more filters that, for each input sequence in the plurality of input sequences, performs operations including:
determining an estimated similarity value for the input sequence and the query sequence, wherein the estimated similarity value is determined such that the estimated similarity value is greater than or equal to an actual similarity value, and
including the input sequence in a set of remainder sequences in response to determining that the estimated similarity value is at or above a similarity threshold, wherein the set of remainder sequences is comprised of all of the input sequences in the plurality of input sequences having the estimated similarity value at or above the similarity threshold,
wherein the one or more filters include a histogram filter that performs operations including creating histograms for the query sequence and one or more of the input sequences in the plurality of input sequences, and wherein the histogram filter performs further operations including:
determining a first sum of a first histogram of the query sequence,
determining a second sum of a second histogram of the input sequence,
determining a third sum comprising a sum of a minimum from each bin of the first histogram and a corresponding bin of the second histogram,
wherein determining the estimated similarity value includes determining the estimated similarity value based, at least in part, on the first sum, the second sum, and the third sum; and
wherein the operations further include associating the estimated similarity value with the input sequence; and
determines a results set, said determining including, for each remainder sequence in the set of remainder sequences:
determining a length of the longest common subsequence (LLCS) of the remainder sequence and the query sequence,
determining a similarity value of the remainder sequence and the query sequence based, at least in part, on the LLCS, and
in response to determining that the similarity value is above the similarity threshold, including the remainder sequence in the results set.
5. The system of claim 4 , wherein the one or more filters include a size filter that performs operations including:
determining a size of the input sequence; and
determining a size of the query sequence;
wherein determining the estimated similarity value includes determining the estimated similarity value based, at least in part, on the size of the input sequence, the size of the query sequence, and a minimum of the size of the input sequence and the size of the query sequence.
6. The system of claim 4 , wherein said system—
determines whether a number of sequences in the results set is equal to or greater than a result set size; and
in response to determining that the number of sequences in the results set is equal to or greater than the result set size, performs operations including:
determining a most similar sequence in a subset of sequences in the set of remainder sequences, the subset comprising remainder sequences for which an LLCS has not been determined,
in response to determining that the estimated similarity value of the most similar sequence is less than or equal to the similarity value of a least similar sequence in the results set, terminating determining the results set.
7. A non-transitory computer readable medium containing program instructions for determining similar sequences, wherein execution of the program instructions by one or more processors of a computer system causes the one or more processors to carry out the steps of:
receiving a plurality of input sequences and a query sequence;
performing one or more filters that, for each input sequence in the plurality of input sequences, performs operations including:
determining an estimated similarity value for the input sequence and the query sequence, wherein the estimated similarity value is determined such that the estimated similarity value is greater than or equal to an actual similarity value, and
including the input sequence in a set of remainder sequences in response to determining that the estimated similarity value is at or above a similarity threshold, wherein the set of remainder sequences is comprised of all of the input sequences in the plurality of input sequences having the estimated similarity value at or above the similarity threshold,
wherein the one or more filters include a histogram filter that performs operations including creating histograms for the query sequence and one or more of the input sequences in the plurality of input sequences, and wherein the histogram filter performs further operations including:
determining a first sum of a first histogram of the query sequence,
determining a second sum of a second histogram of the input sequence,
determining a third sum comprising a sum of a minimum from each bin of the first histogram and a corresponding bin of the second histogram,
wherein determining the estimated similarity value includes determining the estimated similarity value based, at least in part, on the first sum, the second sum, and the third sum; and
wherein the operations further include associating the estimated similarity value with the input sequence; and
determining a results set, said determining including, for each remainder sequence in the set of remainder sequences:
determining a length of the longest common subsequence (LLCS) of the remainder sequence and the query sequence,
determining a similarity value of the remainder sequence and the query sequence based, at least in part, on the LLCS, and
in response to determining that the similarity value is above the similarity threshold, including the remainder sequence in the results set.
8. The non-transitory computer readable medium claim 7 , wherein the one or more filters include a size filter that performs operations including:
determining a size of the input sequence; and
determining a size of the query sequence;
wherein determining the estimated similarity value includes determining the estimated similarity value based, at least in part, on the size of the input sequence, the size of the query sequence, and a minimum of the size of the input sequence and the size of the query sequence.
9. The non-transitory computer readable medium of claim 7 , wherein execution of the program instructions by one or more processors of the computer system causes the one or more processors to carry out the steps of:
determining whether a number of sequences in the results set is equal to or greater than a result set size; and
in response to determining that the number of sequences in the results set is equal to or greater than the result set size, performing operations including:
determining a most similar sequence in a subset of sequences in the set of remainder sequences, the subset comprising remainder sequences for which an LLCS has not been determined,
in response to determining that the estimated similarity value of the most similar sequence is less than or equal to the similarity value of a least similar sequence in the results set, terminating determining the results set.