Methods and apparatus for high-speed approximate sub-string searches
First Claim
1. A computer-implemented method for comparing a plurality of query sequences against a sequence database comprising the steps of:
- (a) combining said plurality of query sequences into a combined query sequence;
(b) determining a plurality of subdivisions of said database;
(c) performing a plurality of searches, wherein each search comprises a comparison of said combined query sequence against one of said plurality of subdivisions of said database, producing a plurality of word matches;
(d) extending the length of plurality of word matches produced in step (c), producing a plurality of High-scoring Segment Pairs;
(e) combining said plurality of High-scoring Segment Pairs; and
(f) producing a plurality of reports, each report representing the highest scoring matches for one of said plurality of query sequences.
3 Assignments
0 Petitions
Accused Products
Abstract
A method and system for conducting sequence searches in a sequence database wherein in one embodiment, the method includes: combining a plurality of query sequences into a combined query sequence; determining a plurality of subdivisions of the sequence database; performing a plurality of searches, wherein each search includes a comparison of the combined query sequence against one of the plurality of subdivisions of the database to produce a plurality of word matches; extending the length of the plurality of word matches to produce a plurality of High-scoring Segment Pairs, combining the plurality of High-scoring Segment Pairs; and producing a plurality of reports, each report representing the highest scoring matches for one of the plurality of query sequences.
76 Citations
4 Claims
-
1. A computer-implemented method for comparing a plurality of query sequences against a sequence database comprising the steps of:
-
(a) combining said plurality of query sequences into a combined query sequence;
(b) determining a plurality of subdivisions of said database;
(c) performing a plurality of searches, wherein each search comprises a comparison of said combined query sequence against one of said plurality of subdivisions of said database, producing a plurality of word matches;
(d) extending the length of plurality of word matches produced in step (c), producing a plurality of High-scoring Segment Pairs;
(e) combining said plurality of High-scoring Segment Pairs; and
(f) producing a plurality of reports, each report representing the highest scoring matches for one of said plurality of query sequences. - View Dependent Claims (2, 3, 4)
-
Specification