Ex Parte PANTALEONI

Patent Trial and Appeal Board

Nov 19, 2018

13719796 (P.T.A.B. Nov. 19, 2018)

UNITED STA TES p A TENT AND TRADEMARK OFFICE
APPLICATION NO. FILING DATE
13/719,796 12/19/2012
102324 7590 11/21/2018
Artegis Law Group, LLP/NVIDIA
7710 Cherry Park Drive Suite T #104
Houston, TX 77095
FIRST NAMED INVENTOR
Jacopo PANTALEON!
UNITED STATES DEPARTMENT OF COMMERCE
United States Patent and Trademark Office
Address: COMMISSIONER FOR PATENTS
P.O. Box 1450
Alexandria, Virginia 22313-1450
www .uspto.gov
ATTORNEY DOCKET NO. CONFIRMATION NO.
NVDA/MI-12-0273-USl 3285
EXAMINER
HARWARD, SOREN T
ART UNIT PAPER NUMBER
1631
NOTIFICATION DATE DELIVERY MODE
11/21/2018 ELECTRONIC
Please find below and/or attached an Office communication concerning this application or proceeding.
The time period for reply, if any, is set in the attached communication.
Notice of the Office communication was sent electronically on above-indicated "Notification Date" to the
following e-mail address(es):
kcruz@artegislaw.com
ALGdocketing@artegislaw.com
j matthews @artegislaw.com
PTOL-90A (Rev. 04/07)
UNITED STATES PATENT AND TRADEMARK OFFICE
BEFORE THE PATENT TRIAL AND APPEAL BOARD
Exparte JACOPO PANTALEON!
Appeal2017-008118
Application 13/719, 796
Technology Center 1600
Before DEMETRA J. MILLS, JEFFREY N. FREDMAN and
JOHN G. NEW, Administrative Patent Judges.
MILLS, Administrative Patent Judge.
DECISION ON APPEAL
This is an appeal under 35 U.S.C. § 134. The Examiner has rejected as
directed to an abstract idea, and for obviousness. We have jurisdiction under
35 U.S.C. § 6(b).
We affirm.
1
Appeal2017-008118
Application 13/719,796
NATURE OF THE INVENTION
The present invention generally relates to bioinfonnatics and, more
specifically, to the streaming processing of short read alignment algorithms.
Spec. 1. In bioinformatics, aligning portions of DNA (referred to herein as
"short read") with a reference genome provides valuable information for
DNA analysis, such as identifying sequence variations and mutations. To
generate such information, hundreds of thousands of short reads are aligned
with a reference genome. Performing alignment operations in an efficient
manner requires fast and accurate alignment algorithms, such as the Burrows
Wheeler Aligner (BW A). Id.
Typically, an instance of an alignment algorithm for aligning a
particular short read with a reference genome is executed on a single
thread within a processing unit in a single thread, multiple data (SIMT)
environment, however, such an execution mode is not efficient because
the alignment algorithm does not execute uniformly across every
thread. More specifically, when each thread in multiple threads
executes an entire instance of the alignment algorithm, at given points
in time, each thread may be executing different portions of the
alignment algorithm as necessary. In a SIMT environment, having
different threads executing different stages of an algorithm is
extremely inefficient because the threads that are ahead must wait for
the remaining threads to reach the same execution point. Requiring
threads to wait for the remaining threads wastes processing cycles and
slows down the overall execution of the various instances of the
alignment algorithm.
Spec. 2. An advantage of claimed method
is that threads within a thread group executing a particular stage
of the alignment algorithm perform the same alignment operations on
data associated with different short reads. Having a distinct thread
group perform each stage of the alignment algorithm reduces the
2
Appeal2017-008118
Application 13/719,796
number of wasted processing cycles because all the threads within a
particular thread block perform the same operations and thus do not
have to wait for other operations to complete.
Spec. 6.
STATEMENT OF CASE
The following claim is representative.
1. A computer-implemented method for aligning a plurality of short
reads, each short read comprising a set of base pairs, with a reference
genome, the method comprising:
generating a plurality of root nodes, wherein each root node in the
plurality of root nodes is a root node of a search tree corresponding to each
short read in the plurality of short reads;
instantiating a plurality of thread groups within a processing unit for
performing an alignment algorithm based on the tree representation, wherein
the alignment algorithm includes a plurality of sequential stages, and each
thread group is responsible for executing a different stage included in the
plurality of sequential stages; and
transmitting the plurality of root nodes to the processing unit for
processmg.
Grounds of Rejection
Claims 1-20 are rejected under 35 U.S.C. §101 because the claimed
inventions are directed to non-statutory subject matter.
Claims 1-20 are rejected under pre-AIA 35 U.S.C. § 103(a) as being
unpatentable over Schatz, Mattson, and Meijer.
3
Appeal2017-008118
Application 13/719,796
FINDINGS OF FACT
The Examiner's findings of fact are set forth in the Answer at pages 3-
1 O; Final Action at pages 2-11.
PRINCIPLES OF LAW
In making our determination, we apply the preponderance of the
evidence standard. See, e.g., Ethicon, Inc. v. Quigg, 849 F .2d 1422, 1427
(Fed. Cir. 1988) (explaining the general evidentiary standard for proceedings
before the Office).
"The combination of familiar elements according to known methods
is likely to be obvious when it does no more than yield predictable results."
KSR Int'! Co. v. Teleflex Inc., 550 U.S. 398,416 (2007).
In KSR, the Supreme Court stated:
When there is a design need or market pressure to solve a
problem and there are a finite number of identified, predictable
solutions, a person of ordinary skill has good reason to pursue the
known options within his or her technical grasp. If this leads to the
anticipated success, it is likely the product not of innovation but of
ordinary skill and common sense. In that instance the fact that a
combination was obvious to try might show that it was obvious under
§ 103.
KSR International Co., v. Teleflex Inc., 550 U.S. 398,421 (2007).
§101 Rejection, unpatentable subject matter
The Examiner finds that
The claims as a whole, considering all claim elements both
individually and in combination, do not amount to significantly more
than the abstract idea of an algorithm that aligns a set of short
4
Appeal2017-008118
Application 13/719,796
nucleotide reads to a reference sequence; a series of data processing
steps or algorithm is a court-established abstract idea, and further is
similar to other court-established abstract ideas such as mathematical
operations and procedures for organizing information.
Final Act. 2.
Appellant contends that when the pending§ 101 rejection is evaluated
under the two-step framework set forth in Alice Corp. Pty. Ltd. v. CLS Bank
lnt'l, 134 S.Ct. 2347, 2355 (2014), it is found that the claimed method
"improves computer capabilities, as opposed to simply invoking a computer
as a tool. In particular, the claimed approach enables a parallel processing
environment - including a plurality of thread groups - to more efficiently
execute an alignment algorithm to align a plurality of short reads with a
reference genome. See Application at ,r [0004]." Reply Br. 9. Appellant
argues that, "The claimed approach improves the functionality of the parallel
processing system by dividing the alignment algorithm into a plurality of
sequential stages." Reply Br. 10. Appellant argues that "under the
Guidance and DDR Holdings,PJ the claimed approach provides a technical
solution to a technical problem arising in computing systems." Reply Br.
11. Appellant argues that the claims do not preempt an abstract idea and
that, "with respect to the second prong of the two-step Alice test, the claims
include additional elements that amount to "significantly more" than an
abstract idea itself," and the claims include one unconventional step. Reply
Br. 13.
1 DDR Holdings, LLC v. Hotels.com, L.P., 773 F.3d 1245, 1257 (Fed. Cir.
2014).
5
Appeal2017-008118
Application 13/719,796
ANALYSIS
We agree with the Examiner's fact finding, statement of the rejection
and responses to Appellant's arguments as set forth in the Answer. We find
that the Examiner has provided argument/ evidence to support a prima facie
case of unpatentable subject matter because the claims are directed to an
abstract idea. We provide the following additional comment to the
Examiner's argument set forth in the Final Rejection and Answer.
The Examiner argues that additional non-abstract claim elements do
not provide meaningful limitations to transform the abstract idea into a
patent eligible application of the abstract idea such that the claims amount to
significantly more than the abstract idea itself. Ans. 6. In particular, the
Examiner argues that the claims do not recite additional elements other than
the abstract idea per se and the claims
amount to no more than mere instructions to implement the
abstract idea as "a plurality of thread groups within a processing unit"
( as in claim 1 and its dependents), and other generic computer
structures such as "a computer-readable medium" and "a memory"
and "an instantiation engine" (as in claims 10, 19 and their
dependents). As demonstrated by numerous references of record (e.g.
Klus 2012, Ligowski 2009, Liu 2011, Lu 2012, Mahmood 2011,
Schatz2007, Shi 2009 and Trapnell 2009), implementing algorithms -
including nucleotide sequence alignment or assembly algorithms - as
multithreaded GPGPU-accelerated computer programs was a well-
understood, routine and conventional activity in the art prior to the
time of invention.
Final Act. 3. Furthermore, the Examiner finds that
"the claimed solution is directed to solving the problem in the
conventional art [ of alignment algorithms] ... to provide a more
efficient way to execute an alignment algorithm via multiple thread
6
Appeal2017-008118
Application 13/719,796
groups" (Reply, p. 11 ). Sequence alignment is not "a problem rooted
in computer technology"; problems of sequence alignment do not
arise from the use of computers, nor are computers necessary to
perform sequence alignment.
Final Act. 4. The Examiner argues that, "the claims are not actually limited
to executing the alignment algorithm using "a specific type of computer
hardware" (Reply, p. 9) or "in a SIMT [ single instruction multiple thread]
environment" (Reply, pp. 8-10)." Final Act. 4. The Examiner finds that
The disclosure describes an exemplary "parallel processing unit"
(0023; 202@ Fig. 2), but the description is so generic that it
encompasses any multi-core processor, which were essentially
ubiquitous at the time of invention, and this description does not limit
the claims. The examiner has applied art wherein a GPGPU
constitutes the claimed "processing unit", but a generic claim
limitation cannot be interpreted as being limited only a particular
species disclosed in the art applied in a § 103 rejection. So all of
Applicant's discussion of SIMT environments or any other particular
hardware is irrelevant to the claims because the claims are not limited
to being implemented by any device more specific than "a
processing unit". The fact that the claims are not limited to any
particular computer hardware or processing environment is further
evidence that the claims are not an improvement to computer
technology.
Final Act. 5.
In Alice, the Supreme Court referred to the two-step analysis set forth
in Mayo Collaborative Servs. v. Prometheus Labs., Inc., 132 S.Ct. 1289
(2012), as providing "a framework for distinguishing patents that claim laws
of nature, natural phenomena, and abstract ideas from those that claim
patent-eligible applications of those concepts." Alice, 134 S.Ct. at 2355
(citing Mayo, 132 S.Ct. at 1289). Under Mayo, "[w]e must first determine
7
Appeal2017-008118
Application 13/719,796
whether the claims at issue are directed to a patent-ineligible concept." Id.
Next, "we consider the elements of each claim both individually and 'as an
ordered combination' to determine whether the additional elements
'transform the nature of the claim' into a patent-eligible application." Id.
(citing Mayo, 132 S.Ct. at 1297-98).
Under Mayo, to be patentable, a claim must do more than simply state
the law of nature or abstract idea and add the words "'apply it."' Mayo, 132
S.Ct. at 1294; Benson, 409 U.S. at 67. For example, "the mere recitation of
a generic computer cannot transform a patent-ineligible abstract idea into a
patent-eligible invention." Alice, 134 S.Ct. at 2358. "Thus, if a patent's
recitation of a computer amounts to a mere instruction to 'implemen[t ]' an
abstract idea 'on ... a computer,' that addition cannot impart patent
eligibility." Id. (internal citation omitted).
In addition, the "notion that [ extra ]-solution activity, no matter how
conventional or obvious in itself, can transform an unpatentable principle
into a patentable process exalts form over substance." Parker v. Flook, 437
U.S. 584, 590 (1978). See also Mayo, 132 S.Ct. at 1298 ("Purely
'conventional or obvious' '[pre]-solution activity' is normally not sufficient
to transform an unpatentable law of nature into a patent-eligible application
of such a law.").
A challenged patent claim, properly construed, must incorporate
enough meaningful limitations to ensure that it claims more than just an
abstract idea and not just a mere "drafting effort designed to monopolize the
[abstract idea]." Alice, 134 S.Ct. at 2357 (quoting Mayo, 132 S.Ct. at 1297).
"Simply appending conventional steps, specified at a high level of
8
Appeal2017-008118
Application 13/719,796
generality," is not "enough" for patent eligibility. Id. (quoting Mayo, 132 S.
Ct. at 1300).
In the present case, under the Mayo analysis, our first question is
whether claim 1 is directed to a judicial exception, an abstract idea. Similar
to the claim in Alice, present claim 1 is directed to a computer-implemented
method, in particular, a method for aligning a plurality of short reads, each
short read comprising a set of base pairs, with a reference genome.
Essentially, claim 1 is directed to an abstract idea, an alignment algorithm,
which is executed in sequential stages.
With respect to the first prong of the two-step test, the Federal Circuit
has emphasized that the first prong "asks whether the focus of the claims is
on the specific asserted improvement in computer capabilities ... or, instead,
on a process that qualifies as an 'abstract idea' for which computers are
invoked merely as a tool." See Enfzsh, LLC v. Microsoft Corp., No. 2015-
1244, slip op. at 11 (Fed. Cir. May 12, 2016). We, therefore find that under
Alice, step 1, the claims are directed to an abstract idea, an alignment
algorithm, for which computers are invoked as a tool. We further find that
the claims do not recite an inventive concept sufficient to transform any
abstract idea into patent-eligible subject matter.
Next, "we consider the elements of each claim both individually and
'as an ordered combination' to determine whether the additional elements
'transform the nature of the claim' into a patent-eligible application." Id.
(citing Mayo, 132 S. Ct. at 1297-98).
We agree with the Examiner that
The claimed invention is not an improvement to a computer
technology, nor to the computer itself: "the present invention
9
Appeal2017-008118
Application 13/719,796
generally relates to bioinfonnatics and, more specifically, to the
streaming processing of short read alignment algorithms"
(Specification ,r 0001) and "the present invention sets forth a method
for aligning a plurality of sets of base pairs to a reference genome
(Specification ,r 0005)."
Ans. 6. We further agree with the Examiner that the claims "are not directed
to a parallel processing environment" (Brief, p. 15) or "a specific type of
computer hardware" (Brief, p. 17). The claims recite only a generic
"processing unit", which does not imply any particular type of computer
hardware, much less "a parallel processing environment"." Ans. 7. None of
the claims actually require execution of the alignment algorithm in a parallel
processing environment (or any other environment for that matter). Ans. 8.
Thus, the claims amount to mere use of a generic, general-purpose computer
to prepare data, and an algorithm for execution on another generic
processing unit (cf Specification ,r,r 0067-0068). Ans. 8-9.
Appellant argues that the pending claims recite at least one
unconventional step. App. Br. 19. The Examiner, in tum, argues that,
"Schatz and numerous other references of record demonstrate that[,] prior to
the time of invention, multithreaded computer programs, and GPGPU
acceleration of such programs (i.e. the non-abstract elements on the claims)
were well-understood, routine and conventional practices for implementing
algorithms, including sequence alignment and assembly algorithms." Ans.
9. We do not find that Appellant has provided sufficient evidence to counter
the Examiner's evidence that the claimed methods were well-understood,
routine and conventional practices for implementing algorithms as described
10
Appeal2017-008118
Application 13/719,796
in Mattson. The additional elements 'transform the nature of the claim' into
a patent-eligible application.
In sum, "[ s ]imply appending conventional steps, specified at a high
level of generality," to a method already "well known in the art" (parallel
processing of an algorithm) is not "enough" to supply the" 'inventive
concept' " needed to make this transformation." Alice, 13 4 S. Ct. at 2 3 5 0
(quoting Mayo, 132 S.Ct. at 1297). "The introduction of a computer into
the claims does not alter the analysis." Alice, 134 S.Ct. at 2357 ( quoting
Mayo, 132 S.Ct. at 1294).
For the reasons of record, we affirm the Examiner's lack of patentable
subject matter rejection.
Obviousness Rejection
For the reasons outlined in the Final Action at pages 6-9, we find that
the Examiner has set forth a prima facie case of obviousness. The Examiner
found that Schatz teaches each element claimed, but "differs from the
claimed invention in that only one stage of the algorithm is executed as a
thread group on the GPU, whereas in the claimed invention, multiple
different stages of the algorithm are implemented as thread groups on the
processing unit." Final Act. 6. The Examiner relies on Mattson to make up
for the deficiency of Schatz. Final Act. 7.
Mattson teaches design patterns for parallelizing computational
problems. These patterns include data parallelism (p. 36 § 3.3.1.2),
for which "GPU hardware is specifically designed to support
problems that use the data parallelism pattern" (p. 37); and pipelines,
in which sequential independent steps are performed by a thread or a
group of threads (p. 39 § 3.3.1.4). A common parallel implementation
11
Appeal2017-008118
Application 13/719,796
pattern is the task-queue pattern (p. 49 § 3.3.2.5), in which a pool of
threads pull independent tasks from a shared queue. Since Schatz
teaches that the overall algorithm constitutes several different stages
(p. 4 § "Implementation"), the combined teachings of Schatz and
Mattson suggest implementing the multiple stages on the GPU as a
pipeline, in which each stage of the pipeline is implemented as a
separate group of threads that execute a task pulled from a share
queue.
Final Act. 7.
We are not persuaded by Appellant's arguments. Appellant argues
that, "Schatz fails to disclose instantiating a plurality of thread groups
within the GPU, where each thread group is responsible for executing a
different stage of an alignment algorithm." Reply Br. 3; App. Br. 12.
However, Appellant errs in attacking the references individually, as the
rejection is based on a combination of references, both Schatz and Mattson.
See In re Merck & Co., Inc., 800 F.2d 1091, 1097 (Fed. Cir. 1986). The
references cannot be read in isolation, but for what they teach in
combination with the prior art as a whole. See id.
The Examiner relied on Mattson, not Schatz, for the disclosure that it
was well known in the art to employ parallel algorithm strategy patterns to
solve any problem with segments that can execute concurrently. Mattson, p.
34, § 3 .31. In particular, Mattson discloses that
Parallel programming is the application of concurrency to ( 1) solve a
problem in less time or (2) solve a bigger problem in a fixed amount
of time. Concurrency is present in a system when multiple tasks can
be active and potentially make progress at the same time. The
processes of creating a parallel algorithm can therefore be
summarized in two steps:
12
Appeal2017-008118
Application 13/719,796
1. Find tasks that can execute concurrently.
2. Manage data conflicts between tasks so the same results are
produced (within round-off error) for every semantically allowed way
the execution of the tasks can be interleaved.
To solve any problem in parallel, you must decompose the problem
into concurrent tasks AND decompose the data to manage data access
conflicts between tasks.
The goal of the algorithm strategy patterns is to define this dual
task/data decomposition. They start with a conceptual understanding
of a problem and how it can be executed in parallel. They finish with
a decomposition of the problem into concurrent tasks and data.
Mattson, p. 34, § 3.3.1, § 3.3.1.4; Ans. 4.
We agree with the Examiner that,
Since Schatz teaches that the overall algorithm constitutes several
different stages (p. 4 § "Implementation"), the combined teachings of
Schatz and Mattson suggest implementing the multiple stages on the
GPU as a pipeline, in which each stage of the pipeline is implemented
as a separate group of threads that execute a task pulled from a share
queue.
Final Act. 7.
In KSR, the Supreme Court stated:
When there is a design need or market pressure to solve a problem
and there are a finite number of identified, predictable solutions, a
person of ordinary skill has good reason to pursue the known options
within his or her technical grasp. If this leads to the anticipated
success, it is likely the product not of innovation but of ordinary skill
and common sense.
KSR International Co., v. Teleflex Inc., 550 U.S. 398,421 (2007). In the
present case, Appellant combines the predictable solution of parallel
13
Appeal2017-008118
Application 13/719,796
processing of algorithm steps (as described in Mattson, Schatz) with a
method for aligning a plurality of short reads, each short read comprising a
set of base pairs, with a reference genome (as described in Schatz). This led
to the anticipated success of faster processing of sequence alignment and is
the obvious result of the ordinary skill in the art.
The obviousness rejection is affirmed for the reasons of record.
CONCLUSION OF LAW
The cited references support the Examiner's obviousness rejection,
which is affirmed for the reasons of record. The lack of patentable subject
matter rejection is also affirmed. All pending, rejected claims fall.
No time period for taking any subsequent action in connection with
this appeal may be extended under 37 C.F.R. § 1.136(a)(l )(iv).
AFFIRMED
14