Method and system for rapid searching of genomic data and uses thereof
Inventors
Daly, Kristopher Edward • Stephens, Kurtis Phillip
Assignees
Interested in licensing this patent?
MTEC can help explore whether this patent might be available for licensing for your application.
Publication Number
US-9529891-B2
Publication Date
2016-12-27
Expiration Date
Abstract
A method, apparatus and system for transforming genomic data into a computer database environment comprising a forward lookup table and a plurality of reverse lookup tables which relate consecutive overlapping reference sequence segments to reference sequences stored in the forward lookup table enables rapid and precise matching of undefined biological sequences with reference sequences.
Core Innovation
The invention provides a computer-implemented method for matching at least one query sequence comprising a third string of contiguous characters of string length L to at least one reference sequence. A computer database environment is maintained in a non-transitory computer readable storage medium and includes a forward lookup table and at least one reverse lookup table, where each reverse lookup table relates reference sequence segments to reference sequences stored in the forward lookup table.
For matching, at least a first reverse lookup table having the largest preselected positive integer k that is less than or equal to L is selected. The query is transformed into a first set of L/k consecutive non-overlapping query sequence segments by partitioning the third string into L/k consecutive non-overlapping segments using the selected k, and the transformed query segments are queried against each set of Y−k+1 consecutive overlapping reference sequence segments in the selected reverse lookup table.
In the described implementation and refinements, matched segments are combined into reconstructed contiguous-character strings, species of origin is used to filter and select matches, and the reconstructed results are formed by offset-sorted concatenation. Remaining gaps in the reconstructed contiguous-character strings are characterized and iteratively filled using progressively smaller k values, including optional sliding matching, permutative matching, or hybrid matching, to output reconstructed sequences and related reports.
Claims Coverage
The included independent claims cover two main inventive features and related system-level processing. The core coverage centers on selecting a reverse lookup table based on the largest k ≤ L, partitioning the query into L/k non-overlapping segments of size k, matching these segments against sets of Y−k+1 consecutive overlapping reference segments in the selected reverse lookup table, and outputting matching reference sequences, with additional coverage for parallel/asynchronous execution and gap filling through the forward lookup table.
Selecting reverse lookup tables parameterized by k relative to query length L
Selecting, via the data processing system, at least a first reverse lookup table of at least one reverse lookup table in a computer database environment that has the largest preselected positive integer k that is less than or equal to L; the database environment comprises a forward lookup table and the at least one reverse lookup table that relates reference sequence segments stored therein to reference sequences stored in the forward lookup table, wherein each reverse lookup table comprises sets of Y−k+1 consecutive overlapping reference sequence segments for each reference sequence record stored in the forward lookup table.
Partitioning query into non-overlapping segments of size k
Transforming the at least one query sequence into at least a first set of L/k consecutive non-overlapping query sequence segments by partitioning the third string of contiguous characters into L/k consecutive non-overlapping segments where k is equal to the preselected positive integer k for the at least the first reverse lookup table selected.
Segment matching against overlapping reference segments and outputting matching references
Querying the at least the first set of L/k consecutive non-overlapping query sequence segments against each set of Y−k+1 consecutive overlapping reference sequence segments in the at least the first reverse lookup table selected for matching reference and query sequence segments; outputting at least one reference sequence that matches the at least one query sequence.
Parallel/asynchronous processing with thread manager for transform, query, gap filling, and output
A data processing system comprising a processor circuit having a thread manager configured to create a maximum number of threads available in response to receiving a query, where the maximum number of threads comprise a first thread for partitioning the query, a second thread for querying the reverse lookup tables, and a third thread for gap filling, and wherein the maximum number of threads perform asynchronously and in parallel the steps of transforming each query sequence into L/k consecutive non-overlapping equally sized query sequence segments, querying against the corresponding reverse lookup table comprising the preselected positive integer k for matching non-overlapping query sequence segments, gap filling to match the query sequence with at least one reference sequence in the forward lookup table, and outputting the at least one reference sequence that matches the query sequence.
Reverse lookup table sets relate overlapping reference segments to forward lookup reference records
A computer database environment comprising a forward lookup table and a plurality of reverse lookup tables maintained in a non-transitory computer readable storage medium and configured to relate each set of Y−k+1 consecutive overlapping reference sequence segments stored in records of the plurality of reverse lookup tables to reference sequences stored in records of the forward lookup table, wherein each set comprises a first string of contiguous characters having a length equal to a preselected positive integer k which differs for each of the reverse lookup tables.
Across the included independent claims, the inventive core is an architecture and method for selecting a reverse lookup table by the largest k ≤ L, partitioning the query into L/k non-overlapping segments of size k, matching them against sets of Y−k+1 consecutive overlapping reference segments in the selected reverse lookup table, and outputting matching reference sequences; the data processing system claim further covers parallel/asynchronous execution with a thread manager that performs transform, reverse-lookup querying, gap filling through the forward lookup table, and output.
Stated Advantages
Not explicitly described in patent.
Documented Applications
Not explicitly described in patent.
Interested in licensing this patent?