Patent ID: 9652586
Date: 2017-05-16
CPC Classifications: G16B

Claim:
1. A computer-implemented method for performing homology searching through comparing a first string of electronically represented target biological sequence data and a second string of electronically represented query biological sequence data to identify one or more sections of alignments between the first string and the second string, the method comprising: accessing a library comprised of one or more data structures, each of the one or more data structures configured to store one or more binary mask strings indicative of sequence data positions where a match is required at that sequence data position and sequence data positions where a match is not required at that sequence data position, each of the one or more binary mask strings having a weight determined by a number of sequence data positions where a match is required, and a length determined by a total number of sequence data positions in the binary mask string; generating one or more proposed binary mask models by populating each of the one or more data structures with a corresponding proposed binary mask string, each proposed binary mask string representing a possible non-consecutive spaced mask model having a predefined weight and a predefined length; determining which data structure of the one or more data structures is populated with an optimal binary mask string having a highest likelihood of identifying hits in a random pair of similar regions between the first string and the second string of biological sequence data being searched the optimal mask string being computationally identified by processing the one or more data structures to identify a data structure that maximizes the probability that a seed match is found, the probability characterized by the recursive relation: converting the first string into a reduced target sequence array by: determining one or more pairs of locations indicative of probable alignments between the first string and the second string by; processing each pair locations of the one or more flagged pairs of locations to determine the one or more sections of alignments between the first string and the second string.