Composite Pattern Discovery
for PCR Application
Stanislav Angelov

University of Pennsylvania, USA

Shunsuke Inenaga

Kyushu University, Japan
Japan Society for the Promotion of SciencePattern Discovery
Input
text data

Outputpatternknowledge

ACGTTGACGTTGGATCGATG
ACCGATGACAGATAAATGGG
CAGTGTCACAGTTATGCCCC
ACTGTGCCTT
TTGGCAAAGT

ruleFinding Missing Patterns
Input : text T and threshold Output : Pattern pair (A,B) satisfying:
1. The distance between any occurrencesof A and B in T is at least ,
2. |A| = |B|, and
3. |A| (=|B|) is shortest possible.

Finding Missing Patterns [cont.]
Case 1: -close
TIf A and B are non -close,B
A be a missingA pair.
B(A,B)
is said toCase 2: non -close


TB


AA


B


Case 3: non -close
TAA

Application - PCR
PCR (Polymerase Chain Reaction)
 Standard technique to produce many copies

of a region of DNA (can be a tiny sample).

 In Medicine, to detect infections.
 In Forensic Science, to identify individuals.

Application – PCR [cont.]
Nested PCR
 Repeated PCR with nested primers Achieving ultra-sensitive detection
 Good adapter primers for nested PCR:

bind only to the adapters, andamplify nothing directly from the samples!

Application – PCR [cont.]
5’S (sample)

3’
Adapter

Right specific primer
Adapter3’

Left specific primer

S’ (complement to S)

5’• We want a pair of good adapter primers
which amplify nothing directly from S or S’.
(Adapter primers are complements to adapters.)

Application – PCR [cont.]
5’

S (sample)

3’
Adapter

Right specific primer
Adapter3’

Left specific primer

S’ (complement to S)

5’• If (A,B) is a missing pair in S and S’,
then (A’,B) is not a pair of binding sites
for any region of length less than .

Application – PCR [cont.]
5’S (sample)

3’Adapter

Right specific primer
Adapter3’

Left specific primer

S’ (complement to S)

5’• So (A’,B) satisfies a necessary conditionof being a good adapter primer pair!!

Previous Work

Inenaga, Kivioja and Makinen. [WABI’04]
proposed a bit-table based algorithm to find amissing pattern pair of the same length.
We also gave a suffix tree based algorithm tosolve a generalized problem where the patterns in
the pair can be of different length.

Complexity ComparisonsFinding missing pattern pair of same length

time

space

our algorithmO(nloglogn)O(n)bit-table algorithm ofinenaga et al. [WABI’04]

O(n(+loglogn))O(n)  is the alphabet size.

  is typically 5000 (due to PCR application)!

Complexity Comparisons [cont.]
Finding missing pattern pair of different length

time

space

our algorithmO(nlogn)O(n)suffix tree algorithm A of
Inenaga et al. [WABI’04]

O(n2)

O(n)

suffix tree algorithm B of
Inenaga et al. [WABI’04]

O(nlogn)O(nlogn) Our algorithm does not need a suffix tree –not only faster but also simpler.

Single Missing PatternWe start with finding a single missing pattern.

KEY: There are at most k patterns of length k.

nT
P1
P2kPk-1
Pkn-k+1<nSingle Missing Pattern [cont.]- We have k < logn .
- If k is the largest integer for whichall k patterns of length k exist in T,
then there is a missing pattern of length logn .
nT
P1
P2kPk-1
Pkn-k+1<nSingle Missing Pattern [cont.]Compute a bit table of all patterns of length lognusing a bijective mapping f from patterns tointegers. (O(n) time, using e.g. Karp & Rabin algo.)
1) there exists a missing pattern of length lognoutput it.
2) otherwise (all patterns of length logn arepresent in T)
there is a missing pattern of length logncompute and output it.

Missing Pair of Fixed LengthInput: text T, threshold ,pattern lengths a and b
Output: missing pattern pair (A, B)
such that |A| = a and |B| = bAssume w.l.o.g. a > b.
We consider the case a < m, where m is the length of
the shortest single missing pattern P in T.
Or else P can be paired with any pattern of length b.
Let Na = a and Nb = b (Note n > Na > Nb).

Missing Pair of Fixed Length [cont.]
i1

T

i2

i3

AaL0hNa-1• Let f (A) = h.
i1i2i3• L : array of size Na,where L[h] is the list ofoccurrences of A in T.

Missing Pair of Fixed Length [cont.]
jT
BHb0• Let f (B) = h’.
j h’n-b• H : array of size n-b+1,
where H[j] = h’.

Missing Pair of Fixed Length [cont.]
i1

T




B1

LH

00f (B1) = h1
 h1

hi1i2i3

M0h1 1i1
Nb-1

Na-1

CM = 0n-bMissing Pair of Fixed Length [cont.]
i1T



B1

LH00f (B1) = h1
 h1

hi1i2i3

M0h1 1i1


Nb-1Na-1

CM = 1n-b

Missing Pair of Fixed Length [cont.]
i1T

B2

LH0

h0i1i2i31
 hh2 f (B2) = h2i1

M0h1 1
h2 1
Nb-1

Na-1

CM = 1n-b

Missing Pair of Fixed Length [cont.]
i1T




B2

LH0

h0

i1

i2i31
 hh2 f (B2) = h2i1



M0

h1 1
h2 1
Nb-1

Na-1

CM = 2n-b

Missing Pair of Fixed Length [cont.]
The iteration ends
when CM = Nb.
This case, all patterns of length b are -close to A.
 or when all positions in L[h] are processed.
This case, scan M and find a missing pattern oflength b. The algorithm outputs the missing pair.
The algorithm runs in total of O(n) time and O(n)space.

Missing Pair of Same Length [cont.]Monotonicity property: If (A, B) is a missing pair,
for any superstrings C, D of A, B resp., (C, D) isalso a missing pair.
By monotonicity property we can do a binary
search on the length 1… logn of the patterns
using the aforementioned algorithm, and find theshortest missing pair of same length.
It takes O(nloglogn) time and O(n) space.

Missing Pair of Different Length

It is not hard to extend the algorithm to thecase where A and B do not necessarily have thesame length.
We can find such a missing pair in O(nlogn) timeand O(n) space.

Experiments
 Linux on 1GHz CPU with 2GB RAM.
 In Java. http://www.cis.upenn.edu/~angelov
 Human genome (2.5GB) fromftp://ftp.ensembl.org/pub/current_human/  = 5000.

Experiments [cont.]
We found 238 pairs of missing patterns of length
8 for the human genome.
For the Baker’s yeast genome, the patterns in theshortest missing pairs are also of length 8 ! [Inenaga et al.
WABI’04]

There are common missing pairs of patterns oflength 8 for the human and yeast genomes.

Experiments [cont.]
Missing pattern pairs of length 8 for both the human and theyeast gemones. The reverse complements are also missing

missing pairyeast ABhuman AB

(AATCGACG,CGATCGGT)

5008

6458

(CCGATCGG,CCGTACGG)

5658

6839

(CGACCGTA,TACGGTCG)

13933

7585

(CGACCGTA,TCGCGTAC)

5494

5345

(CGAGTACG,GTCGATCG)

5903

8090

(CGATCGGA,GCGCGATA)

6432

6619

Conclusions
We solved the missing pattern pair problem inO(nloglogn) time for the same length case, andO(nlogn) time for the different length case.
Both in O(n) space.
We also developed an alternative algorithm tosolve this problem, and moreover solved extendedproblems (see the proceedings).