DETAILED ACTION
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 .
Remarks
In response to communications sent November 9, 2022, claim(s) 1-19 and 27 are pending in this application; of these claims 1, 19, and 27 are in independent form. Claims 20 to 26 and 28-38 are cancelled.
Response to Amendment
The preliminary amendments to the Specification filed March 31, 2022 are acknowledged and have been entered into the record.
Priority
Applicant’s claim for the benefit of a prior-filed application under 35 U.S.C. 119(e) or under 35 U.S.C. 120, 121, 365(c), or 386(c) is acknowledged. Applicant has indeed complied with one or more conditions for receiving the benefit of an earlier filing date under 35 U.S.C. 119(e) as follows:
The claims of the prior-filed application, Application No. 62/903,351 appears similar to claims of the instant application. Hence, the benefit of the early filing date is assumed despite that the provisional patent application includes only 96 paragraphs, whereas the instant application is 133 paragraphs. For example, paragraphs [0120]-[0133] of the instant application do not have a corresponding section in the provisional patent application. Hence, there are at least some elements in the specification of the instant application that are not in the provisional patent application. Nevertheless, there is support for the claimed invention of the instant application.
Drawings
The drawings are objected to under 37 CFR 1.83(a) because they fail to show the labels of “K-mers” and “variants” in Figures 1A, 1B, 1C, and 3 as described in the specification at Paragraph [0066] and [0069]. Any structural detail that is essential for a proper understanding of the disclosed invention should be shown in the drawing. MPEP § 608.02(d). Corrected drawing sheets in compliance with 37 CFR 1.121(d) are required in reply to the Office action to avoid abandonment of the application. Any amended replacement drawing sheet should include all of the figures appearing on the immediate prior version of the sheet, even if only one figure is being amended. The figure or figure number of an amended drawing should not be labeled as “amended.” If a drawing figure is to be canceled, the appropriate figure must be removed from the replacement sheet, and where necessary, the remaining figures must be renumbered and appropriate changes made to the brief description of the several views of the drawings for consistency. Additional replacement sheets may be necessary to show the renumbering of the remaining figures. Each drawing sheet submitted after the filing date of an application must be labeled in the top margin as either “Replacement Sheet” or “New Sheet” pursuant to 37 CFR 1.121(d). If the changes are not accepted by the examiner, the applicant will be notified and informed of any required corrective action in the next Office action. The objection to the drawings will not be held in abeyance.
Specification
The incorporation of essential material in the specification by reference to an unpublished U.S. application, foreign application or patent, or to a publication is improper. Applicant is required to amend the disclosure to include the material incorporated by reference, if the material is relied upon to overcome any objection, rejection, or other requirement imposed by the Office. The amendment must be accompanied by a statement executed by the applicant, or a practitioner representing the applicant, stating that the material being inserted is the material previously incorporated by reference and that the amendment contains no new matter. 37 CFR 1.57(g).
See Applicant’s Specification at Paragraphs [0062]-[0063], [0065], [0082], and [0104].
The disclosure is objected to because of the following informalities: Paragraph [0126], second paragraph, the Specification does not underline x when referring to the hashed value of derived from x. The omitted underlines are in two places in the sentence. The Examiner believes that the Applicant intended the second sentence to recite:
“To unhash a hashed K-mer x, compute x = V * x (mod |Xk|).”
Appropriate correction is required.
Information Disclosure Statement
The Information Disclosure Statement(s) is/are acknowledged and the references contained therein have been considered by the Examiner. This includes the Information Disclosure Statements(s) filed on: November 9, 2022.
Claim Rejections - 35 USC § 112
The following is a quotation of 35 U.S.C. 112(b):
(b) CONCLUSION.—The specification shall conclude with one or more claims particularly pointing out and distinctly claiming the subject matter which the inventor or a joint inventor regards as the invention.
The following is a quotation of 35 U.S.C. 112 (pre-AIA ), second paragraph:
The specification shall conclude with one or more claims particularly pointing out and distinctly claiming the subject matter which the applicant regards as his invention.
Claims 1-19 and 27 are rejected under 35 U.S.C. 112(b) or 35 U.S.C. 112 (pre-AIA ), second paragraph, as being indefinite for failing to particularly point out and distinctly claim the subject matter which the inventor or a joint inventor (or for applications subject to pre-AIA 35 U.S.C. 112, the applicant), regards as the invention.
Claim 1, 19, and 27 recite the limitation "remaining portion" in line 8, 5, and 6 respectively. There is insufficient antecedent basis for this limitation in the claim. There are several possible meanings of the phrase “remaining portion”:
The phrase “remaining portion” may mean a “remainder” after division, which is a step that the Specification discussed extensively. However, if this is what applicant intended, then it is unclear why the remainder would be stored in a memory slot instead of the remainder influencing the address of the memory slot.
On the other hand, the phrase “remaining portion” may mean that the suffix after the prefix of the K-mer is stored in the memory slot. This is consistent with Para [0077] of the Specification, which describes “remaining bits.” However, the interpretation seems to be in contradiction to dependent claims 5 and 6, which recite that metadata is included in the data structure. The Specification at Para [0024] teaches that the metadata would be stored in the memory slots. But if there are already a “remaining portion” stored in the slots, how would the metadata stored in the same memory location as the “remaining bits”?
The term “remaining portion” may mean “metadata”. However, one of ordinary skill in the art would not assume that a remaining portion encompasses metadata, given the ambiguity above.
Claims 2-18 are rejected because they depend from the rejected claim 1.
Claim 3 and 4 are rejected under 35 U.S.C. 112(b) or 35 U.S.C. 112 (pre-AIA ), second paragraph, as being indefinite for failing to particularly point out and distinctly claim the subject matter which the inventor or a joint inventor (or for applications subject to pre-AIA 35 U.S.C. 112, the applicant), regards as the invention.
Claim 3 and 4 each recite that “each slot stores and invertible function…” However, the Specification describes data, not executable functions, as being stored in each slot. Therefore, it is unclear whether the Applicant intends for a particular value to be stored in the slot that is derived or related to an invertible function, as part of the claim scope.
The following is a quotation of 35 U.S.C. 112(d):
(d) REFERENCE IN DEPENDENT FORMS.—Subject to subsection (e), a claim in dependent form shall contain a reference to a claim previously set forth and then specify a further limitation of the subject matter claimed. A claim in dependent form shall be construed to incorporate by reference all the limitations of the claim to which it refers.
The following is a quotation of pre-AIA 35 U.S.C. 112, fourth paragraph:
Subject to the following paragraph [i.e., the fifth paragraph of pre-AIA 35 U.S.C. 112], a claim in dependent form shall contain a reference to a claim previously set forth and then specify a further limitation of the subject matter claimed. A claim in dependent form shall be construed to incorporate by reference all the limitations of the claim to which it refers.
Claims 2-4 are rejected under 35 U.S.C. 112(d) or pre-AIA 35 U.S.C. 112, 4th paragraph, as being of improper dependent form for failing to further limit the subject matter of the claim upon which it depends, or for failing to include all the limitations of the claim upon which it depends. Dependent claim 2 redefines the “prefix portion” of the K-mer as a hash in a way that causes the address to differ from the address of claim 1, in which the “prefix portion” is a prefix of a K-mer that is an address determined without hashing. Applicant may cancel the claim(s), amend the claim(s) to place the claim(s) in proper dependent form, rewrite the claim(s) in independent form, or present a sufficient showing that the dependent claim(s) complies with the statutory requirements.
Dependent claims 3 and 4 are rejected because they depend from claim 2.
Claims 5 and 6 rejected under 35 U.S.C. 112(d) or pre-AIA 35 U.S.C. 112, 4th paragraph, as being of improper dependent form for failing to further limit the subject matter of the claim upon which it depends, or for failing to include all the limitations of the claim upon which it depends. Claims 5 and 6 store “metadata” in the “data structure”. However claim 1 defines the “data structure” as comprising “memory slots” that are already populated with the “remaining portion of the K-mer sequence”. It is not possible to limit the slot element to include the “metadata” if there is already a “remaining portion of the K-mer sequence” in the slot element. Applicant may cancel the claim(s), amend the claim(s) to place the claim(s) in proper dependent form, rewrite the claim(s) in independent form, or present a sufficient showing that the dependent claim(s) complies with the statutory requirements.
Claim Analysis - 35 USC § 101
Claim 19, which is directed to a data structure. The Examiner interprets this as a storage medium, such as random access memory and magnetic tape, which are statutory medium. Because the storage media comprises addressable slots, the Examiner interprets the media as not encompassing non-transitory signals.
No rejection is made on the grounds of a judicial exception to subject matter eligibility. This is because the data structures in the claim improves the functioning of the computer itself.
Suggestions for Compact Prosecution
The Examiner noticed that Para [0083] recites that a “combination of Fibonacci hashing and linear hash collision resolution provide many improvements in computer functionality over prior methods.” However, these elements are not currently recited in the claims as a combination. Their inclusion, in the bioinformatics context of other elements, would be relevant for the Examiner to determine novelty and to determine whether the claimed invention improves the functioning of the computer itself when contemplating the judicial exceptions to subject matter eligibility.
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.
Claim(s) 1-13, 15, 17-19, and 27 is/are rejected under 35 U.S.C. 102(a)(1) as being anticipated by “Liu”. The “Liu” reference is:
Liu, Jinlin, Qiang Chen, and Chen Zhang. "K-mer index of DNA sequence based on hash algorithm." International Journal on Computational Science & Applications (IJCSA) 5.4 (2015): 19-28..
As to claim 1, Liu teaches a method for indexing K-mers, comprising:
obtaining a nucleotide sequence (Liu Abstract: reading DNA sequences in limited memory);
defining a K-mer size (Liu page 23: “Input K”); and
indexing K-mers in the nucleotide sequence according to the K-mer size (Liu Abstract: establishing a hash index using the length of the k-mer), wherein the K-mers are stored in a data structure defined by a plurality of slots (Liu Abstract: storing K-mers in a hash table), and wherein each slot has an address and stores data (by definition, hash tables have addresses and storage; see also Liu page 22 last paragraph), the address is defined by a prefix portion of each K-mer (Liu page 22 last paragraph: the k-mer is hashed to calculate the address), and the slot stores the remaining portion of the K-mer sequence (the slots store non-functional descriptive material with no functional relationship to the computer substrate; see MPEP § 2111.05 regarding the interpretation of nonfunctional descriptive material).
As to claim 2, Liu teaches the method of claim 1, wherein the prefix portion of each K-mer is defined as a quotient upon division by a parameter plus a number not exceeding a maximum number of hash collisions (Liu page 22 section 4.1: a hash function using the zipper algorithm and address conflict handling).
As to claim 3, Liu teaches the method of claim 2, wherein the parameter is integer-valued, and each slot stores an invertible function of the remainder of a K-mer upon division by the integer-valued parameter (Liu page 22 section 4.1: a hash function using the zipper algorithm and address conflict handling).
As to claim 4, Liu teaches the method of claim 2, wherein the parameter is integer-valued, and the number is an integer h between 0 and J, where J equals one less maximum number of hash collisions, and each slot stores an invertible function of the remainder of a K-mer upon division by the integer-valued parameter and h (Liu page 22 section 4.1: a hash function using the zipper algorithm and address conflict handling).
As to claim 5, Liu teaches the method of claim 1, wherein the data structure further includes metadata associated with each K-mer stored therein (the metadata is nonfunctional descriptive material with no functional relationship to the computer substrate; see MPEP § 2111.05 regarding the interpretation of nonfunctional descriptive material).
As to claim 6, Liu teaches the method of claim 5, wherein the metadata comprises at least one of the following: source, population, species, date of acquisition, sequencing platform, data type, and identity of the sample (the metadata is nonfunctional descriptive material with no functional relationship to the computer substrate; see MPEP § 2111.05 regarding the interpretation of nonfunctional descriptive material).
As to claim 7, Liu teaches the method of claim 1, further comprising updating the data structure with additional sequence data (Liu Page 23: flowchart for updating a hash table with new data iteratively).
As to claim 8, Liu teaches the method of claim 7, wherein the updating step is accomplished by:
obtaining additional sequence data (Liu Page 23: repeatedly reading data); and indexing K-mers in the additional sequence data according to the K-mer size (Liu Page 23: flowchart for updating a hash table with new data iteratively), wherein the K-mers are stored in the data structure (Liu page 23: storing data in the hash table).
As to claim 9, Liu teaches the method of claim 1, wherein the nucleotide sequence is a whole genome sequence (Liu Page 19, Introduction: applicability of the hash table to “all of the information in the genome”).
As to claim 10, Liu teaches the method of claim 1, wherein the nucleotide sequence is a human reference sequence (Liu Page 19, Introduction: human generated sequence data).
As to claim 11, Liu teaches the method of claim 1, wherein the K-mer size is 11-150 base pairs (Liu Page 24-25 Table 4.1 illustrates a K-mer size 12).
As to claim 12, Liu teaches the method of claim 1, wherein each K-mer is stored as a binary integer representing of the underlying DNA sequence of each K-mer (Liu page 20 section 3.2: bases are converted to binary digits).
As to claim 13, Liu teaches the method of claim 12, wherein the K-mers are converted to generate a more uniform distribution (Liu page 22 section 4.1: a hash function using the zipper algorithm for distributing to memory addresses).
As to claim 15, Liu teaches the method of claim 14, further comprising retrieving at least one K-mer from the data structure (Liu page 27: the conclusion mentions the application of querying the hash table; Liu Page 26 illustrates outputting a set of K-mers associated with a genomic data entry event).
As to claim 17, Liu teaches the method of claim 1, wherein collisions occurring during the indexing step are handled by scanning to a lower order slot and incrementing the integer value of the remaining portion of the K-mer by a value equal to a difference between the prefix and the lower order slot (Liu page 22 section 4.1: a hash function using the zipper algorithm that handles address conflicts).
As to claim 18, Liu teaches the method of claim 1, wherein a maximum number of hash collisions results in data being stored in another data structure (Liu Page 23 flowchart: freeing heap space during hash table formation).
As to claim 19, Liu teaches a data structure for storing genetic or genomic data (Liu Abstract: reading DNA sequences in limited memory), comprising:
a plurality of memory slots and a plurality of K-mers (Liu Abstract: storing K-mers in a hash table), wherein each memory slot is associated with an address (by definition, hash tables have addresses and storage; see also Liu page 22 last paragraph), wherein each K-mer is stored in a specific memory slot based on an integer value of a prefix of the K-mer (Liu page 22 last paragraph: the k-mer is hashed to calculate the address), and the remaining portion of the K-mer is stored in the memory slot (the slots store non-functional descriptive material with no functional relationship to the computer substrate; see MPEP § 2111.05 regarding the interpretation of nonfunctional descriptive material).
As to claim 27, Liu teaches a method to identify genomic events, comprising:
accessing a data structure (Liu Abstract: reading DNA sequences in limited memory), wherein the data structure comprises a plurality of memory slots and a plurality of K-mers (Liu Abstract: storing K-mers in a hash table), wherein each memory slot is associated with an address (by definition, hash tables have addresses and storage; see also Liu page 22 last paragraph), wherein each K-mer is stored in a specific memory slot based on an integer value of a prefix of the K-mer (Liu page 22 last paragraph: the k-mer is hashed to calculate the address), and the remaining portion of the K-mer is stored in the memory slot (the slots store non-functional descriptive material with no functional relationship to the computer substrate; see MPEP § 2111.05 regarding the interpretation of nonfunctional descriptive material);
querying the data structure to obtain a set of K-mers associated with a genomic event (Liu page 27: the conclusion mentions the application of querying the hash table); and outputting the set of K-mers associated with the genomic event (Liu Page 26 illustrates outputting a set of K-mers associated with a genomic data entry event).
Conclusion
The prior art made of record and not relied upon is considered pertinent to applicant's disclosure.
US 20170169159 A1: head hash and tail has to identify repetitions in between from DNA sequences
US 20090270277 A1: k-mer storage without hashing
US 20190172553 A1: Para [0084] teaches using a hash table to find annotations pertinent to the hash table
US 20230282309 A1 (relies on provisional date): hashing sub-sequence to group sequences to collapse sequencing reads
WO-2011073680-A1: DNA hash table with collision resolution
US 2015/0331619 A1: See element S11 at Para [0118] for storing a remainder after a prefix.
Pan, Tony, et al. "Kmerind: A flexible parallel library for k-mer indexing of biological sequences on distributed memory systems." Proceedings of the 7th ACM international conference on bioinformatics, computational biology, and health informatics. 2016. (Year: 2016)
Mohamadi, Hamid, et al. "ntHash: recursive nucleotide hashing." Bioinformatics 32.22 (2016): 3492-3494.
Any inquiry concerning this communication or earlier communications from the examiner should be directed to Jesse P Frumkin whose telephone number is (571)270-1849. The examiner can normally be reached Monday - Saturday, 10-5 ET.
Examiner interviews are available via telephone, in-person, and video conferencing using a USPTO supplied web-based collaboration tool. To schedule an interview, applicant is encouraged to use the USPTO Automated Interview Request (AIR) at http://www.uspto.gov/interviewpractice.
If attempts to reach the examiner by telephone are unsuccessful, the examiner’s supervisor, Olivia Wise can be reached at (571) 272-2249. The fax phone number for the organization where this application or proceeding is assigned is 571-273-8300.
Information regarding the status of published or unpublished applications may be obtained from Patent Center. Unpublished application information in Patent Center is available to registered users. To file and manage patent submissions in Patent Center, visit: https://patentcenter.uspto.gov. Visit https://www.uspto.gov/patents/apply/patent-center for more information about Patent Center and https://www.uspto.gov/patents/docx for information about filing in DOCX format. For additional questions, contact the Electronic Business Center (EBC) at 866-217-9197 (toll-free). If you would like assistance from a USPTO Customer Service Representative, call 800-786-9199 (IN USA OR CANADA) or 571-272-1000.
/JESSE P FRUMKIN/Primary Examiner, Art Unit 1685 September 20, 2025