Ex Parte Srinivasa

Board of Patent Appeals and Interferences

Aug 31, 2012

11214603 (B.P.A.I. Aug. 31, 2012)

UNITED STATES PATENT AND TRADEMARK OFFICE
__________

BEFORE THE BOARD OF PATENT APPEALS
AND INTERFERENCES
__________

Ex parte DEEPAK M. SRINIVASA
__________

Appeal 2011-010582
Application 11/214,603
Technology Center 1600
__________

Before DONALD E. ADAMS, JEFFREY N. FREDMAN, and
STEPHEN WALSH, Administrative Patent Judges.

WALSH, Administrative Patent Judge.

DECISION ON APPEAL
This is an appeal under 35 U.S.C. § 134(a) from the rejection of
claims directed to a computer program product. The Patent Examiner
rejected the claims for obviousness. We have jurisdiction under 35 U.S.C.
§ 6(b). We reverse.
Appeal 2011-010582
Application 11/214,603

2
STATEMENT OF THE CASE
The “invention relates to global alignment of molecular sequences,
and relates more particularly to a solution to a (wh)-density problem, defined
herein, for the alignment of data representing such sequences.” (Spec. 1, ll.
5-7.) The Specification states that “[a] constrained version of the pairwise
global alignment problem, termed the (wh)-density global alignment
problem, is defined herein and a computational solution is also described.”
(Id. at 2, ll. 22-23.) Claims 31 and 32 are on appeal.
The Examiner rejected the claims as follows:
 claim 31 under 35 U.S.C. § 103(a) as unpatentable over Brudno1 and
Cheng;2 and
 claim 32 under 35 U.S.C. § 103(a) as unpatentable over Brudno,
Cheng, and Brudno LAGAN.3

I.
Claim 31 reads (bracketed letters added by Board for reference):
31. A computer program product for execution by a computer system
comprising computer hardware, the computer program product comprising a
storage medium readable by the computer system and storing software
instructions executable by the computer system for performing the following
steps:
[a] receiving a first data string representing a first molecular sequence,
with the first data string being a first sequence of characters;

1 Michael Brudno et al., Fast and sensitive multiple alignment of large
genomic sequences, 4 BMC BIOINFORMATICS 66 (2003).
2 Jill Cheng et al., US 2004/0126840 A1, published July 1, 2004.
3 Michael Brudno et al., LAGAN and Multi-LAGAN: Efficient Tools for
Large-Scale Multiple Alignment of Genomic DNA, 13 GENOME RES. 721-
731 (2003).
Appeal 2011-010582
Application 11/214,603

3
[b] receiving a second data string representing a second molecular
sequence, with the second data string being a second sequence of characters;
[c] determining a plurality of global alignments between the first data
string and the second data string, with each global alignment representing a
sequential correspondence between all of the respective characters of the
first and second data strings, and where at least some of the plurality of
global alignments include at least one non-character inserted into at least one
of the first and second data strings;
[d] providing a constraint value w to have an integer value greater than 1;
[e] providing a constraint value h to have an integer value greater than 0
and less than w; and
[f] determining the (wh)-density global alignment(s) from among the
plurality of global alignments, with a (wh) density global alignment being
defined as any alignment where for any w consecutive positions in the
alignment there are at least h matches between the characters of the first and
second data strings.

The Issue
The Examiner’s position is that Brudno described an algorithm
including the steps set out in claim 31, and that the difference between
Brudno’s description and Appellant’s product is that Brudno did not teach a
storage medium. The Examiner found that Cheng described a computer
system making use of analogous information and the Examiner concluded
that it would have been obvious
to modify the genomic sequence alignment method of Brudno et al.
with the system of providing genomic ontological data by Cheng et al.
because Cheng et al. utilizes sequence alignment algorithms,
(paragraph 136), combinable because Brudno et al. provides CHAOS-
DIALIGN software, (page 10, third paragraph), and one skilled in the
art would recognize that each of the elements are known in the art, the
art is in the same technology, i.e. sequence alignment, and one of
ordinary skill would have recognized that the results of the
combination were predictable.

(Ans. 6.)
Appeal 2011-010582
Application 11/214,603

4
Appellant presents two issues:
(1) “[t]he Applied Art, whether considered individually, or in any
combination, does not disclose . . . determination of (wh)-density;” and
(2) “the method of the BMC Article does not do global alignment by
comparing consecutive-length subsets along the entire length of its strings.”
(App. Br. 13.) According to Appellant these issues also relate to claim 32.
(Id. at 16.)

Findings of Fact
1. The Specification states: “A global alignment A between two strings
S1 and S2 satisfies the (wh)-density constraint if any consecutive “w”
alignment positions of A has at least “h” matches. Such an alignment
is referred to as a (wh)-density global alignment.” (Spec. 4, ll. 9-12.)
2. The Specification provides two example alignments A1 and A2 in
Table 2:

(Id. at 5, ll. 1-9.)
3. The Specification assesses the alignments in Table 2 for the settings
w = 2 and h = 1:
In the example of Table 2, Alignment A1 does not satisfy the density
constraint because “s” and “a” are two consecutive positions of S1,
Appeal 2011-010582
Application 11/214,603

5
and there is no match with the corresponding position of S2 for either
of these positions of S1. A2 does satisfy the density constraint.
Therefore, A2 is a (wh)-density global alignment for w = 2 and h = 1,
while A1 is not.

(Id. at ll. 23-26.)
4. The Specification describes “optimal” global alignment:
The (wh)-density optimal global alignment A, given two strings S1 and
S2, is the alignment of the strings that not only satisfies the (wh)-
density global alignment constraint, as explained in the above
example, but that also maximizes an alignment score of the strings.
The alignment score (also referred to herein as "alignment value") is
merely a count of the number of matching positions of the strings.
Note that in the above example, alignments A1 and A2 have the same
alignment score, even though only A2 satisfies the (wh)-density global
alignment constraint.

(Id. at ll. 28-34.)
5. Brudno disclosed a “Fast and sensitive multiple alignment of large
genomic sequences.” (Brudno, Title.)
6. According to Brudno:
One way of combining speed and sensitivity is to use an anchored-
alignment approach. In a first step, a fast search program identifies a
chain of strong local sequence similarities. In a second step, regions
between these anchor points are aligned using a slower but more
accurate method.
Results: Herein, we present CHAOS, a novel algorithm for rapid
identification of chains of local pair-wise sequence similarities. Local
alignments calculated by CHAOS are used as anchor points to
improve the running time of DIALIGN, a slow but sensitive multiple-
alignment tool. . . .
Conclusion: We conclude that the novel CHAOS local alignment tool
is an effective way to significantly speed up global alignment tools
such as DIALIGN without reducing the alignment quality.

(Id., Abstract.)
Appeal 2011-010582
Application 11/214,603

6
7. Brudno disclosed:
The CHAOS algorithm works by chaining together pairs of similar
regions, one from each of the two input DNA sequences; we call such
pairs of regions seeds. More precisely, a seed is a pair of words of
length k with at least n identical base pairs (bp). A seed s(1) can be
chained to another seed s(2)…. The final score of a chain is the total
number of matching bp in it. … The detailed algorithms used for
finding seeds and computing the maximal chains are specified in
Methods.
After computing maximal chains, CHAOS scores each chain….
CHAOS can be used as a stand-alone program for local sequence
alignment or as a pre-processing step to find anchor points for global
alignment procedures.

(Id. at 2.)
8. The Examiner found that Brudno described an algorithm that aligns
molecular sequences by identifying seeds or substrings comprising
pairs of words of length “k” (number of consecutive positions), and
that “k” corresponds to Appellant’s constraint value “w”. (Ans. 4.)
9. The Examiner found that Brudno described identical base pairs “n,”
and that “n” corresponds to Appellant’s constraint value “h”. (Id. at
4-5.)
10. The Examiner found that Brudno determined the density of anchor
points, and this corresponded to Appellant’s determination of (wh)
density global alignment:
Once chains of local sequence similarities are found, a highest scoring
chain of local alignments is determined (anchor points), (page 10, left
column). Brudno teaches that a seed (anchor) is a pair of words of
length k, (w) with at least n (h) identical base pairs, (page 10, right
column, second paragraph). Candidate anchor points are scored and
each anchor accepted as final anchor points provided they are
consistent with the previous candidate, (page 4, left column, second
paragraph). Brudno et al. determines the density of anchor points on
Appeal 2011-010582
Application 11/214,603

7
average to be 2.1 anchor points per kilobases, (page 4, left column,
last paragraph). This chain of anchor points is directly used to anchor
the DIALIGN section's pair-wise plurality of global alignments of
SCL sequences in human, mouse, chicken, pufferfish and zebrafish,
(page 4, left column, first and second paragraph; page 8, left column,
last paragraph - right column, second paragraph; Figure 2), therefore
the use of anchor points in global alignment of sequences teaches w
consecutive positions in the alignment and at least h matches between
the first and second sequences, (page 10, right column, second
paragraph). Brudno et al. teaches non-character inserts in the
sequences, (Figure 2). Brudno et al. teaches CHAOS-DIALIGN
software, (page 10, third paragraph).

(Id. at 5.)
11. The Examiner found that Brudno did not teach a storage medium.
(Id.)
12. The Examiner found that Cheng described a computer system making
use of information correlating probe-set identifiers with a plurality of
ontological categories, and including a computer readable medium
and other components associated with a computer. (Id. at 5-6.)

Analysis
First, we acknowledge Appellant’s agreement that Brudno disclosed a
method for determining global alignments (App. Br. 13), and Appellant’s
statement that “[f]or purposes of this appeal, the Final rejection will be
considered to be correct . . . that w, in parlance of the present application, is
analogous to k in the BMC article and further that h, in the parlance of the
present application, is analogous to n in the BMC Article” (id. at 15). Thus,
there appears to be no dispute that Brudno taught a global alignment method
that included steps [a], [b], [d], and [e]. We acknowledge Appellant’s
Appeal 2011-010582
Application 11/214,603

8
statement that “[n]one of the Final Rejection's characterizations of Cheng are
disputed in this appeal.” (Id. at 13.)
As to Appellant’s first issue, we think the Examiner was correct to
find that Brudno’s combined use of k and n was equivalent to (wh)-density
determination. (See FF 10.) We therefore disagree with Appellant’s
contention that Applied Art, whether considered individually, or in any
combination, does not disclose determination of (wh)-density. We turn to
Appellant’s second issue, whether Brudno did global alignment by
comparing consecutive-length subsets along the entire length of its strings.
The claimed computer program product stores instructions for two
determining steps: [c] “determining a plurality of global alignments
between the first data string and the second data string . . . each global
alignment representing a sequential correspondence between all of the
respective characters of the first and second data strings,” and
[f] “determining the (wh)-density global alignment(s) from among the
plurality of global alignments . . . .” Implicitly, step [c] must be done before
step [f] in order that the global alignments determined in step [c] be
available for the determining step in [f]. Because step [f] operates on the
global alignments determined in step [c], the two steps are distinct
operations. Although we have agreed with the Examiner that Brudno
produced a (wh)-density global alignment, if Brudno’s method did not
perform [c] and [f], the rejection must be reversed.
Appellant’s Specification provided an example of the step [c]
determination in its Table 2. (FF 2.) Table 2 shows two different global
alignments between first and second data strings as sequential
correspondences between all the string characters, with non-characters
Appeal 2011-010582
Application 11/214,603

9
inserted. (FF 2.) Operating on that plurality of two global alignments, the
Specification determines (wh)-density. (FF 3.)
Appellant notes that Brudno also taught producing a global alignment
in two stages using CHAOS and DIALIGN algorithms respectively, but
disagrees that Brudno’s stages are the same as steps [c] and [f] “because the
cited portions of the BMC Article deal with localized alignment of strings
and not global alignment of strings.” (Id. at 14.) Appellant explains:
the disclosure of the BMC Article still falls short because claim 31
recites “determining the (wh)-density global alignment(s) from
among the plurality of global alignments, with a (wh) density global
alignment being defined as any alignment where for any w
consecutive positions in the alignment there are at least h matches
between the characters of the first and second data strings” (emphasis
added to highlight what the BMC Article fails to disclose).

(Id. at 15.) To resolve this issue, we first ask: did Brudno’s CHAOS
algorithm produce global alignments with each global alignment
representing a sequential correspondence between all the respective
characters of the first and second data strings? If the answer to this question
is no, the rejection may be reversed because step [c] was not suggested. If
the answer to this question is yes, the next step is to ask whether Brudno’s
DIALIGN algorithm then operated on global alignments produced by
CHAOS to perform the determination recited in [f].
The Examiner found that “CHAOS aligns molecular sequences by
identifying seeds or substrings.” (Ans. 4.) Appellant contends that CHAOS
determines the number of matching pairs within small isolated portions of
the long strings being compared, but “the CHAOS stage does not apply this
technique to the entire length of the chain.” (App. Br. 13.) The Examiner
found Appellant’s argument unpersuasive because “the entirety of the
Appeal 2011-010582
Application 11/214,603

10
CHAOS-DIALIGN algorithm is what is taught and relied upon in the instant
rejection.” (Ans. 9.)
CHAOS does apply its technique to the entire length of two input
sequences, but its output is described as chains comprising seeds (pairs of
similar regions). (FF 7.) Brudno does not describe the chains that CHAOS
outputs as a sequential correspondence between all the respective characters
of the first and second data strings, nor is it clear that the outputted chains
inherently include all the respective characters. From Brudno’s description
of computing “maximal chains” (FF 7), it appears that the CHAOS output
comprises chains that are less than all the respective characters of the input
sequences. Brudno therefore apparently fails to suggest step [c]. In any
case, the Examiner has failed to provide evidence showing that the CHAOS
output incorporates all of the characters of the first and second data strings.
The rejection must be reversed because the computer product suggested by
Brudno and Cheng does not include instructions for performing step [c].

CONCLUSION
The prior art of record did not suggest a computer product including
instructions for determining a plurality of global alignments between a first
data string and a second data string, with each global alignment representing
a sequential correspondence between all of the respective characters of the
first and second data strings, and then determining the (wh)-density global
alignment(s) from among the plurality of global alignments.
Because claims 31 and 32 each define a product including instructions
for this step, the rejections of both claims are reversed.

Appeal 2011-010582
Application 11/214,603

11
SUMMARY
We reverse the rejection of claim 31 under 35 U.S.C. § 103(a) as
unpatentable over Brudno and Cheng.
We reverse the rejection of claim 32 under 35 U.S.C. § 103(a) as
unpatentable over Brudno, Cheng, and Brudno LAGAN.

REVERSED

lp