DETAILED ACTION
Notice of 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 .
In the event the determination of the status of the application as subject to AIA 35 U.S.C. 102 and 103 (or as subject to pre-AIA 35 U.S.C. 102 and 103) is incorrect, any correction of the statutory basis (i.e., changing from AIA to pre-AIA ) for the rejection will not be considered a new ground of rejection if the prior art relied upon, and the rationale supporting the rejection, would be the same under either status.
Status of the Claims
Claims 1-20 are pending.
Claims 5 and 12 are objected to.
Claims 1-20 are rejected.
Priority
This US Application 17/832,252 (06/03/2022) claims priority from Foreign Applications KR10-2021-0072711 (06/04/2021) and KR10-2022-0048190 (04/19/2022), as reflected in the filing receipt mailed on 06/13/2022. The claims to the benefit of priority are acknowledged; and the effective filing date of claims 1-20 is 06/04/2021.
Information Disclosure Statement
The information disclosure statements (IDS) submitted on 06/03/2022 was considered by the examiner.
Claim objections
Claims 1, 7 and 19 are objected to because of the following informalities:
Colons should begin lists in which list elements are separated by newlines, e.g. claim 1 "performs" should be followed by a colon, and the same applies in claims 7 and 19.
Appropriate correction is required.
Claim Rejections - 35 USC § 112(b)
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.
Claims 1-9, 11 and 17-20 are rejected under 35 U.S.C. 112(b)as being indefinite for failing to particularly point out and distinctly claim the subject matter the invention. Dependent claims are rejected similarly, unless otherwise noted below. The following issues cause the respective claims to be rejected under 112(b) as indefinite:
1. In claim 5, the grammatical construction and punctuation are unclear such that (i) it is unclear what is modified by the recited "which are extracted...," e.g. whether that "which" clause modifies the preceding "seeds," "hash entries," etc. And, (ii) it is unclear how the recited "...and a multi-location table..." relates to the rest of the claim, e.g. to what list does this recitation belong, "seeds" and "...table" or "hash entries" and "...table," etc. If the list to which "...table" belongs contains only two list elements, then the comma before "and" is improper, i.e. "X and Y" not "X, and Y."
2. Claim 9 recites:
"when the exact match ... is not found in the reference genome, the program performs finding a maximal exact match … based on the essential index; ... when finding the maximal exact match is performed, the program accelerates an initial step of finding the maximal exact match based on a second index of the additional index."
It is unclear if the occurrences of "exact match" refer to the same type or different type of matches, leading to the following indefiniteness issues:
It is not clear whether each instance must refer to matching the nucleotide sequence to the reference genome. If so, it is not clear how an instance where an exact match does not occur can call for a second check for the existence of an exact match, given that it's already been certified that the exact match did not take place in the first check.
It is not clear whether all instances matching the nucleotide sequences to the reference genome must be based on different index sources (e.g. additional index vs essential index). There are three instances that call for checks regarding exact matches. The relationship between each index source being used is unclear in the recited "…based on the essential index; ... when finding the maximal exact match is performed, the program accelerates an initial step of finding the maximal exact match based on a second index of the additional index."
For compact examination, all described instances of exact matches are interpreted as exact matches made on any index source.
3. Claims 4 and 11 recite "essential part" in which the recited "essential" is a term of relative or vague degree or form of association, neither defined in the specification (e.g. [12-15]) nor having a well-known and sufficiently particular definition in the art and in the instant context. Also, the preceding recitation of "essential index" (e.g. claim 1, 1st "loading" step and also claim 2) does not clearly resolve this issue. (MPEP 2173.05(b) pertains.)
4. Claim 9 lacks clarity regarding the recited "match" finding, reciting "when the exact match of the target nucleotide sequence is not found..." and "...finding a maximal exact match..." It is not clear what kind of match is not found in order for the maximal exact match to be found. This rejection may be overcome by amending the claims to clarify recitation of the conditional expression. Claim 17 is rejected similarly.
Claim Rejections - 35 USC § 101
35 U.S.C. 101 reads as follows:
Whoever invents or discovers any new and useful process, machine, manufacture, or composition of matter, or any new and useful improvement thereof, may obtain a patent therefor, subject to the conditions and requirements of this title.
Claims 1-20 are rejected under 35 USC § 101 because the claimed inventions are directed to one or more Judicial Exceptions (JEs) without significantly more. Regarding JEs, "Claims directed to nothing more than abstract ideas..., natural phenomena, and laws of nature are not eligible for patent protection" (MPEP 2106.04 §I). Abstract ideas include mathematical concepts and procedures for evaluating, analyzing or organizing information, which are a type of mental process (MPEP 2106.04(a)(2)).
101 background
MPEP 2106 organizes JE analysis into Steps 1, 2A (Prong One & Prong Two), and 2B as analyzed below. MPEP 2106 and the following USPTO website provide further explanation and case law citations: uspto.gov/patent/laws-and-regulations/examination-policy/examination-guidance-and-training-materials.
Step 1: Are the claims directed to a process, machine, manufacture, or composition of matter (MPEP 2106.03)?
Step 2A, Prong One: Do the claims recite a judicially recognized exception, i.e., a law of nature, a natural phenomenon, or an abstract idea (MPEP 2106.04(a-c))?
Step 2A, Prong Two: If the claims recite a judicial exception under Prong One, then is the judicial exception integrated into a practical application by an additional element (MPEP 2106.04(d))?
Step 2B: Do the claims recite a non-conventional arrangement of elements in addition to any identified judicial exception(s) (MPEP 2106.05)?
Analysis of instant claims
Step 1: Are the claims directed to a 101 process, machine, manufacture, or composition of matter (MPEP 2106.03)?
The instant claims are directed to an apparatus (claims 1-9), and a method (claims 10-20), each of which falls within one of the categories of statutory subject matter.
[Step 1: claims 1-20 – Yes].
Step 2A, Prong One: Do the claims recite a judicially recognized exception, i.e., a law of nature, a natural phenomenon, or an abstract idea (MPEP 2106.04(a-c))?
Background
With respect to Step 2A, Prong One, the claims recite judicial exceptions in the form of abstract ideas. MPEP § 2106.04(a)(2) further explains that abstract ideas are defined as:
• mathematical concepts (mathematical formulas or equations, mathematical relationships
and mathematical calculations) (MPEP 2106.04(a)(2)(I));
• certain methods of organizing human activity (fundamental economic principles or practices, managing personal behavior or relationships or interactions between people) (MPEP 2106.04(a)(2)(II)); and/or
• mental processes (concepts practically performed in the human mind, including observations, evaluations, judgments, and opinions) (MPEP 2106.04(a)(2)(III)).
Analysis of instant claims
Mathematical concepts recited in instant claims 1-2, 5, 7-10, 12, 14-17, and 19-20 include the terms:
• "checking whether an exact match of the target nucleotide sequence is present" (claims 1, 5, 10, 12, 14, 17, and 19);
• "calculated/calculating" (claims 2, 7, 14, and 19);
• "checking whether the extracted seed matches the target nucleotide sequence" (claims 7-8, 14-15, and 19-20)
• "checking whether a seed of the found entry matches the target nucleotide sequence" (claims 8, 15, and 20)
• "finding a maximal exact match" (claims 9 and 16-17);
• "measuring a degree of matching" (claims 9 and 16-17);
Said terms are being identified as mathematical concepts. The claims in this application are given their broadest reasonable interpretation using the plain meaning of the claim language in light of the specification as it would be understood by one having ordinary skill in the art. In this instant disclosure, [0006, 0106, 0110-0112, and 0130] describes algorithmic operations involving mathematical methods; which indicates the use of math. Thus, the recited terms corresponds to verbal equivalents of mathematical concepts because they constitute actions executed by a group of mathematical steps in a form of a mathematical algorithm; thus mathematical concepts (MPEP 2106.04(a)(2)). A mathematical concept need not be expressed in mathematical symbols, because "words used in a claim operating on data to solve a problem can serve the same purpose as a formula." In re Grams, 888 F.2d 835, 837 and n.1, 12 USPQ2d 1824, 1826 and n.1 (Fed. Cir. 1989).
Dependent claims 5-6, 10-13, and 18 recite further details about "values/indexes" being calculated; dependent claims 7-9, 14-16, and 19-20 recite further details about "checking" for exact matches; not reciting any additional non-abstract elements; all reciting further aspects of the information being analyzed, the manner in which that analysis is performed. Hence, the claims explicitly recite numerous elements that, individually and in combination, constitute abstract ideas. The instant claims must therefore be examined further to determine whether they integrate that abstract idea into a practical application (MPEP 2106.04(d)).
[Step 2A Prong One: claims 1-20 – Yes].
Step 2A, Prong Two: If the claims recite a judicial exception under Prong One, then is the judicial exception integrated into a practical application by an additional element (MPEP 2106.04(d))?
Background
MPEP 2106.04(d).I lists the following example considerations for evaluating whether a judicial exception is integrated into a practical application:
An improvement in the functioning of a computer or an improvement to other technology or another technical field, as discussed in MPEP §§ 2106.04(d)(1) and 2106.05(a);
Applying or using a judicial exception to effect a particular treatment or prophylaxis for a disease or medical condition, as discussed in MPEP § 2106.04(d)(2);
Implementing a judicial exception with, or using a judicial exception in conjunction with, a particular machine or manufacture that is integral to the claim, as discussed in MPEP § 2106.05(b);
Effecting a transformation or reduction of a particular article to a different state or thing, as discussed in MPEP § 2106.05(c); and
Applying or using the judicial exception in some other meaningful way beyond generally linking the use of the judicial exception to a particular technological environment, such that the claim as a whole is more than a drafting effort designed to monopolize the exception, as discussed in MPEP § 2106.05(e).
Analysis of instant claims
Instant claims 1, 9-10, and 16-17 recite additional elements that are not abstract ideas:
• "loading an … index …" (claims 1, 10, and 17);
• "reading a target nucleotide sequence" (claims 1, 10, and 17);
• "generating a result" (claims 1, 9-10, and 16-17)
The recited limitations in these claims are interpreted to require the use of a computer. Hence, the claims explicitly recite steps executed by computers and therefore can be described as computer functions or instructions to implement on a generic computer.
Claims 1, 9-10, and 16-17 relate to computers or further aspects of the information being analyzed by computers, and do not describe any specific computational steps by which the computer performs or carries out the abstract idea, nor do they provide any details of how specific structures of the computer are used to implement these functions. Dependent claims 2-4 and 11 recite further details about the "loading" step.
The recited claims regarding "loading and reading" data read on data gathering activities or the type of data being gathered; not amounting to a practical application. The type of data doesn’t change that it is mere data gathering or conventional computer receiving means. These limitations are mere data gathering activity because these are used as input for the subsequent mathematical operations, reading on receiving or transmitting data over a network, e.g., using the Internet to gather data, Symantec, 838 F.3d at 1321. MPEP 2106.05(a) pertains
Claims directed to "generating a result" read on transmitting data over a network, e.g., using the Internet to gather data, Symantec, 838 F.3d at 1321 MPEP 2106.05(a); which constitutes just necessary data gathering and outputting and therefore correspond to insignificant extra-solution activity. The recited limitations in these claims are interpreted to require multiple computer parts (processor/ memory), not requiring specialized hardware other than a generic computer, which does not integrate the abstract idea into a practical application. Hence, the claims explicitly recite steps executed by computers and therefore can be described as computer functions.
Hence, these are mere instructions to apply the abstract idea using a computer and insignificant extra-solution activity and therefore the claims do not integrate that abstract idea into a practical application (see MPEP 2106.04(d) § I; 2106.05(f); and 2106.05(g)). None of the dependent claims recite any additional non-abstract elements; they are all directed to further aspects of the information being analyzed, the manner in which that analysis is performed, or the mathematical operations performed on the information.
In Step 2A, Prong One above, claim steps and/or elements were identified as part of one or more judicial exceptions (JEs).
In this Step 2A, Prong Two immediately above claim steps and/or elements were identified as part of one or more additional elements. Additional elements are further discussed in Step 2B below.
Here in Step 2A, Prong Two, no additional step or element clearly demonstrates integration of the JE(s) into a practical application.
At this point in examination it is not yet the case that any of the Step 2A, Prong Two considerations enumerated above clearly demonstrates integration of the identified JE(s) into a practical application. Referring to the considerations above, none of 1. an improvement, 2. treatment, 3. a particular machine or 4. a transformation is clear in the record.
For example, regarding the first consideration at MPEP 2106.04(d)(1), the record, including for example the specification, does not yet clearly disclose an explanation of improvement over the previous state of the technology field. The claims do not yet clearly result in such an improvement [0033]
[Step 2A Prong Two: claims 1-20 - No].
Step 2B: Do the claims recite a non-conventional arrangement of elements in addition to any identified judicial exception(s) (MPEP 2106.05)?
Claims found to be directed to a judicial exception are then further evaluated to determine if the claims recite an inventive concept that provides significantly more than the judicial exception itself. Step 2B of the 35 USC § 101 analysis determines whether the claims contain additional elements that amount to an inventive concept, and an inventive concept cannot be furnished by an abstract idea itself (MPEP 2106.05).
Claims 1, 9-10, and 16-17 recite a computer or computer functions, interpreted as instructions to apply the abstract idea using a computer, where the computer does not impose meaningful limitations on the judicial exceptions; which can be performed without the use of a computer (MPEP 2106.04(d) § I; and MPEP 2106.05(f)).
Claims directed to "loading and reading" data read on performing a standard computer task, which the courts have identified as a conventional computer function in Symantec, 838 F.3d at 1321, 120 USPQ2d at 1362; OIP Techs., Inc., v. Amazon.com, Inc., 788 F.3d 1359, 1363, 115 USPQ2d 1090, 1093 (Fed. Cir. 2015); and buySAFE, Inc. v. Google, Inc., 765 F.3d 1350, 1355, 112 USPQ2d 1093, 1096 (Fed. Cir. 2014). MPEP 2106.05(d) pertains.
Claims directed to "generating a result" read on electronically outputting data on a computer which is a conventional computer function (Alice Corp. Pty. Ltd. v. CLS Bank Int'l, 573 U.S. 208, 225, 110 USPQ2d 1984 (2014) MPEP 2106.05(d)).
It is known in the art that the use of loading/reading steps to process genomic alignment data and generate an alignment result is well-understood, routine and conventional (Aluru "A review of hardware acceleration for computational genomics." IEEE Design & Test 31(1):19-30 (2013)).
When the claims are considered as a whole, they do not integrate the abstract idea into a practical application; they do not confine the use of the abstract idea to a particular technology; they do not solve a problem rooted in or arising from the use of a particular technology; they do not improve a technology by allowing the technology to perform a function that it previously was not capable of performing; and they do not provide any limitations beyond generally linking the use of the abstract idea to a broad technological environment. See MPEP 2106.05(a) and 2106.05(h).
[Step 2B: claims 1-20 - No].
Conclusion: Instant claims are directed to non-statutory subject matter
For these reasons, the claims in this instant application, when the limitations are considered individually and as a whole, are directed to an abstract idea and lack an inventive concept. Hence, the claimed invention does not constitute significantly more than the abstract idea, so instant claims 1-20 are rejected under 35 USC § 101 as being directed to non-statutory subject matter.
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 1, 5-8 and 12-15 are rejected under 35 U.S.C. 102(a)(1) as being anticipated by Aluru ("A review of hardware acceleration for computational genomics" IEEE Design & Test 31(1):19-30 (2013)) as evidenced by Nelson ("Shepard: A fast exact match short read aligner." Tenth ACM/IEEE International Conference on Formal Methods and Models for Codesign (MEMCODE2012). IEEE, 2012), as cited on the attached Form PTO-892.
Independent claim 1 recites "an apparatus for accelerating genome sequence alignment, comprising: memory in which at least one program is recorded; and a processor for executing the program, wherein the program performs loading an essential index for a reference genome into memory; loading an additional index corresponding to an amount of available memory into memory; reading a target nucleotide sequence for which genome sequence alignment is to be performed; checking whether an exact match of the target nucleotide sequence is present in the reference genome based on the additional index; and generating a result of alignment of the target nucleotide sequence using a location of the exact match in the reference genome when the exact match is found" which Aluru teaches as hardware accelerators for applications in sequences alignment (pg. 19 col. 2 para. 1); wherein an exact string matcher (ESM) based on FM-index (i.e. essential index) is proposed for reads (i.e. nucleotide sequences) that align perfectly (pg. 25 col. 1 para. 2); wherein the FM-index combines suffix array with Burrows-Wheeler Transform (BWT) to find all exact occurrences (pg. 25 col. 1 para. 2); wherein a fast, exact matching solution uses a minimal perfect hash table (i.e. additional index) to perform lookups, wherein the hash table is created in software (i.e. inherent loading step, processor and memory) and minimizes the memory bandwidth overhead (i.e. corresponding to an amount of available memory), decreasing the constraint on the speed (pg. 25 col. 1 para. 1); wherein reads (i.e. nucleotide sequences) generated from a genome are mapped to a template or reference genome with specificity of where the reads map to the reference genome(i.e. generating a result of alignment of the target nucleotide sequence using a location of the exact match in the reference genome when the exact match is found) (pg. 24 Fig. 3); wherein some of the reads map to more than one location and some others do not map to any location (i.e. checking whether an exact match of the target nucleotide sequence is present in the reference genome based on the additional index) (pg. 24 Fig. 3). Independent claim 10 recites a method that performs the steps taught in claim 1.
Dependent claims 5 and 12 recite " wherein: the additional index includes a first index that is used when checking whether the exact match of the target nucleotide sequence is present in the reference genome is performed, and the first index includes a seed table configured with hash entries corresponding to respective seeds having a predetermined length, which are extracted from the reference genome, and a multi-location table in which two or more locations of an identical seed in the reference genome are collectively mapped to a single index" which Aluru teaches as hardware accelerators for applications in sequences alignment (pg. 19 col. 2 para. 1); wherein a fast, exact matching solution uses a minimal perfect hash table (i.e. additional index) to perform reads lookups (pg. 25 col. 1 para. 1); wherein the hash table lookup pipeline is broken stages as evidenced by Nelson (pg. 3 Fig. 3), wherein if the read (i.e. nucleotide sequence) matches to the reference genome, the index of occurrence in the genome and number of occurrences are recorded (i.e. includes a first index that is used when checking whether the exact match of the target nucleotide sequence is present in the reference genome); wherein the unique index is calculated and used to load the value from the hash table (i.e. hash entry) (pg. 3 Fig. 3 Nelson); wherein the value is either a new seed value or an offset from an intermediate table (i.e. seed table); wherein the index in the genome loaded from the hash table is used to load the corresponding 100 base pairs from the reference genome (i.e. includes a seed table configured with hash entries corresponding to respective seeds having a predetermined length, which are extracted from the reference genome) (pg. 3 Fig. 3 Nelson); wherein finding all the entries that need to be stored in the hash table is done by hashing each 100 base pair word in the reference genome in rounds, with duplicate entries being identified and discarded (pg. 2 col. 1 para. 4 Nelson) (i.e. reading on multilocation table with two or more locations of an identical seed in the reference genome are collectively mapped to a single index)
Dependent claims 6 and 13 recite "wherein the hash entry includes information about a location of a seed in the reference genome, information about whether the hash entry has a hash collision, an index number of a next hash entry having a same hash value as the hash entry, and information about an index in the multi-location table" which Aluru teaches as hardware accelerators for applications in sequences alignment (pg. 19 col. 2 para. 1); wherein a fast, exact matching solution uses a minimal perfect hash table (i.e. additional index) to perform reads lookups (pg. 25 col. 1 para. 1); wherein the minimal perfect hash table requires first looking up a seed or offset value in an intermediate table (i.e. seed table), then using this seed or offset to compute the actual index into the hash table as evidenced by Nelson (pg. 2 col. 1 para. 3); wherein an entry in the hash table contains the index in genome (i.e. information about a location of a seed in the reference genome) (pg. 2 Fig. 2 Nelson); wherein the method hash and displace sorts buckets containing a number of keys (short reads) that represent the number of collisions with other keys (pg. 2 col. 1 para. 5 Nelson); wherein finding all the entries that need to be stored in the hash table is done by hashing each 100 base pair word in the reference genome in rounds, with duplicate entries being identified and discarded (pg. 2 col. 1 para. 4 Nelson) (i.e. information about an index in the multi-location table).
Dependent claims 7 and 14 recite "wherein, when checking whether the exact match of the target nucleotide sequence is present in the reference genome based on the additional index, the program performs calculating a hash value of the target nucleotide sequence; searching for a hash entry corresponding to the hash value when the hash value is less than a number of loaded hash entries of the seed table; when the hash entry corresponding to the hash value is found and when the found entry is not an entry having a hash collision, extracting a seed from the reference genome using location information stored in the found entry; checking whether the extracted seed matches the target nucleotide sequence; and when the extracted seed is determined to match the target nucleotide sequence, searching the multi-location table for all exact matches of the target nucleotide sequence in the reference genome" which Aluru teaches as hardware accelerators for applications in sequences alignment (pg. 19 col. 2 para. 1); wherein a fast, exact matching solution uses a minimal perfect hash table (i.e. additional index) to perform reads lookups (pg. 25 col. 1 para. 1); wherein the minimal perfect hash table requires first looking up a seed or offset value in an intermediate table (i.e. seed table), then using this seed or offset to compute the actual index into the hash table (i.e. extracting a seed from the reference genome using location information stored in the found entry) as evidenced by Nelson (pg. 2 col. 1 para. 3); wherein the method hash and displace sorts buckets containing a number of keys (short reads) that represent the number of collisions with other keys (pg. 2 col. 1 para. 5 Nelson); wherein reseed values and offsets values are stored in an intermediate table (i.e. seed table) (pg. 2 col. 2 para. 1 Nelson)with the intermediate table providing a minimal perfect hash entry for the given key set, and can now be used to add values to the table to complete the key-value association (i.e. the step of completing a step reads on "when the hash value is less than a number of loaded hash entries of the seed table" – being interpreted as the need of completing the addition of values due to sufficient space remaining in said table)(pg. 2 col. 2 para. 2 Nelson) ; wherein a minimal perfect hash is one with no collisions (i.e. hash entry corresponding to the hash value is found and when the found entry is not an entry having a hash collision) and no empty slots, but requires a fixed set of keys (i.e. short reads) known in advance (pg. 2 col. 1 para. 2 Nelson); wherein in stage 5 of the hash table lookup pipeline, the reference genome is compared to the read to search for a match (pg. 3 Fig. 3 Nelson) (i.e. searching the multi-location table for all exact matches of the target nucleotide sequence in the reference genome).
Dependent claims 8 and 15 recite "wherein, when checking whether the extracted seed matches the target nucleotide sequence is performed, if it is determined that the extracted seed does not match the target nucleotide sequence, the program searches for an entry corresponding to a next value of the hash entry in the seed table and further performs checking whether a seed of the found entry matches the target nucleotide sequence" Aluru teaches as hardware accelerators for applications in sequences alignment (pg. 19 col. 2 para. 1); wherein a fast, exact matching solution uses a minimal perfect hash table (i.e. additional index) to perform reads lookups (pg. 25 col. 1 para. 1); minimal perfect hash function looks up at seed value in a seed intermediate table and uses it to compute an index into the hash table as evidenced by Nelson (pg. 2 col. 1 para. 3), that in turn is used to see if the short read is an actual match to the reference genome (pg. 2 col. 2 para. 3 Nelson); wherein a check for existence is needed and no unnecessary data is stored in the hash table (i.e. if it is determined that the extracted seed does not match the target nucleotide sequence, the program searches for an entry corresponding to a next value) (pg. 2 col. 2 para. 3 Nelson).
Claim Rejections - 35 USC § 103
(a) A patent may not be obtained though the invention is not identically disclosed or described as set forth in section 102, if the differences between the subject matter sought to be patented and the prior art are such that the subject matter as a whole would have been obvious at the time the invention was made to a person having ordinary skill in the art to which said subject matter pertains. Patentability shall not be negated by the manner in which the invention was made. The factual inquiries for establishing a background for determining obviousness under pre-AIA 35 U.S.C. 103(a) are summarized as follows:
1. Determining the scope and contents of the prior art.
2. Ascertaining the differences between the prior art and the claims at issue.
3. Resolving the level of ordinary skill in the pertinent art.
4. Considering objective evidence present in the application indicating obviousness or nonobviousness.
Claims 2-4 and 11 are rejected under 35 U.S.C. 103(a) as being unpatentable over Aluru as applied to claims 1 and 10 in the 102 rejection above and further in view of Wang ("Accelerating FM-index search for genomic data processing." Proceedings of the 47th International Conference on Parallel Processing (2018)), as cited on the attached Form PTO-892.
Dependent claim 2 recites "wherein, when loading the additional index into memory, the program uses available memory, an amount of which is calculated by subtracting a size of the essential index from a total amount of memory to be used for indexes for genome sequence alignment, in order to load the additional index."
Dependent claim 3 recites "wherein: when loading the additional index into memory, if the additional index comprises two or more additional indexes, the program sequentially loads the additional indexes, and an order in which the additional indexes are loaded is determined based on an effect of each of the additional indexes on genome sequence alignment performance" which Aluru teaches as hardware accelerators for applications in sequences alignment (pg. 19 col. 2 para. 1); wherein a fast, exact matching solution uses a minimal perfect hash table (i.e. additional index) to perform reads lookups (pg. 25 col. 1 para. 1); wherein the method hash and displace sorts buckets containing a number of keys (short reads) that represent the number of collisions with other keys, wherein buckets containing one key are loaded first buckets with one or more keys are reseeded and then loaded as evidenced by Nelson (pg. 2 col. 1 para. 5) (i.e. an order in which the additional indexes are loaded is determined based on an effect of each of the additional indexes on genome sequence alignment performance).
Dependent claims 4 and 11 recites "wherein: when loading the additional index into memory, the program loads all or part of the additional index depending on whether the amount of available memory is equal to or greater than a size of the additional index to be loaded, and when part of the additional index is loaded, the program preferentially loads an essential part of the additional index" which Aluru teaches as hardware accelerators for applications in sequences alignment (pg. 19 col. 2 para. 1); wherein a fast, exact matching solution uses a minimal perfect hash table (i.e. additional index) to perform reads lookups (pg. 25 col. 1 para. 1); wherein the block ram available was greater than the amount used by the described method as evidenced by Nelson (pg. 4 Table 2).
Ascertainment of the Difference Between Scope the Prior Art and the Claims
(MPEP §2141.02)
Regarding claim 2, Aluru does not teach the recited limitation above. However, Wang teaches it as an accelerator for FM-index (i.e. essential index) search in genomic sequence alignment (pg. 2 col. 1 para. 1) using data-level parallelism to improve memory bandwidth utilization (pg. 3 col. 2 para. 2); wherein to analyze the limitation of memory bandwidth, the model considers the total 64 bytes available (i.e. a total amount of memory to be used for indexes) and measures the utilization of the available memory bandwidth supplied by a single memory channel (i.e. reading on the step of an amount of memory to be used for indexes for genome sequence alignment) (pg. 9 col. 1 para. 2) with the use of memory operations (pg. 7 Table 2) to explore memory locality (pg. 6 col. 2 para. 2).
Finding of Prima Facie Obviousness Rationale and Motivation
(MPEP §2142-2143)
Regarding claims 2-4 and 11, one of ordinary skill in the art would be motivated to apply the teachings by Wang to the method by Aluru because Wang teaches to maximize memory throughput during the search in genomic sequence alignment (pg. 7 col. 1 para. 4 Wang). One of ordinary skill in the art would be able to motivated to combine the teachings in these references with a reasonable expectation of success since the described teachings pertain to methods for genomic sequence alignment.
Claims 9 and 16-20 are rejected under 35 U.S.C. 103(a) as being unpatentable over Aluru as applied to claims 1 and 10 in the 102 rejection above and further in view of Fujiki ("GenAx: A genome sequencing accelerator." 2018 ACM/IEEE 45th Annual International Symposium on Computer Architecture (ISCA). IEEE (2018)), as cited on the attached Form PTO-892.
Dependent claim 9 recites "wherein: when the exact match of the target nucleotide sequence is not found in the reference genome, the program performs finding a maximal exact match between the target nucleotide sequence and the reference genome based on the essential index; measuring a degree of matching between the target nucleotide sequence and the maximal exact match found in the reference genome; and generating a result indicating the degree of matching, and when finding the maximal exact match is performed, the program accelerates an initial step of finding the maximal exact match based on a second index of the additional index." Similarly claim 16 recites "when the exact match of the target nucleotide sequence is not found in the reference genome, finding a maximal exact match between the target nucleotide sequence and the reference genome based on the essential index; measuring a degree of matching between the target nucleotide sequence and the maximal exact match found in the reference genome; and generating a result indicating the degree of matching, wherein, when finding the maximal exact match is performed, an initial step of finding the maximal exact match is accelerated based on a second index of the additional index."
Aluru teaches hardware accelerators for applications in sequences alignment (pg. 19 col. 2 para. 1); wherein a fast, exact matching solution uses a minimal perfect hash table (i.e. additional index) to perform reads lookups (pg. 25 col. 1 para. 1) reading on the acceleration of "an initial step of finding the maximal exact match based on a second index of the additional index" in claims 9 and 16.
Dependent claim 3 recites "wherein: when loading the additional index into memory, if the additional index comprises two or more additional indexes, the program sequentially loads the additional indexes, and an order in which the additional indexes are loaded is determined based on an effect of each of the additional indexes on genome sequence alignment performance" which Aluru teaches as hardware accelerators for applications in sequences alignment (pg. 19 col. 2 para. 1); wherein a fast, exact matching solution uses a minimal perfect hash table (i.e. additional index) to perform reads lookups (pg. 25 col. 1 para. 1); wherein the method hash and displace sorts buckets containing a number of keys (short reads) that represent the number of collisions with other keys, wherein buckets containing one key are loaded first buckets with one or more keys are reseeded and then loaded as evidenced by Nelson (pg. 2 col. 1 para. 5) (i.e. an order in which the additional indexes are loaded is determined based on an effect of each of the additional indexes on genome sequence alignment performance).
Dependent claims 4 and 11 recites "wherein: when loading the additional index into memory, the program loads all or part of the additional index depending on whether the amount of available memory is equal to or greater than a size of the additional index to be loaded, and when part of the additional index is loaded, the program preferentially loads an essential part of the additional index" which Aluru teaches as hardware accelerators for applications in sequences alignment (pg. 19 col. 2 para. 1); wherein a fast, exact matching solution uses a minimal perfect hash table (i.e. additional index) to perform reads lookups (pg. 25 col. 1 para. 1); wherein the block ram available was greater than the amount used by the described method as evidenced by Nelson (pg. 4 Table 2).
Dependent claim 18 recites "wherein the hash entry includes information about a location of a seed in the reference genome, information about whether the hash entry has a hash collision, an index number of a next hash entry having a same hash value as the hash entry, and information about an index in the multi-location table" which Aluru teaches as hardware accelerators for applications in sequences alignment (pg. 19 col. 2 para. 1); wherein a fast, exact matching solution uses a minimal perfect hash table (i.e. additional index) to perform reads lookups (pg. 25 col. 1 para. 1); wherein the minimal perfect hash table requires first looking up a seed or offset value in an intermediate table (i.e. seed table), then using this seed or offset to compute the actual index into the hash table as evidenced by Nelson (pg. 2 col. 1 para. 3); wherein an entry in the hash table contains the index in genome (i.e. information about a location of a seed in the reference genome) (pg. 2 Fig. 2 Nelson); wherein the method hash and displace sorts buckets containing a number of keys (short reads) that represent the number of collisions with other keys (pg. 2 col. 1 para. 5 Nelson); wherein finding all the entries that need to be stored in the hash table is done by hashing each 100 base pair word in the reference genome in rounds, with duplicate entries being identified and discarded (pg. 2 col. 1 para. 4 Nelson) (i.e. information about an index in the multi-location table).
Dependent claim 19 recites "wherein, when checking whether the exact match of the target nucleotide sequence is present in the reference genome based on the additional index, the program performs calculating a hash value of the target nucleotide sequence; searching for a hash entry corresponding to the hash value when the hash value is less than a number of loaded hash entries of the seed table; when the hash entry corresponding to the hash value is found and when the found entry is not an entry having a hash collision, extracting a seed from the reference genome using location information stored in the found entry; checking whether the extracted seed matches the target nucleotide sequence; and when the extracted seed is determined to match the target nucleotide sequence, searching the multi-location table for all exact matches of the target nucleotide sequence in the reference genome" which Aluru teaches as hardware accelerators for applications in sequences alignment (pg. 19 col. 2 para. 1); wherein a fast, exact matching solution uses a minimal perfect hash table (i.e. additional index) to perform reads lookups (pg. 25 col. 1 para. 1); wherein the minimal perfect hash table requires first looking up a seed or offset value in an intermediate table (i.e. seed table), then using this seed or offset to compute the actual index into the hash table (i.e. extracting a seed from the reference genome using location information stored in the found entry) as evidenced by Nelson (pg. 2 col. 1 para. 3); wherein the method hash and displace sorts buckets containing a number of keys (short reads) that represent the number of collisions with other keys (pg. 2 col. 1 para. 5 Nelson); wherein reseed values and offsets values are stored in an intermediate table (i.e. seed table) (pg. 2 col. 2 para. 1 Nelson)with the intermediate table providing a minimal perfect hash entry for the given key set, and can now be used to add values to the table to complete the key-value association (i.e. the step of completing a step reads on "when the hash value is less than a number of loaded hash entries of the seed table" – being interpreted as the need of completing the addition of values due to sufficient space remaining in said table)(pg. 2 col. 2 para. 2 Nelson) ; wherein a minimal perfect hash is one with no collisions (i.e. hash entry corresponding to the hash value is found and when the found entry is not an entry having a hash collision) and no empty slots, but requires a fixed set of keys (i.e. short reads) known in advance (pg. 2 col. 1 para. 2 Nelson); wherein in stage 5 of the hash table lookup pipeline, the reference genome is compared to the read to search for a match (pg. 3 Fig. 3 Nelson) (i.e. searching the multi-location table for all exact matches of the target nucleotide sequence in the reference genome).
Dependent claim 20 recites "wherein, when checking whether the extracted seed matches the target nucleotide sequence is performed, if it is determined that the extracted seed does not match the target nucleotide sequence, the program searches for an entry corresponding to a next value of the hash entry in the seed table and further performs checking whether a seed of the found entry matches the target nucleotide sequence" Aluru teaches as hardware accelerators for applications in sequences alignment (pg. 19 col. 2 para. 1); wherein a fast, exact matching solution uses a minimal perfect hash table (i.e. additional index) to perform reads lookups (pg. 25 col. 1 para. 1); minimal perfect hash function looks up at seed value in a seed intermediate table and uses it to compute an index into the hash table as evidenced by Nelson (pg. 2 col. 1 para. 3), that in turn is used to see if the short read is an actual match to the reference genome (pg. 2 col. 2 para. 3 Nelson); wherein a check for existence is needed and no unnecessary data is stored in the hash table (i.e. if it is determined that the extracted seed does not match the target nucleotide sequence, the program searches for an entry corresponding to a next value) (pg. 2 col. 2 para. 3 Nelson).
Ascertainment of the Difference Between Scope the Prior Art and the Claims
(MPEP §2141.02)
Regarding claims 9 and 16, Aluru does not teach "when the exact match of the target nucleotide sequence is not found in the reference genome, the program performs finding a maximal exact match between the target nucleotide sequence and the reference genome based on the essential index; measuring a degree of matching between the target nucleotide sequence and the maximal exact match found in the reference genome; and generating a result indicating the degree of matching, and when finding the maximal exact match is performed."
Regarding claim 17, Aluru does not teach "finding a maximal exact match between the target nucleotide sequence and the reference genome based on the essential index when the exact match of the target nucleotide sequence is not found; measuring a degree of matching between the target nucleotide sequence and the maximal exact match found in the reference genome; and generating a result indicating the degree of matching, wherein when finding the maximal exact match is performed, an initial step of finding the maximal exact match is accelerated based on a second index of the additional index."
However, Fujiki teaches said recitations in claims 9 and 16-17 as an accelerator for read alignment consisting of a seeding and see-extension accelerator (pg. 69 col. 1 para. 2); wherein the seeding step finds a set of positions in the reference genome (hits) where a read could find a match (pg. 70 col. 2 para. 4); wherein the algorithm uses an index table that has one entry for each k-mer, which points to a list in a position table, wherein the list contains the hits where the k-mer occurs in the reference genome and, for each position (pivot) in the read, a right maximal exact match (RMEM) is found until the intersection returns an empty set of candidate hits (pg. 77 col. 2 para. 3); wherein the degree of hits per read are measured as seeding accelerator optimizations (pg. 80 Fig. 16).
Finding of Prima Facie Obviousness Rationale and Motivation
(MPEP §2142-2143)
Regarding claims 9 and 16-20, one of ordinary skill in the art would be motivated to apply the teachings by Fujiki to the method by Aluru because Fujiki teaches seeding accelerator overcoming irregular high-bandwidth memory accesses to the reference index by segmenting the genome to generate cache-able indexes and seeding acceleration using right maximal exact match within each genome segment (pg. 70 col. 2 para. 3 Fujiki). One of ordinary skill in the art would be able to motivated to combine the teachings in these references with a reasonable expectation of success since the described teachings pertain to methods for genomic sequence alignment.
Conclusion
No claims are allowed.
Any inquiry concerning this communication or earlier communications from the examiner should be directed to FRANCINI A FONSECA LOPEZ whose telephone number is (571)270-0899. The examiner can normally be reached Monday - Friday 8AM - 5PM 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.
/F.F.L./Examiner, Art Unit 1685
/G. STEVEN VANNI/Primary patents examiner, Art Unit 1686