Notice of Pre-AIA or AIA Status
The present application, filed on or after March 16, 2013, is being examined under the first inventor to file provisions of the AIA .
Response to Amendment
The amendment filed 10/08/2025 has been entered. No claims are canceled or amended. Claims 21-42 remain pending in the application.
Response to Arguments
Regarding claim 21 Applicant argues that “Independent claim recites, inter alia, "determining, by the mapping and aligning unit, whether the response to the executed query includes (i) an extend record and (ii) an interval record, wherein the interval record identifies a contiguous set of reference sequence locations, stored in an extension table, that match the first seed” (emphasis added). The applicant respectfully submits that Van Rooyen does not disclose at least these claim features, rendering claims novel. The office action alleges that Van Rooyen's disclosure of an ''EXTEND record" and seed extension process constitute disclosure of the claimed interval record. See office action at pgs. 15-17. However, nothing in Van Rooyen discloses the claimed "interval record'' as claimed. For example, at a minimum, Van Rooyen does not determine whether a response to a hash table query includes "(i) an extend record and (ii) an interval record, wherein the interval record identifies a contiguous set of reference sequence locations, stored in an extension table, that match the first seed'' ( emphasis added). Van Rooyen does not disclose a single hash table location that stores both an extend record and an interval record. Thus, Van Rooyen cannot disclose a response to a hash table query of the hash table that includes "(i) an extend record and (ii) an interval record," as claimed. The office action continues that Van Rooyen discloses that an interval record identifies a contiguous set of reference sequence locations, stored in an extension table, that match the first seed, as claimed. In this regard, the office action alleges that "chains" as disclosed in Van Rooyen (e.g., in Van Rooyen paragraph [00227]) correspond to "contiguous interval." The applicant disagrees.
Van Rooyen describes chains as connections of hash buckets for storage of data that exceeds capacity of individual has buckets, and chaining as storing information in such chains of hash buckets. Unlike the office action's characterization, Van Rooyen' s "chaining" of information in hash buckets does not correspond to "a contiguous set of reference sequence locations" comprising an "interval record" as claimed. Van Rooyen therefore does not disclose, at a minimum, "determining, by the mapping and aligning unit, whether the response to the executed query includes (i) an extend record and (ii) an interval record, wherein the interval record identifies a contiguous set of reference sequence locations, stored in an extension table, that match the first seed" as claimed.”
Examiner respectfully submits that Van Rooyen in paragraph [00227], line 4, describes that “queries of the hash table may be repeated with various seed lengths if one or more EXTEND records appear. The end result will be a plurality of seeds that match similar reference positions, which seeds may then be grouped into chains and aligned;”. Examiner interprets that “queries of the hash table may be repeated with various seed lengths if the EXTEND records appear” is corresponding to “whether the response to the executed query includes (i) an extend record”. Besides, Van Rooyen in paragraph [00224], describes that “ At run-time, a first query to the hash table retrieves the EXTEND record, which induces the mapper engine to re-hash at 31-base length, and query the hash table again, retrieving either a single reference position or a group of 8 positions, assuming the extended seed still matches the reference somewhere.”. Further, Van Rooyen in paragraph [00222] explains that “The positions of these extended seeds may then be saved in the table. For instance, multiple reference positions matching a given seed may be stored as multiple hash records, either all in the same hash bucket, or spread by probing or chaining into additional buckets”. Hence, Van Rooyen teaches multiple reference positions matching a given seed may be stored as multiple hash records.
Therefore, Van Rooyen describes that queries of the hash table may be repeated with various seed lengths if the EXTEND records appear. EXTEND record induces the mapper engine to re-hash and query the hash table again retrieving either a single reference position or a group of 8 positions, assuming the extended seed still matches the reference somewhere. So, EXTEND record induces the following steps of query of hash table again and retrieving either a single reference position or a group of 8 positions. Examiner interprets that “either a single reference position or a group of 8 positions” is corresponding to “interval record”. On the other hand, Van Rooyen in paragraph [00221] explains that “Consequently, in various instances, an algorithm, like a Burrows-Wheeler based algorithm, may be employed so as to incrementally extend matches until the suffix interval becomes narrow enough to process a reasonable number of reference positions….Therefore, when a particular seed matches up to a plurality, e.g., several, positions in the reference, each position may be stored in the table, such as at an address derived from the hash function of the seed”. Van Rooyen teaches using Burrows-Wheeler algorithm to incrementally extend matches until the suffix interval becomes narrow enough. Therefore, it is searching for the intervals that match the query.
Examiner submits that paragraph [0032] of specification recites that “the interval record references a plurality of locations, in the seed extension table, that include data describing reference sequence locations that match the first seed of the query.”. Moreover, paragraph [0051] of specification recites that “an "interval record" that can be stored in a hash table location. The interval record identifies, for a particular seed, a contiguous set of reference sequence locations, stored in a seed extension table, that match the particular seed.”.
Therefore, Van Rooyen teaches “determining, whether the response to the executed query includes (i) an extend record and (ii) an interval record, wherein the interval record identifies a contiguous set of reference sequence locations, stored in an extension table, that match the first seed”.
Double Patenting
The nonstatutory double patenting rejection is based on a judicially created doctrine grounded in public policy (a policy reflected in the statute) so as to prevent the unjustified or improper timewise extension of the “right to exclude” granted by a patent and to prevent possible harassment by multiple assignees. A nonstatutory double patenting rejection is appropriate where the conflicting claims are not identical, but at least one examined application claim is not patentably distinct from the reference claim(s) because the examined application claim is either anticipated by, or would have been obvious over, the reference claim(s). See, e.g., In re Berg, 140 F.3d 1428, 46 USPQ2d 1226 (Fed. Cir. 1998); In re Goodman, 11 F.3d 1046, 29 USPQ2d 2010 (Fed. Cir. 1993); In re Longi, 759 F.2d 887, 225 USPQ 645 (Fed. Cir. 1985); In re Van Ornum, 686 F.2d 937, 214 USPQ 761 (CCPA 1982); In re Vogel, 422 F.2d 438, 164 USPQ 619 (CCPA 1970); In re Thorington, 418 F.2d 528, 163 USPQ 644 (CCPA 1969).
A timely filed terminal disclaimer in compliance with 37 CFR 1.321(c) or 1.321(d) may be used to overcome an actual or provisional rejection based on nonstatutory double patenting provided the reference application or patent either is shown to be commonly owned with the examined application, or claims an invention made as a result of activities undertaken within the scope of a joint research agreement. See MPEP § 717.02 for applications subject to examination under the first inventor to file provisions of the AIA as explained in MPEP § 2159. See MPEP §§ 706.02(l)(1) - 706.02(l)(3) for applications not subject to examination under the first inventor to file provisions of the AIA . A terminal disclaimer must be signed in compliance with 37 CFR 1.321(b).
The USPTO Internet website contains terminal disclaimer forms which may be used. Please visit www.uspto.gov/patent/patents-forms. The filing date of the application in which the form is filed determines what form (e.g., PTO/SB/25, PTO/SB/26, PTO/AIA /25, or PTO/AIA /26) should be used. A web-based eTerminal Disclaimer may be filled out completely online using web-screens. An eTerminal Disclaimer that meets all requirements is auto-processed and approved immediately upon submission. For more information about eTerminal Disclaimers, refer to www.uspto.gov/patents/process/file/efs/guidance/eTD-info-I.jsp.
Claims 21-42 are rejected on the ground of nonstatutory anticipatory type double patenting as being unpatentable over claims 1-6, 13-14, 19 and 21-22 of U.S. Patent No. 11803554 B2. Although the claims at issue are not identical, they are not patentably distinct from each other because they are obvious variants of each other.
The chart below shows the correspondence between the claims in the current application and the patent claims.
Current Application (18/497,830)
U.S. Patent No. 11803554 B2
21. A method for using a hash table to improve the mapping of sample reads to a reference sequence, the method comprising:
executing, by a mapping and aligning unit, a query of a hash table, the query including a first seed, wherein the first seed includes a subset of nucleotides that were obtained from a particular read of the sample reads;
1. A method for using a hash table to improve the mapping of sample reads to a reference sequence, the method comprising:
executing, by a mapping and aligning unit, a query of a hash table, the query including a first seed, wherein the first seed includes a subset of nucleotides that were obtained from a particular read of the sample reads;
obtaining, by the mapping and aligning unit, a response to the executed query that includes information stored by a location of the hash table that is determined to be responsive to the query;
obtaining, by the mapping and aligning unit, a response to the executed query that includes information stored by a location of the hash table that is determined to be responsive to the query;
determining, by the mapping and aligning unit, whether the response to the executed query includes (i) an extend record and (ii) an interval record, wherein the interval record identifies a contiguous set of reference sequence locations, stored in an extension table, that match the first seed;
determining, by the mapping and aligning unit, whether the response to the executed query includes (i) an extend record and (ii) an interval record, wherein the interval record identifies a contiguous set of reference sequence locations, stored in an extension table, that match the first seed;
based on determining, by the mapping and aligning unit, that the response to the executed query includes (i) an extend record and (ii) an interval record:
determining, by the mapping and aligning unit, whether the extension table is to be accessed to obtain one or more matching reference sequence locations in the extension table that are referenced by the interval record;
based on determining, by the mapping and aligning unit, that the response to the executed query includes (i) an extend record and (ii) an interval record:
determining, by the mapping and aligning unit, whether the extension table is to be accessed to obtain one or more matching reference sequence locations in the extension table that are referenced by the interval record;
and based on determining that the extension table is to be accessed: accessing, by the mapping and aligning unit, the extension table to obtain the one or more matching reference sequence locations in the extension table that are referenced by the interval record;
2. based on determining that the extension table is to be accessed: accessing, by the mapping and aligning unit, the extension table to obtain the one or more matching reference sequence locations in the extension table that are referenced by the interval record;
and adding, by the mapping and aligning unit, the one or more matching reference sequence locations to a seed match set.
and adding, by the mapping and aligning unit, the one or more matching reference sequence locations to a seed match set.
22. The method of claim 21, the method further comprising:
based on determining that the extension table is not to be accessed: determining, by the mapping and aligning unit, whether to store the first information describing the interval record in a memory device as information describing a candidate best interval;
generating, by the mapping and aligning unit, a first extended seed that is an extension of the first seed using the extend record;
generating, by the mapping and aligning unit, a subsequent hash query that includes the first extended seed;
and executing, by the mapping and aligning unit, the subsequent hash query of the hash table.
1. based on determining that the extension table is not to be accessed: determining, by the mapping and aligning unit, whether to store the first information describing the interval record in a memory device as information describing a candidate best interval;
generating, by the mapping and aligning unit, a first extended seed that is an extension of the first seed using the extend record;
generating, by the mapping and aligning unit, a subsequent hash query that includes the first extended seed;
and executing, by the mapping and aligning unit, the subsequent hash query of the hash table.
23. The method of claim 22, the method further comprising:
determining, by the mapping and aligning unit, that the response to the executed query includes one or more matching reference sequence locations;
and based on determining, by the mapping and aligning unit, that the response to the executed query includes one or more matching reference sequence locations:
adding, by the mapping and aligning unit, the one or more matching reference sequence locations to a seed match set.
3. The method of claim 1, the method further comprising:
determining, by the mapping and aligning unit, that the response to the executed query includes one or more matching reference sequence locations;
and based on determining, by the mapping and aligning unit, that the response to the executed query includes one or more matching reference sequence locations:
adding, by the mapping and aligning unit, the one or more matching reference sequence locations to a seed match set.
24. The method of claim 22, wherein determining, by the mapping and aligning unit, whether to store the first information describing the interval record in a memory device as information describing a candidate best interval comprises:
determining, by the mapping and aligning unit, that there is not prior information describing an interval record as a candidate best interval for the particular read;
and storing, by the mapping and aligning unit, the first information describing the interval record in the memory device as information describing a candidate best interval.
4. The method of claim 1, wherein determining, by the mapping and aligning unit, whether to store the first information describing the interval record in a memory device as information describing a candidate best interval comprises:
determining, by the mapping and aligning unit, that there is not prior information describing an interval record as a candidate best interval for the particular read;
and storing, by the mapping and aligning unit, the first information describing the interval record in the memory device as information describing a candidate best interval.
25. The method of claim 22, the method further comprising:
obtaining, by the mapping and aligning unit, a response to the subsequent executed query that includes information stored by a location of the hash table that is determined to be responsive to the query;
determining, by the mapping and aligning unit, whether the response to the subsequent executed query includes (i) a second extend record (ii) a second interval record, and (iii) one or more matching reference sequence locations; based on determining, by the mapping and aligning unit, that the response to the subsequent executed query includes (i) the second extend record and (ii) the second interval record:
determining, by the mapping and aligning unit, whether the extension table is to be accessed to obtain one or more matching reference sequence locations in the extension table that are referenced by the second interval record;
based on determining that the extension table is not to be accessed:
determining, by the mapping and aligning unit and using one or more heuristic rules, whether second information describing the second interval record or the first information describing the candidate best interval is to be used as the candidate best interval;
generating, by the mapping and aligning unit, a second extended seed that is an extension of the first extended seed using the second extend record;
generating, by the mapping and aligning unit, a third hash query that includes the second extended seed; and
executing, by the mapping and aligning unit, the third query of the hash table that includes the second extended seed.
5. The method of claim 1, the method further comprising:
obtaining, by the mapping and aligning unit, a response to the subsequent executed query that includes information stored by a location of the hash table that is determined to be responsive to the query;
determining, by the mapping and aligning unit, whether the response to the subsequent executed query includes (i) a second extend record (ii) a second interval record, or (iii) one or more matching reference sequence locations;
based on determining, by the mapping and aligning unit, that the response to the subsequent executed query includes (i) the second extend record and (ii) the second interval record:
determining, by the mapping and aligning unit, whether the extension table is to be accessed to obtain one or more matching reference sequence locations in the extension table that are referenced by the second interval record;
based on determining that the extension table is not to be accessed:
determining, by the mapping and aligning unit and using one or more heuristic rules, whether second information describing the second interval record or the first information describing the candidate best interval is to be used as the candidate best interval;
generating, by the mapping and aligning unit, a second extended seed that is an extension of the first extended seed using the second extend record;
generating, by the mapping and aligning unit, a third hash query that includes the second extended seed; and
executing, by the mapping and aligning unit, the third query of the hash table that includes the second extended seed.
26. The method of claim 25, wherein determining, by the mapping and aligning unit and using one or more heuristic rules, whether the second information describing the second interval record or the first information describing the candidate best interval is to be used as the best interval comprises:
selecting either the second information describing the second interval record or the first information describing the candidate best interval record based on a plurality of factors that include (i) a number of matching reference sequence locations returned by each of the interval record and the second interval record, (ii) a predetermined threshold level of reference sequence locations, or (iii) each seed length of the respective seeds that reached the hash locations storing the interval record and the second interval record.
6. The method of claim 5, wherein determining, by the mapping and aligning unit and using one or more heuristic rules, whether the second information describing the second interval record or the first information describing the candidate best interval is to be used as the best interval comprises:
selecting either the second information describing the second interval record or the first information describing the candidate best interval record based on a plurality of factors that include (i) a number of matching reference sequence locations returned by each of the interval record and the second interval record, (ii) a predetermined threshold level of reference sequence locations, or (iii) each seed length of the respective seeds that reached the hash locations storing the interval record and the second interval record.
33. The system of claim 27, wherein the interval record references one or more locations, in the seed extension table, that include data describing reference sequence locations that match the first seed of the query.
13. The system of claim 7, wherein the interval record references one or more locations, in the seed extension table, that include data describing reference sequence locations that match the first seed of the query.
34. The system of claim 33, wherein the one or more locations, in the seed extension table, that include data describing reference sequence locations that match the first seed of the query comprises: a contiguous interval, in an extension table, of reference sequence locations that match the first seed of the query.
14. The system of claim 13, wherein the one or more locations, in the seed extension table, that include data describing reference sequence locations that match the first seed of the query comprises: a contiguous interval, in an extension table, of reference sequence locations that match the first seed of the query.
39. The computer-readable medium of claim 36, the operations further comprising:
obtaining, by the mapping and aligning unit, a response to the subsequent executed query that includes information stored by a location of the hash table that is determined to be responsive to the query;
determining, by the mapping and aligning unit, whether the response to the subsequent executed query includes (i) a second extend record (ii) a second interval record, or (iii) one or more matching reference sequence locations;
based on determining, by the mapping and aligning unit, that the response to the subsequent executed query includes (i) the second extend record and (ii) the second interval record: determining, by the mapping and aligning unit, whether the extension table is to be accessed to obtain one or more matching reference sequence locations in the extension table that are referenced by the second interval record;
based on determining that the extension table is not to be accessed:
determining, by the mapping and aligning unit and using one or more heuristic rules, whether second information describing the second interval record or the first information describing the candidate best interval is to be used as the candidate best interval;
generating, by the mapping and aligning unit, a second extended seed that is an extension of the first extended seed using the second extend record;
generating, by the mapping and aligning unit, a third hash query that includes the second extended seed; and
executing, by the mapping and aligning unit, the third query of the hash table that includes the second extended seed.
19. The computer-readable medium of claim 15, the operations further comprising:
obtaining, by the mapping and aligning unit, a response to the subsequent executed query that includes information stored by a location of the hash table that is determined to be responsive to the query;
determining, by the mapping and aligning unit, whether the response to the subsequent executed query includes (i) a second extend record (ii) a second interval record, or (iii) one or more matching reference sequence locations;
based on determining, by the mapping and aligning unit, that the response to the subsequent executed query includes (i) the second extend record and (ii) the second interval record:
determining, by the mapping and aligning unit, whether the extension table is to be accessed to obtain one or more matching reference sequence locations in the extension table that are referenced by the second interval record;
based on determining that the extension table is not to be accessed:
determining, by the mapping and aligning unit and using one or more heuristic rules, whether second information describing the second interval record or the first information describing the candidate best interval is to be used as the candidate best interval;
generating, by the mapping and aligning unit, a second extended seed that is an extension of the first extended seed using the second extend record;
generating, by the mapping and aligning unit, a third hash query that includes the second extended seed; and
executing, by the mapping and aligning unit, the third query of the hash table that includes the second extended seed.
41. An integrated circuit for using a hash table to improve the mapping of sample reads to a reference sequence, the integrated circuit comprising multiple hardware logic gates that have been physically configured into one or more hardware digital logic circuits that realize functionality of a mapping and aligning unit, the integrated circuit comprising:
one or more hardware logic circuits that execute a query of a hash table, the query including a first seed, wherein the first seed includes a subset of nucleotides that were obtained from a particular read of the sample reads;
one or more hardware logic circuits that obtain a response to the executed query that includes information stored by a location of the hash table that is determined to be responsive to the query; one or more hardware logic circuits that determine whether the response to the executed query includes (i) an extend record and (ii) an interval record, wherein the interval record identifies a contiguous set of reference sequence locations, stored in an extension table, that match the first seed;
one or more hardware logic circuits that, based on a determination that the response to the executed query includes (i) an extend record and (ii) an interval record, determine whether the extension table is to be accessed to obtain one or more matching reference sequence locations in the extension table that are referenced by the interval record; and one or more hardware logic circuits that, based on determining that the extension table is to be accessed: accessing the extension table to obtain the one or more matching reference sequence locations in the extension table that are referenced by the interval record, and adding the one or more matching reference sequence locations to a seed match set.
21. An integrated circuit for using a hash table to improve the mapping of sample reads to a reference sequence, the integrated circuit comprising multiple hardware logic gates that have been physically configured into one or more hardware digital logic circuits that realize functionality of a mapping and aligning unit, the integrated circuit comprising:
one or more hardware logic circuits that execute a query of a hash table, the query including a first seed, wherein the first seed includes a subset of nucleotides that were obtained from a particular read of the sample reads;
one or more hardware logic circuits that obtain a response to the executed query that includes information stored by a location of the hash table that is determined to be responsive to the query;
one or more hardware logic circuits that determine whether the response to the executed query includes (i) an extend record and (ii) an interval record, wherein the interval record identifies a contiguous set of reference sequence locations, stored in an extension table, that match the first seed;
one or more hardware logic circuits that, based on a determination that the response to the executed query includes (i) an extend record and (ii) an interval record, determine whether the extension table is to be accessed to obtain one or more matching reference sequence locations in the extension table that are referenced by the interval record;
one or more hardware logic circuits that, based on determining that the extension table is not to be accessed, determine whether to store the first information describing the interval record in a memory device as information describing a candidate best interval, generate a first extended seed that is an extension of the first seed using the extend record, generate a subsequent hash query that includes the first extended seed, and execute the subsequent hash query of the hash table.
42. The integrated circuit of claim 41, wherein the integrated circuit is a field programmable gate array (FPGA).
22. The integrated circuit of claim 21, wherein the integrated circuit is a field programmable gate array (FPGA).
Claims 27 and 35 correspond to claim 21, and are rejected accordingly.
Claims 28 and 36 correspond to claim 22, and are rejected accordingly.
Claims 29 and 37 correspond to claim 23, and are rejected accordingly.
Claims 30 and 38 correspond to claim 24, and are rejected accordingly.
Claim 31 corresponds to claim 25, and is rejected accordingly.
Claims 32 and 40 correspond to claim 26, and are rejected accordingly.
Claim Rejections - 35 USC § 102
The following is a quotation of the appropriate paragraphs of 35 U.S.C. 102 that form the basis for the rejections under this section made in this Office action:
A person shall be entitled to a patent unless –
(a)(1) the claimed invention was patented, described in a printed publication, or in public use, on sale, or otherwise available to the public before the effective filing date of the claimed invention.
Claims 21, 27, 35 and 41-42 are rejected under 35 U.S.C. 102(a)(l) as being anticipated by Van Rooyen (AU 2016287752 B2 )
Regarding claim 21, Van Rooyen discloses: A method for using a hash table to improve the mapping of sample reads to a reference sequence, the method comprising: executing, by a mapping and aligning unit (Van Rooyen, Fig.8 , item “Dragen Chip”; [00228], line 8, “mapping and aligning hardware”), a query of a hash table (Van Rooyen, [00224], line 9 - a first query to the hash table ), the query including a first seed, wherein the first seed includes a subset of nucleotides that were obtained from a particular read of the sample reads; (Van Rooyen, [00224], line 9 - a first query to the hash table ;[00144] a hash table, such as where a selected subset of the reads, a k-mer of a selected length “k”, e.g., a seed, are placed in a hash table as keys [0012] receive a read of genomic data via one or more of the plurality of physical electrical interconnects; extract a portion of the read to generate a seed, the seed representing a subset of the sequence of nucleotides represented by the read; [00206] In such an instance, before hashing, the k-base seed (k = the number of nucleotides in the sequence) beginning at each reference offset may be extracted…line 9 - Particularly, during run-time queries, e.g., during read mapping, a procedure of hashing and looking up the smaller or larger of the query seed or its reverse complement may be implemented. )
obtaining, by the mapping and aligning unit, a response to the executed query that includes information stored by a location of the hash table that is determined to be responsive to the query; (Van Rooyen, [00224], line 9- a first query to the hash table retrieves the EXTEND record, which induces the mapper engine to re-hash at 31-base length, and query the hash table again, retrieving either a single reference position or a group of 8 positions, assuming the extended seed still matches the reference somewhere; [00227], line 3- each seed may be passed through the hash function, e.g., a CRC hash function, and queries of the hash table may be repeated with various seed lengths if one or more EXTEND records appear. The end result will be a plurality of seeds that match similar reference positions, which seeds may then be grouped into chains and aligned. )
determining, by the mapping and aligning unit, whether the response to the executed query includes (i) an extend record and (ii) an interval record, (Van Rooyen, [00227], line 4- queries of the hash table may be repeated with various seed lengths if one or more EXTEND records appear. The end result will be a plurality of seeds that match similar reference positions, which seeds may then be grouped into chains and aligned; [00221] Consequently, in various instances, an algorithm, like a Burrows-Wheeler based algorithm, may be employed so as to incrementally extend matches until the suffix interval becomes narrow enough to process a reasonable number of reference positions. [0012]receive a record from the address, the record (corresponding to “interval record”)representing position information in the genetic reference sequence; determine one or more matching positions from the read to the genetic reference sequence based on the record; [0047], e.g. line 10- such as when the primary hash table returns an extend record instructing the set of hardwired digital logic circuits to extend the at least one of the one or more seeds with the additional neighboring nucleotides; [00224] At run-time, a first query to the hash table retrieves the EXTEND record, which induces the mapper engine to re-hash at 31-base length, and query the hash table again, retrieving either a single reference position or a group of 8 positions (corresponding to “interval record”), assuming the extended seed still matches the reference somewhere.)
wherein the interval record identifies a contiguous set of reference sequence locations, stored in an extension table, that match the first seed; (Van Rooyen [00227], line 4- queries of the hash table may be repeated with various seed lengths if one or more EXTEND records appear. The end result will be a plurality of seeds that match similar reference positions, which seeds may then be grouped into chains (Note: Examiner interprets that “chains” is corresponding to “contiguous interval”) and aligned; [0012]receive a record from the address, the record (corresponding to “interval record”) representing position information in the genetic reference sequence; determine one or more matching positions from the read to the genetic reference sequence based on the record; [00222] a "seed extension" command may be saved in the table for the seed…The positions of these extended seeds may then be saved in the table. For instance, multiple reference positions matching a given seed may be stored as multiple hash records, either all in the same hash bucket, or spread by probing or chaining into additional buckets.)
based on determining, by the mapping and aligning unit, that the response to the executed query includes (i) an extend record and (ii) an interval record: determining, by the mapping and aligning unit, whether the extension table is to be accessed to obtain one or more matching reference sequence locations in the extension table that are referenced by the interval record; (Van Rooyen, [00221] so as to incrementally extend matches until the suffix interval becomes narrow enough to process a reasonable number of reference positions. Accordingly, in construction of the hash table, when a given seed occurs in a plurality, e.g., many reference positions, an EXTEND record may instead be populated, thereby encoding a selected asymmetric or symmetric extension length, and the many reference positions may be populated at various table addresses obtained by hashing the extended seeds. Hence, the EXTEND record may be populated into the hash table at the calculated address, encoding a selected extension length; [00225], line 8- At run-time where the read matches any of the 1000 reference positions, the 21-base query will retrieve the EXTEND-8 record. Upon querying for the 29-base extended seed, if it matches one or more of the 200 positions, these will be retrieved. But if the read matches one of the 800 positions, an EXTEND-20 record will be found in the table, and matching reference positions will be found by querying the table again with the 49-base extended seed; [0012]receive a record from the address, the record (corresponding to “interval record”) representing position information in the genetic reference sequence; determine one or more matching positions from the read to the genetic reference sequence based on the record;) and based on determining that the extension table is to be accessed: accessing, by the mapping and aligning unit, the extension table to obtain the one or more matching reference sequence locations in the extension table that are referenced by the interval record; (Van Rooyen, [00225], line 8- At run-time where the read matches any of the 1000 reference positions, the 21-base query will retrieve the EXTEND-8 record. Upon querying for the 29-base extended seed, if it matches one or more of the 200 positions, these will be retrieved. But if the read matches one of the 800 positions, an EXTEND-20 record will be found in the table, and matching reference positions will be found by querying the table again with the 49-base extended seed; [00221] so as to incrementally extend matches until the suffix interval becomes narrow enough to process a reasonable number of reference positions. Accordingly, in construction of the hash table, when a given seed occurs in a plurality, e.g., many reference positions, an EXTEND record may instead be populated, thereby encoding a selected asymmetric or symmetric extension length, and the many reference positions may be populated at various table addresses obtained by hashing the extended seeds. Hence, the EXTEND record may be populated into the hash table at the calculated address, encoding a selected extension length; [00222] Particularly, in certain instances, when a seed matches numerous positions in the reference, then a "seed extension" command may be saved in the table for the seed; [0012]receive a record from the address, the record (corresponding to “interval record”) representing position information in the genetic reference sequence; determine one or more matching positions from the read to the genetic reference sequence based on the record;)
and adding, by the mapping and aligning unit, the one or more matching reference sequence locations to a seed match set. (Van Rooyen, [00222], e.g. line 6- The positions of these extended seeds may then be saved in the table. For instance, multiple reference positions matching a given seed may be stored as multiple hash records, either all in the same hash bucket, or spread by probing or chaining into additional buckets)
Claims 27 and 35 correspond to claim 21, and are rejected accordingly.
Regarding claim 41, Van Rooyen discloses: An integrated circuit for using a hash table to improve the mapping of sample reads to a reference sequence, the integrated circuit comprising multiple hardware logic gates (Van Rooyen, [0037] the integrated circuit may be configured as a field programmable gate array (FPGA) having hardwired digital logic circuits) that have been physically configured into one or more hardware digital logic circuits that realize functionality of a mapping and aligning unit (Van Rooyen, [00228], line 8, “mapping and aligning hardware”), the integrated circuit comprising: (Van Rooyen, [00621] Further, all of these packaging options may be configured to facilitate easy deployment of the tightly-integrated CPU+FPGA platform such as into a cloud or datacenter server rack, which require compact/dense servers, and very high reliability/availability. Hence, in accordance with the teachings herein, there are many processing stages for data from DNA (or RNA) sequencing to mapping and aligning to variant calling)
one or more hardware logic circuits that execute a query of a hash table, (Van Rooyen, Fig.8 , item “Dragen Chip”; [00228], line 8, “mapping and aligning hardware”; [00224], line 9 - a first query to the hash table)
the query including a first seed, wherein the first seed includes a subset of nucleotides that were obtained from a particular read of the sample reads; (Van Rooyen, [00224], line 9 - a first query to the hash table ;[00144] a hash table, such as where a selected subset of the reads, a k-mer of a selected length “k”, e.g., a seed, are placed in a hash table as keys [0012] receive a read of genomic data via one or more of the plurality of physical electrical interconnects; extract a portion of the read to generate a seed, the seed representing a subset of the sequence of nucleotides represented by the read; [00206] In such an instance, before hashing, the k-base seed (k = the number of nucleotides in the sequence) beginning at each reference offset may be extracted…line 9 - Particularly, during run-time queries, e.g., during read mapping, a procedure of hashing and looking up the smaller or larger of the query seed or its reverse complement may be implemented.)
one or more hardware logic circuits that obtain a response to the executed query that includes information stored by a location of the hash table that is determined to be responsive to the query; (Van Rooyen, [00224], line 9- a first query to the hash table retrieves the EXTEND record, which induces the mapper engine to re-hash at 31-base length, and query the hash table again, retrieving either a single reference position or a group of 8 positions, assuming the extended seed still matches the reference somewhere; [00227], line 3- each seed may be passed through the hash function, e.g., a CRC hash function, and queries of the hash table may be repeated with various seed lengths if one or more EXTEND records appear. The end result will be a plurality of seeds that match similar reference positions, which seeds may then be grouped into chains and aligned. )
one or more hardware logic circuits that determine whether the response to the executed query includes (i) an extend record and (ii) an interval record, (Van Rooyen, [00227], line 4- queries of the hash table may be repeated with various seed lengths if one or more EXTEND records appear. The end result will be a plurality of seeds that match similar reference positions, which seeds may then be grouped into chains and aligned; [00221] Consequently, in various instances, an algorithm, like a Burrows-Wheeler based algorithm, may be employed so as to incrementally extend matches until the suffix interval becomes narrow enough to process a reasonable number of reference positions. [0012]receive a record from the address, the record representing position information in the genetic reference sequence; determine one or more matching positions from the read to the genetic reference sequence based on the record; [0047], e.g. line 10- such as when the primary hash table returns an extend record instructing the set of hardwired digital logic circuits to extend the at least one of the one or more seeds with the additional neighboring nucleotides;)
wherein the interval record identifies a contiguous set of reference sequence locations, stored in an extension table, that match the first seed; (Van Rooyen [00227], line 4- queries of the hash table may be repeated with various seed lengths if one or more EXTEND records appear. The end result will be a plurality of seeds that match similar reference positions, which seeds may then be grouped into chains (Note: Examiner interprets that “chains” is corresponding to “contiguous interval”) and aligned; [0012]receive a record from the address, the record (corresponding to “interval record”) representing position information in the genetic reference sequence; determine one or more matching positions from the read to the genetic reference sequence based on the record;)
one or more hardware logic circuits that, based on a determination that the response to the executed query includes (i) an extend record and (ii) an interval record, determine whether the extension table is to be accessed to obtain one or more matching reference sequence locations in the extension table that are referenced by the interval record; (Van Rooyen, [00221] so as to incrementally extend matches until the suffix interval becomes narrow enough to process a reasonable number of reference positions. Accordingly, in construction of the hash table, when a given seed occurs in a plurality, e.g., many reference positions, an EXTEND record may instead be populated, thereby encoding a selected asymmetric or symmetric extension length, and the many reference positions may be populated at various table addresses obtained by hashing the extended seeds. Hence, the EXTEND record may be populated into the hash table at the calculated address, encoding a selected extension length; [00225], line 8- At run-time where the read matches any of the 1000 reference positions, the 21-base query will retrieve the EXTEND-8 record. Upon querying for the 29-base extended seed, if it matches one or more of the 200 positions, these will be retrieved. But if the read matches one of the 800 positions, an EXTEND-20 record will be found in the table, and matching reference positions will be found by querying the table again with the 49-base extended seed; [0012]receive a record from the address, the record (corresponding to “interval record”) representing position information in the genetic reference sequence; determine one or more matching positions from the read to the genetic reference sequence based on the record;)
and one or more hardware logic circuits that, based on determining that the extension table is to be accessed: accessing the extension table to obtain the one or more matching reference sequence locations in the extension table that are referenced by the interval record, (Van Rooyen, [00225], line 8- At run-time where the read matches any of the 1000 reference positions, the 21-base query will retrieve the EXTEND-8 record. Upon querying for the 29-base extended seed, if it matches one or more of the 200 positions, these will be retrieved. But if the read matches one of the 800 positions, an EXTEND-20 record will be found in the table, and matching reference positions will be found by querying the table again with the 49-base extended seed; [00221] so as to incrementally extend matches until the suffix interval becomes narrow enough to process a reasonable number of reference positions. Accordingly, in construction of the hash table, when a given seed occurs in a plurality, e.g., many reference positions, an EXTEND record may instead be populated, thereby encoding a selected asymmetric or symmetric extension length, and the many reference positions may be populated at various table addresses obtained by hashing the extended seeds. Hence, the EXTEND record may be populated into the hash table at the calculated address, encoding a selected extension length; [00222] Particularly, in certain instances, when a seed matches numerous positions in the reference, then a "seed extension" command may be saved in the table for the seed; [0012]receive a record from the address, the record (corresponding to “interval record”) representing position information in the genetic reference sequence; determine one or more matching positions from the read to the genetic reference sequence based on the record;)
and adding the one or more matching reference sequence locations to a seed match set. (Van Rooyen, [00222], e.g. line 6- The positions of these extended seeds may then be saved in the table. For instance, multiple reference positions matching a given seed may be stored as multiple hash records, either all in the same hash bucket, or spread by probing or chaining into additional buckets)
Regarding claim 42, Van Rooyen discloses: wherein the integrated circuit is a field programmable gate array (FPGA). (Van Rooyen, [0037] the integrated circuit may be configured as a field programmable gate array (FPGA) having hardwired digital logic circuits)
Claim Rejections - 35 USC § 103
The following is a quotation of 35 U.S.C. 103 which forms the basis for all obviousness rejections set forth in this Office action:
A patent for a claimed invention may not be obtained, notwithstanding that the claimed invention is not identically disclosed as set forth in section 102, if the differences between the claimed invention and the prior art are such that the claimed invention as a whole would have been obvious before the effective filing date of the claimed invention to a person having ordinary skill in the art to which the claimed invention pertains. Patentability shall not be negated by the manner in which the invention was made.
Claims 22-26, 28-34 and 36-40 are rejected under 35 U.S.C. 103 as being unpatentable over Van Rooyen (AU 2016287752 B2 ) in view of SEMENYUK (WO 2016/141294, cited in IDS)
Regarding claim 22, Van Rooyen discloses all of the features with respect to claim 21 as outlined above. Claim 22 further recites: the method further comprising: based on determining that the extension table is not to be accessed: (Van Rooyen, [00226], line 8- When a sub-group of seed positions cannot be brought under the frequency limit by any extension under 64 bases, these positions are not individually populated in the hash table; a single HIFREQ record is populated in lieu of another EXTEND, which at run-time indicates seed mapping failure due to extreme high frequency, not due to variation from the reference; [00225], line 8- At run-time where the read matches any of the 1000 reference positions, the 21-base query will retrieve the EXTEND-8 record. Upon querying for the 29-base extended seed, if it matches one or more of the 200 positions, these will be retrieved. But if the read matches one of the 800 positions, an EXTEND-20 record will be found in the table, and matching reference positions will be found by querying the table again with the 49-base extended seed.)
generating, by the mapping and aligning unit, a first extended seed that is an extension of the first seed using the extend record; (Van Rooyen [0047], line 9-the secondary hash function may be executed by the set of hardwired digital logic circuits, such as when the primary hash table returns an extend record instructing the set of hardwired digital logic circuits to extend the at least one of the one or more seeds with the additional neighboring nucleotides.)
generating, by the mapping and aligning unit, a subsequent hash query that includes the first extended seed; (Van Rooyen, page 69, [00236], line 8- a prefix and/or suffix Tree and/or a Burrows/Wheeler transformation may be performed on the sequence data in such a manner that the index of the reference genome is constructed and/or queried as a tree-like data structure, where starting from a single-base or short subsequence of a read, the subsequence is incrementally extended within the read, each incremental extension stimulating accesses to the index, tracing a path through the tree-like data structure, until the subsequence becomes unique enough, e.g., an optimal length has been attained, and/or a leaf node is reached in the tree-like data structure)
and executing, by the mapping and aligning unit, the subsequent hash query of the hash table. (Van Rooyen, page 69, [00236], line 8- a prefix and/or suffix Tree and/or a Burrows/Wheeler transformation may be performed on the sequence data in such a manner that the index of the reference genome is constructed and/or queried as a tree-like data structure, where starting from a single-base or short subsequence of a read, the subsequence is incrementally extended within the read, each incremental extension stimulating accesses to the index, tracing a path through the tree-like data structure, until the subsequence becomes unique enough, e.g., an optimal length has been attained, and/or a leaf node is reached in the tree-like data structure; [0046] the index may include one or more hash tables,)
However, Van Rooyen does not clearly disclose:
determining, by the mapping and aligning unit, whether to store the first information describing the interval record in a memory device as information describing a candidate best interval;
However, SEMENYUK discloses:
determining, by the mapping and aligning unit, whether to store the first information describing the interval record in a memory device as information describing a candidate best interval; (SEMENYUK, page 24, third paragraph- since the hash of a string is an index for an entry in a table, the entry is a place to store information. In the desc1ibed embodiment, the entry stores the location identifiers (Note: Examiner interprets that “location identifier” is corresponding to “information describing the interval record”) for the k-mer that is hashed.; page 5, third paragraph- A search procedure is employed which looks for regions inside the graph which are similar to the read in size and which contain a substantial number of block matches with the read. An efficient search would leverage the strict order of location identifiers inside hash lists. In some embodiments, an initial set of positions to be considered is identified by taking the first (lowest-value) location identifier from each hash list in the search list. The highest-value location identifier within the set is identified. If the number of location identifiers in the set within a "look-back" interval L of that highest-value location identifier is greater than a threshold T, the range within or near the interval is a "candidate" for where the read might align; if not, it is discarded. The next set to be considered is created by replacing one of the identifiers with the next-in-order identifier belonging to the same hash list (i.e., hash list that contains the identifier being replaced); this next-in-order identifier is always the smallest identifier among all possible next-in-order identifiers (these are determined by picking one next-in-order candidate from each hash list if such identifier exists). The steps are repeated until the set consists of the highest-value location identifiers in each relevant hash list (i.e., there are no more location identifiers to be added;)
Therefore, it would have been obvious to a person of ordinary skill in the art before the effective filing date of the claimed invention to incorporate the teaching of Van Rooyen with the teaching of SEMENYUK to resolve any collisions according to known hash function techniques for collision resolution, (SEMENYUK, page 5, 1st paragraph, line 7) and also to provide an efficient search that would leverage the strict order of location identifiers inside hash lists, (SEMENYUK, page 5, third paragraph, line 3), and also to quickly and efficiently find candidate alignment regions for genomic data sequences, (SEMENYUK, page 21, 1st paragraph, line 3).
Claims 28 and 36 correspond to claim 22, and are rejected accordingly.
Regarding claim 23, Van Rooyen in view of SEMENYUK discloses all of the features with respect to claim 22 as outlined above. Claim 23 further recites: determining, by the mapping and aligning unit, that the response to the executed query includes one or more matching reference sequence locations; (Van Rooyen, [00225], line 8- At run-time where the read matches any of the 1000 reference positions, the 21-base query will retrieve the EXTEND-8 record. Upon querying for the 29-base extended seed, if it matches one or more of the 200 positions, these will be retrieved. But if the read matches one of the 800 positions, an EXTEND-20 record will be found in the table, and matching reference positions will be found by querying the table again with the 49-base extended seed.)
and based on determining, by the mapping and aligning unit, that the response to the executed query includes one or more matching reference sequence locations: adding, by the mapping and aligning unit, the one or more matching reference sequence locations to a seed match set. (Van Rooyen, [00222], e.g. line 6- The positions of these extended seeds may then be saved in the table. For instance, multiple reference positions matching a given seed may be stored as multiple hash records, either all in the same hash bucket, or spread by probing or chaining into additional buckets)
Claims 29 and 37 correspond to claim 23, and are rejected accordingly.
Regarding claim 24, Van Rooyen in view of SEMENYUK discloses all of the features with respect to claim 22 as outlined above. Van Rooyen does not clearly disclose: wherein determining, by the mapping and aligning unit, whether to store the first information describing the interval record in a memory device as information describing a candidate best interval comprises: determining, by the mapping and aligning unit, that there is not prior information describing an interval record as a candidate best interval for the particular read; and storing, by the mapping and aligning unit, the first information describing the interval record in the memory device as information describing a candidate best interval.
However, SEMENYUK discloses:
wherein determining, by the mapping and aligning unit, whether to store the first information describing the interval record in a memory device as information describing a candidate best interval comprises: determining, by the mapping and aligning unit, that there is not prior information describing an interval record as a candidate best interval for the particular read; (SEMENYUK, page 5, third paragraph, line 4- an initial set of positions to be considered is identified by taking the first (lowest-value) location identifier from each hash list in the search list.)
and storing, by the mapping and aligning unit, the first information describing the interval record in the memory device as information describing a candidate best interval. (SEMENYUK, page 24, third paragraph- since the hash of a string is an index for an entry in a table, the entry is a place to store information. In the desc1ibed embodiment, the entry stores the location identifiers (Note: Examiner interprets that “location identifier” is corresponding to “information describing the interval record”) for the k-mer that is hashed.; page 5, third paragraph- A search procedure is employed which looks for regions inside the graph which are similar to the read in size and which contain a substantial number of block matches with the read. An efficient search would leverage the strict order of location identifiers inside hash lists. In some embodiments, an initial set of positions to be considered is identified by taking the first (lowest-value) location identifier from each hash list in the search list. The highest-value location identifier within the set is identified. If the number of location identifiers in the set within a "look-back" interval L of that highest-value location identifier is greater than a threshold T, the range within or near the interval is a "candidate" for where the read might align; if not, it is discarded. The next set to be considered is created by replacing one of the identifiers with the next-in-order identifier belonging to the same hash list (i.e., hash list that contains the identifier being replaced); this next-in-order identifier is always the smallest identifier among all possible next-in-order identifiers (these are determined by picking one next-in-order candidate from each hash list if such identifier exists). The steps are repeated until the set consists of the highest-value location identifiers in each relevant hash list (i.e., there are no more location identifiers to be added;)
Therefore, it would have been obvious to a person of ordinary skill in the art before the effective filing date of the claimed invention to incorporate the teaching of Van Rooyen with the teaching of SEMENYUK to resolve any collisions according to known hash function techniques for collision resolution, (SEMENYUK, page 5, 1st paragraph, line 7) and also to provide an efficient search that would leverage the strict order of location identifiers inside hash lists, (SEMENYUK, page 5, third paragraph, line 3), and also to quickly and efficiently find candidate alignment regions for genomic data sequences, (SEMENYUK, page 21, 1st paragraph, line 3).
Claims 30 and 38 correspond to claim 24, and are rejected accordingly.
Regarding claim 25, Van Rooyen in view of SEMENYUK discloses all of the features with respect to claim 22 as outlined above. Claim 25 further recites: obtaining, by the mapping and aligning unit, a response to the subsequent executed query that includes information stored by a location of the hash table that is determined to be responsive to the query; (Van Rooyen, [00224], line 9- a first query to the hash table retrieves the EXTEND record, which induces the mapper engine to re-hash at 31-base length, and query the hash table again, retrieving either a single reference position or a group of 8 positions, assuming the extended seed still matches the reference somewhere; [00212], line 6 - the seed may go into the hash table and a plurality of matches may be returned, such as where the sample seed matches to 2, 3, 5, 10, 15, 20, or more places in the table. In such an instance, multiple records may be returned all pointing to various different locations in the reference genome where that particular seed matches, the records for these matches may either be in the same bucket, or a multiplicity of buckets may have to be probed to return all of the significant, e.g., match, results ; [00229] Hence, as the hash bucket data returns from the DRAM to each processing engine, two hash records per cycle may be decoded and processed; [0012] calculate an address within the index based on the seed; [0047], e.g. line 10 - such as when the primary hash table returns an extend record instructing the set of hardwired digital logic circuits to extend the at least one of the one or more seeds with the additional neighboring nucleotides)
determining, by the mapping and aligning unit, whether the response to the subsequent executed query includes (i) a second extend record (ii) a second interval record, and (iii) one or more matching reference sequence locations; (Van Rooyen, [00227], line 4- queries of the hash table may be repeated with various seed lengths if one or more EXTEND records appear. The end result will be a plurality of seeds that match similar reference positions, which seeds may then be grouped into chains and aligned; [00221] Consequently, in various instances, an algorithm, like a Burrows-Wheeler based algorithm, may be employed so as to incrementally extend matches until the suffix interval becomes narrow enough to process a reasonable number of reference positions. [0012]receive a record from the address, the record representing position information in the genetic reference sequence; determine one or more matching positions from the read to the genetic reference sequence based on the record; [0047], e.g. line 10- such as when the primary hash table returns an extend record instructing the set of hardwired digital logic circuits to extend the at least one of the one or more seeds with the additional neighboring nucleotides; )
based on determining, by the mapping and aligning unit, that the response to the subsequent executed query includes (i) the second extend record and (ii) the second interval record: determining, by the mapping and aligning unit, whether the extension table is to be accessed to obtain one or more matching reference sequence locations in the extension table that are referenced by the second interval record; (Van Rooyen, [00221] so as to incrementally extend matches until the suffix interval becomes narrow enough to process a reasonable number of reference positions. Accordingly, in construction of the hash table, when a given seed occurs in a plurality, e.g., many reference positions, an EXTEND record may instead be populated, thereby encoding a selected asymmetric or symmetric extension length, and the many reference positions may be populated at various table addresses obtained by hashing the extended seeds. Hence, the EXTEND record may be populated into the hash table at the calculated address, encoding a selected extension length; [00225], line 8- At run-time where the read matches any of the 1000 reference positions, the 21-base query will retrieve the EXTEND-8 record. Upon querying for the 29-base extended seed, if it matches one or more of the 200 positions, these will be retrieved. But if the read matches one of the 800 positions, an EXTEND-20 record will be found in the table, and matching reference positions will be found by querying the table again with the 49-base extended seed; [0012]receive a record from the address, the record (corresponding to “interval record”) representing position information in the genetic reference sequence; determine one or more matching positions from the read to the genetic reference sequence based on the record;)
based on determining that the extension table is not to be accessed: (Van Rooyen, [00226], line 8- When a sub-group of seed positions cannot be brought under the frequency limit by any extension under 64 bases, these positions are not individually populated in the hash table; a single HIFREQ record is populated in lieu of another EXTEND, which at run-time indicates seed mapping failure due to extreme high frequency, not due to variation from the reference; [00225], line 8- At run-time where the read matches any of the 1000 reference positions, the 21-base query will retrieve the EXTEND-8 record. Upon querying for the 29-base extended seed, if it matches one or more of the 200 positions, these will be retrieved. But if the read matches one of the 800 positions, an EXTEND-20 record will be found in the table, and matching reference positions will be found by querying the table again with the 49-base extended seed.)
generating, by the mapping and aligning unit, a second extended seed that is an extension of the first extended seed using the second extend record; (Van Rooyen [0047], line 9-the secondary hash function may be executed by the set of hardwired digital logic circuits, such as when the primary hash table returns an extend record instructing the set of hardwired digital logic circuits to extend the at least one of the one or more seeds with the additional neighboring nucleotides.)
generating, by the mapping and aligning unit, a third hash query that includes the second extended seed; (Van Rooyen, page 69, [00236], line 8- a prefix and/or suffix Tree and/or a Burrows/Wheeler transformation may be performed on the sequence data in such a manner that the index of the reference genome is constructed and/or queried as a tree-like data structure, where starting from a single-base or short subsequence of a read, the subsequence is incrementally extended within the read, each incremental extension stimulating accesses to the index, tracing a path through the tree-like data structure, until the subsequence becomes unique enough, e.g., an optimal length has been attained, and/or a leaf node is reached in the tree-like data structure)
and executing, by the mapping and aligning unit, the third query of the hash table that includes the second extended seed. (Van Rooyen, page 69, [00236], line 8- a prefix and/or suffix Tree and/or a Burrows/Wheeler transformation may be performed on the sequence data in such a manner that the index of the reference genome is constructed and/or queried as a tree-like data structure, where starting from a single-base or short subsequence of a read, the subsequence is incrementally extended within the read, each incremental extension stimulating accesses to the index, tracing a path through the tree-like data structure, until the subsequence becomes unique enough, e.g., an optimal length has been attained, and/or a leaf node is reached in the tree-like data structure; [0046] the index may include one or more hash tables,)
However, Van Rooyen does not clearly disclose:
determining, by the mapping and aligning unit and using one or more heuristic rules, whether second information describing the second interval record or the first information describing the candidate best interval is to be used as the candidate best interval;
However, SEMENYUK discloses:
determining, by the mapping and aligning unit and using one or more heuristic rules, whether second information describing the second interval record or the first information describing the candidate best interval is to be used as the candidate best interval; (SEMENYUK, page 24, third paragraph- since the hash of a string is an index for an entry in a table, the entry is a place to store information. In the desc1ibed embodiment, the entry stores the location identifiers (Note: Examiner interprets that “location identifier” is corresponding to “information describing the interval record”) for the k-mer that is hashed.; page 5, third paragraph- A search procedure is employed which looks for regions inside the graph which are similar to the read in size and which contain a substantial number of block matches with the read. An efficient search would leverage the strict order of location identifiers inside hash lists. In some embodiments, an initial set of positions to be considered is identified by taking the first (lowest-value) location identifier from each hash list in the search list. The highest-value location identifier within the set is identified. If the number of location identifiers in the set within a "look-back" interval L of that highest-value location identifier is greater than a threshold T, the range within or near the interval is a "candidate" for where the read might align; if not, it is discarded. The next set to be considered is created by replacing one of the identifiers with the next-in-order identifier belonging to the same hash list (i.e., hash list that contains the identifier being replaced); this next-in-order identifier is always the smallest identifier among all possible next-in-order identifiers (these are determined by picking one next-in-order candidate from each hash list if such identifier exists). The steps are repeated until the set consists of the highest-value location identifiers in each relevant hash list (i.e., there are no more location identifiers to be added;)
Therefore, it would have been obvious to a person of ordinary skill in the art before the effective filing date of the claimed invention to incorporate the teaching of Van Rooyen with the teaching of SEMENYUK to resolve any collisions according to known hash function techniques for collision resolution, (SEMENYUK, page 5, 1st paragraph, line 7) and also to provide an efficient search that would leverage the strict order of location identifiers inside hash lists, (SEMENYUK, page 5, third paragraph, line 3), and also to quickly and efficiently find candidate alignment regions for genomic data sequences, (SEMENYUK, page 21, 1st paragraph, line 3).
Claim 31 corresponds to claim 25, and is rejected accordingly.
Regarding claim 26, Van Rooyen in view of SEMENYUK discloses all of the features with respect to claim 25 as outlined above. Van Rooyen does not clearly disclose:
wherein determining, by the mapping and aligning unit and using one or more heuristic rules, whether the second information describing the second interval record or the first information describing the candidate best interval is to be used as the best interval comprises: selecting either the second information describing the second interval record or the first information describing the candidate best interval record based on a plurality of factors that include (i) a number of matching reference sequence locations returned by each of the interval record and the second interval record, (ii) a predetermined threshold level of reference sequence locations, or (iii) each seed length of the respective seeds that reached the hash locations storing the interval record and the second interval record.
However, SEMENYUK discloses:
wherein determining, by the mapping and aligning unit and using one or more heuristic rules, whether the second information describing the second interval record or the first information describing the candidate best interval is to be used as the best interval comprises: selecting either the second information describing the second interval record or the first information describing the candidate best interval record based on a plurality of factors that include (i) a number of matching reference sequence locations returned by each of the interval record and the second interval record, (ii) a predetermined threshold level of reference sequence locations, or (iii) each seed length of the respective seeds that reached the hash locations storing the interval record and the second interval record. (SEMENYUK, page 5, third paragraph- A search procedure is employed which looks for regions inside the graph which are similar to the read in size and which contain a substantial number of block matches with the read. An efficient search would leverage the strict order of location identifiers inside hash lists. In some embodiments, an initial set of positions to be considered is identified by taking the first (lowest-value) location identifier from each hash list in the search list. The highest-value location identifier within the set is identified. If the number of location identifiers in the set within a "look-back" interval L of that highest-value location identifier is greater than a threshold T, the range within or near the interval is a "candidate" for where the read might align; if not, it is discarded. The next set to be considered is created by replacing one of the identifiers with the next-in-order identifier belonging to the same hash list (i.e., hash list that contains the identifier being replaced); this next-in-order identifier is always the smallest identifier among all possible next-in-order identifiers (these are determined by picking one next-in-order candidate from each hash list if such identifier exists). The steps are repeated until the set consists of the highest-value location identifiers in each relevant hash list (i.e., there are no more location identifiers to be added; page 3, second paragraph, line 3- Mapping a query can comprise finding an optimal alignment between the query and the identified candidate mapping region. Finding an optimal alignment may include finding a highest-scoring trace through a multi-dimensional matrix.)
Therefore, it would have been obvious to a person of ordinary skill in the art before the effective filing date of the claimed invention to incorporate the teaching of Van Rooyen with the teaching of SEMENYUK to resolve any collisions according to known hash function techniques for collision resolution, (SEMENYUK, page 5, 1st paragraph, line 7) and also to provide an efficient search that would leverage the strict order of location identifiers inside hash lists, (SEMENYUK, page 5, third paragraph, line 3), and also to quickly and efficiently find candidate alignment regions for genomic data sequences, (SEMENYUK, page 21, 1st paragraph, line 3).
Claims 32 and 40 correspond to claim 26, and are rejected accordingly.
Regarding claim 33, Van Rooyen in view of SEMENYUK discloses all of the features with respect to claim 27 as outlined above. Claim 33 further recites: wherein the interval record references one or more locations, in the seed extension table, that include data describing reference sequence locations that match the first seed of the query. (Van Rooyen [0012]receive a record from the address, the record (corresponding to “interval record”) representing position information in the genetic reference sequence; determine one or more matching positions from the read to the genetic reference sequence based on the record; [00221] Consequently, in various instances, an algorithm, like a Burrows-Wheeler based algorithm, may be employed so as to incrementally extend matches until the suffix interval becomes narrow enough to process a reasonable number of reference positions. Accordingly, in construction of the hash table, when a given seed occurs in a plurality, e.g., many reference positions, an EXTEND record may instead be populated, thereby encoding a selected asymmetric or symmetric extension length, and the many reference positions may be populated at various table addresses obtained by hashing the extended seeds. Hence, the EXTEND record may be populated into the hash table at the calculated address, encoding a selected extension length; [00225], line 8- At run-time where the read matches any of the 1000 reference positions, the 21-base query will retrieve the EXTEND-8 record. Upon querying for the 29-base extended seed, if it matches one or more of the 200 positions, these will be retrieved. But if the read matches one of the 800 positions, an EXTEND-20 record will be found in the table, and matching reference positions will be found by querying the table again with the 49-base extended seed;)
Regarding claim 34, Van Rooyen in view of SEMENYUK discloses all of the features with respect to claim 33 as outlined above. Claim 34 further recites: wherein the one or more locations, in the seed extension table, that include data describing reference sequence locations that match the first seed of the query comprises: a contiguous interval, in an extension table, of reference sequence locations that match the first seed of the query. (Van Rooyen [00227], line 4- queries of the hash table may be repeated with various seed lengths if one or more EXTEND records appear. The end result will be a plurality of seeds that match similar reference positions, which seeds may then be grouped into chains (Note: Examiner interprets that “chains” is corresponding to “contiguous interval”) and aligned; [0012]receive a record from the address, the record (corresponding to “interval record”) representing position information in the genetic reference sequence; determine one or more matching positions from the read to the genetic reference sequence based on the record;)
Regarding claim 39, Van Rooyen in view of SEMENYUK discloses all of the features with respect to claim 36 as outlined above. Claim 39 further recites: the operations further comprising: obtaining, by the mapping and aligning unit, a response to the subsequent executed query that includes information stored by a location of the hash table that is determined to be responsive to the query; (Van Rooyen, [00224], line 9- a first query to the hash table retrieves the EXTEND record, which induces the mapper engine to re-hash at 31-base length, and query the hash table again, retrieving either a single reference position or a group of 8 positions, assuming the extended seed still matches the reference somewhere; [00212], line 6 - the seed may go into the hash table and a plurality of matches may be returned, such as where the sample seed matches to 2, 3, 5, 10, 15, 20, or more places in the table. In such an instance, multiple records may be returned all pointing to various different locations in the reference genome where that particular seed matches, the records for these matches may either be in the same bucket, or a multiplicity of buckets may have to be probed to return all of the significant, e.g., match, results ; [00229] Hence, as the hash bucket data returns from the DRAM to each processing engine, two hash records per cycle may be decoded and processed; [0012] calculate an address within the index based on the seed; [0047], e.g. line 10 - such as when the primary hash table returns an extend record instructing the set of hardwired digital logic circuits to extend the at least one of the one or more seeds with the additional neighboring nucleotides)
determining, by the mapping and aligning unit, whether the response to the subsequent executed query includes (i) a second extend record (ii) a second interval record, or (iii) one or more matching reference sequence locations; (Van Rooyen, [00227], line 4- queries of the hash table may be repeated with various seed lengths if one or more EXTEND records appear. The end result will be a plurality of seeds that match similar reference positions, which seeds may then be grouped into chains and aligned; [00221] Consequently, in various instances, an algorithm, like a Burrows-Wheeler based algorithm, may be employed so as to incrementally extend matches until the suffix interval becomes narrow enough to process a reasonable number of reference positions. [0012]receive a record from the address, the record representing position information in the genetic reference sequence; determine one or more matching positions from the read to the genetic reference sequence based on the record; [0047], e.g. line 10- such as when the primary hash table returns an extend record instructing the set of hardwired digital logic circuits to extend the at least one of the one or more seeds with the additional neighboring nucleotides; )
based on determining, by the mapping and aligning unit, that the response to the subsequent executed query includes (i) the second extend record and (ii) the second interval record: determining, by the mapping and aligning unit, whether the extension table is to be accessed to obtain one or more matching reference sequence locations in the extension table that are referenced by the second interval record; (Van Rooyen, [00221] so as to incrementally extend matches until the suffix interval becomes narrow enough to process a reasonable number of reference positions. Accordingly, in construction of the hash table, when a given seed occurs in a plurality, e.g., many reference positions, an EXTEND record may instead be populated, thereby encoding a selected asymmetric or symmetric extension length, and the many reference positions may be populated at various table addresses obtained by hashing the extended seeds. Hence, the EXTEND record may be populated into the hash table at the calculated address, encoding a selected extension length; [00225], line 8- At run-time where the read matches any of the 1000 reference positions, the 21-base query will retrieve the EXTEND-8 record. Upon querying for the 29-base extended seed, if it matches one or more of the 200 positions, these will be retrieved. But if the read matches one of the 800 positions, an EXTEND-20 record will be found in the table, and matching reference positions will be found by querying the table again with the 49-base extended seed; [0012]receive a record from the address, the record (corresponding to “interval record”) representing position information in the genetic reference sequence; determine one or more matching positions from the read to the genetic reference sequence based on the record;)
based on determining that the extension table is not to be accessed: (Van Rooyen, [00226], line 8- When a sub-group of seed positions cannot be brought under the frequency limit by any extension under 64 bases, these positions are not individually populated in the hash table; a single HIFREQ record is populated in lieu of another EXTEND, which at run-time indicates seed mapping failure due to extreme high frequency, not due to variation from the reference; [00225], line 8- At run-time where the read matches any of the 1000 reference positions, the 21-base query will retrieve the EXTEND-8 record. Upon querying for the 29-base extended seed, if it matches one or more of the 200 positions, these will be retrieved. But if the read matches one of the 800 positions, an EXTEND-20 record will be found in the table, and matching reference positions will be found by querying the table again with the 49-base extended seed.)
generating, by the mapping and aligning unit, a second extended seed that is an extension of the first extended seed using the second extend record; (Van Rooyen [0047], line 9-the secondary hash function may be executed by the set of hardwired digital logic circuits, such as when the primary hash table returns an extend record instructing the set of hardwired digital logic circuits to extend the at least one of the one or more seeds with the additional neighboring nucleotides.)
generating, by the mapping and aligning unit, a third hash query that includes the second extended seed; (Van Rooyen, page 69, [00236], line 8- a prefix and/or suffix Tree and/or a Burrows/Wheeler transformation may be performed on the sequence data in such a manner that the index of the reference genome is constructed and/or queried as a tree-like data structure, where starting from a single-base or short subsequence of a read, the subsequence is incrementally extended within the read, each incremental extension stimulating accesses to the index, tracing a path through the tree-like data structure, until the subsequence becomes unique enough, e.g., an optimal length has been attained, and/or a leaf node is reached in the tree-like data structure)
and executing, by the mapping and aligning unit, the third query of the hash table that includes the second extended seed. (Van Rooyen, page 69, [00236], line 8- a prefix and/or suffix Tree and/or a Burrows/Wheeler transformation may be performed on the sequence data in such a manner that the index of the reference genome is constructed and/or queried as a tree-like data structure, where starting from a single-base or short subsequence of a read, the subsequence is incrementally extended within the read, each incremental extension stimulating accesses to the index, tracing a path through the tree-like data structure, until the subsequence becomes unique enough, e.g., an optimal length has been attained, and/or a leaf node is reached in the tree-like data structure; [0046] the index may include one or more hash tables,)
However, Van Rooyen does not clearly disclose:
determining, by the mapping and aligning unit and using one or more heuristic rules, whether second information describing the second interval record or the first information describing the candidate best interval is to be used as the candidate best interval;
However, SEMENYUK discloses:
determining, by the mapping and aligning unit and using one or more heuristic rules, whether second information describing the second interval record or the first information describing the candidate best interval is to be used as the candidate best interval; (SEMENYUK, page 24, third paragraph- since the hash of a string is an index for an entry in a table, the entry is a place to store information. In the desc1ibed embodiment, the entry stores the location identifiers (Note: Examiner interprets that “location identifier” is corresponding to “information describing the interval record”) for the k-mer that is hashed.; page 5, third paragraph- A search procedure is employed which looks for regions inside the graph which are similar to the read in size and which contain a substantial number of block matches with the read. An efficient search would leverage the strict order of location identifiers inside hash lists. In some embodiments, an initial set of positions to be considered is identified by taking the first (lowest-value) location identifier from each hash list in the search list. The highest-value location identifier within the set is identified. If the number of location identifiers in the set within a "look-back" interval L of that highest-value location identifier is greater than a threshold T, the range within or near the interval is a "candidate" for where the read might align; if not, it is discarded. The next set to be considered is created by replacing one of the identifiers with the next-in-order identifier belonging to the same hash list (i.e., hash list that contains the identifier being replaced); this next-in-order identifier is always the smallest identifier among all possible next-in-order identifiers (these are determined by picking one next-in-order candidate from each hash list if such identifier exists). The steps are repeated until the set consists of the highest-value location identifiers in each relevant hash list (i.e., there are no more location identifiers to be added;)
Therefore, it would have been obvious to a person of ordinary skill in the art before the effective filing date of the claimed invention to incorporate the teaching of Van Rooyen with the teaching of SEMENYUK to resolve any collisions according to known hash function techniques for collision resolution, (SEMENYUK, page 5, 1st paragraph, line 7) and also to provide an efficient search that would leverage the strict order of location identifiers inside hash lists, (SEMENYUK, page 5, third paragraph, line 3), and also to quickly and efficiently find candidate alignment regions for genomic data sequences, (SEMENYUK, page 21, 1st paragraph, line 3).
Conclusion
THIS ACTION IS MADE FINAL. Applicant is reminded of the extension of time policy as set forth in 37 CFR 1.136(a).
A shortened statutory period for reply to this final action is set to expire THREE MONTHS from the mailing date of this action. In the event a first reply is filed within TWO MONTHS of the mailing date of this final action and the advisory action is not mailed until after the end of the THREE-MONTH shortened statutory period, then the shortened statutory period will expire on the date the advisory action is mailed, and any extension fee pursuant to 37 CFR 1.136(a) will be calculated from the mailing date of the advisory action. In no event, however, will the statutory period for reply expire later than SIX MONTHS from the mailing date of this final action.
Any inquiry concerning this communication or earlier communications from the examiner should be directed to Faezeh Forouharnejad whose telephone number is (571)270-7416. The examiner can normally be reached on generally Monday through Friday.
If attempts to reach the examiner by telephone are unsuccessful, the examiner’s supervisor, Shah Sanjiv can be reached on (571)272-4098. The fax phone number for the organization where this application or proceeding is assigned is 571-273-8300.
Information regarding the status of an application may be obtained from Patent Center and the Private Patent Application Information Retrieval (PAIR) system. Status information for published applications may be obtained from Patent Center or Private PAIR. Status information for unpublished applications is available through Patent Center and Private PAIR to authorized users only. Should you have questions about access to the Private PAIR system, contact the Electronic Business Center (EBC) at 866-217-9197 (toll-free)
/F.F. /
Examiner, Art Unit 2166
/SANJIV SHAH/ Supervisory Patent Examiner, Art Unit 2166