Finding Optimal Pairs ofCooperative and Competing
Patterns with Bounded DistanceShunsuke Inenaga1, Hideo Bannai2, Heikki Hyyrö4,Ayumi Shinohara3,4, Masayuki Takeda3,5, Kenta Nakai2,and Satoru Miyano2
1Department of Computer Science, University of Helsinki, Finland
2Human Genome Center, Institute of Medical Science, University of Tokyo, Japan
3Department of Informatics, Kyushu University, Japan
4PRESTO, Japan Science and Technology Agency (JST)
5SORST, Japan Science and Technology Agency (JST)Pattern Discovery
Input : set S of strings s1, s2, …, sm
Output : pattern p that characterizes input SSPattern discovery is a core of Discovery Science.

Jump and dive into the sea during summer vacation.

p = padova
2Pattern Discovery in Bioinformatics
Machine Discovery System BONSAI(Shimozono et al. 1994)• finds optimal substring patterns tocharacterize input sequence set S.
• has been extended to finding:
subsequence patterns (Hirao et al. 2000)
episode patterns (Hirao et al. 2001)
VLDC patterns (Inenaga et al. 2002)
approximate FVLDC patterns (Takeda et al. 2003)
Refer to the invited talk by Ayumi Shinohara in DS’04“String Pattern Discovery”3Composite Pattern Discovery
 More than one sequence element may actin ensemble!

 Sequence elements may not necessarily becooperative – they may be competitive.

 Consider finding Boolean combination ofpatterns.

e.g.: ppp

q : p AND q
q : p OR q
q : p AND (NOT q)
4

Examples
S = {s1, s2, s3, s4, s5}
s1ps2

qs3s4

qs5

pppq

q

p
true

q
false

p OR q p AND (NOT q)
true
true

false

true

true

false

false

false

false

false

true

true

true

false

true

truetruefalse

substrings: exact match only (no mismatches)5Recent Work by Bannai et al.
“Finding Optimal Pairs of Patterns”(Bannai et al. in WABI’04)

 Efficient algorithm for finding optimal

Boolean pattern pair of substring patterns O(N ) time & O(N) space2(N: total length of strings in input set S)

 O(N ) time & O(N) spacekfor Boolean combination of k substring patterns
6And This Work…
 Introduces the notion of α-distance between

patterns in Boolean pair w.r.t.

 Denoted ps1pαqs3pαs4s5

α

false

true

truefalse

pfalsetrue

qtruefalse

qαpα

q.
p α qfalseαpααααp αq
trueqαs2α q and p(AND).

ααqpαpαq7

Our Result
Input : set S of strings and distance α
Output : optimal pattern pair pα q and pα

q w.r.t. S

2 O(N ) time & O(N) space (not depending on α)k O(N ) time & O(N) spacefor combination of k substring patterns
 Improves the worst case complexity O(αk Nk+1 logN)

due to Arimura et al. (proximity patterns).

9

Optimality of Pattern Pair
Pattern pair π is optimal w.r.t. S
Pattern pair π maximizes score(M(π, S))
Examples of score function:
 Gini index
 Chi-square statistic Rank-sum test
M(π, S) : num. of strings in S that π matches.
Assume score can be computed in O(1) time.10

Suffix Tree
Suffix Tree of s (ST(s))• Tree structure which
represents all suffixes of s.

c ooa$1• Each leaf is marked withits suffix number.

coa$1a• ST(s) can be constructedin O(n) time (n = |s|).

$1(Weiner 1973, McReight 1976,Ukkonen 1995, etc.)

53

1$1coaa$1 $14

s = cocoa$1123456

2611

Generalized Suffix Treepath(v) = concatenation oflabels from root to node v.

Generalized ST (GST(S))
a• ST for set S of strings.
• Can be constructedin O(N) time (N = ||S||).
oaac$2 o$2$1

8

10

5c o

7$1ocao o$2 $2a$1

93$2cc$2o a oa $1 a$1$1142

S = {cocoa$1, cacao$2}1161212

Find Best Single Pattern We can restrict the candidates for pattern p

to those represented by the nodes of GST(S).
 there are only O(N) nodes

 For all nodes v in GST(S), M(path(v), S) is

computable in total O(N) time.

(Color Set Size Problem, Hui 1992)

 Output path(v) of the best score.
 O(N) time & space for single pattern case.
13

Find Best Pair pα qAlgorithm Sketch:
 For each candidate of first pattern p

Compute Zone(p, S) - the region covered by αfrom each position of p in S.
2. Build sparse suffix tree (SST) on Zone(p, S).
3. For each node u in SST, compute score.
1.

 Output pattern pair of the best score.

Sparse suffix trees have been studied byKärkkäinen and Ukkonen 1996, Andersson et al. 1999 14

Zone(p, S)
GST(S)
p = path(v)vs1…smα

αZone(p, S)
15

Build SST on Zone(p, S)
SST on Zone(p, S)

q = path(u) where u
is any node in SSTZone(p, S)
q = path(u) for some node u in SST on Zone(p, S)
q is such a pattern that p

α q matches S16

Analysis
 We have O(N) choices for first pattern p.
For each candidate p- Compute Zone(p, S) – O(N) time
- Construct SST on Zone(p, S) – O(N) time Thus it takes O(N ) time in total.
2

 We need O(N) space since we use one SST

at each stage of the algorithm.

17

Find Best Pair p

O(N2) timeαq

O(N) timeO(N2) timeM(π, S) = M(p, S) – M(π, S)
π=pα q,π=pαq

18

Implementation with Suffix and LCP Arrays
Simulate GST traversalby suffix and LCP arraysa space-economicaloaac$2 o$2$1810c o

57$1ocao o$2 $2a$1

931$2cc$2o a oa $1 a$1$1
4

2

116SA(S)

8

10

5

7

9

3

1

4

2

11612LCP(S)

0

1

10

2

1

20

1

100

1219

Implementation with Suffix and LCP Arrays
SST traversal also
by suffix and LCP arrays

oaaacaoa$2 o $1$2c$2 o$2$1

810c

579oo $1coac$1aoa $1$131$2$2

42116SA(S)

8-

57-

31-

2-

612LCP(S)011021201100

1220

Extended to Correlated Patterns
 Each sequence si in S may be associated withnumeric value ri, such as gene expression level.

 Wanted!:pattern pair π that matches sequences si with high ri,
but doesn’t match sequences sj with low rj (or vice versa).

 pattern pair π that maximizes score(M(π, S), R(π, S)).

 O(N ) time & O(N) space to find2optimal pairs pα q and pαqR(π, S) : sum of r for all s which π matches. 21

Computational Experiments
Yeast mRNA
3’UTR predicted processing site sequences(100nt each)379 fast degrading(t0.5 < 10 min.)393 slowly degrading (t0.5 > 50 min.)Divided according to mRNA decay rate measurements(Wang et al. 2002, Graber 2003)

score function: chi-squared test statistic
22

Computational Experiments (Contd.)

BESTAUAAUA
AUA

UGUA

10

fast
159/393slow
248/379

known biding site of the PUF protein
which is important in mRNA regulation

UGUA

268/393190/379

UGUA

231/393

123/379

10

may influence how efficiently UGUAfunctions, when it is close to UGUA??

23

Conclusions
O(N2) time O(N) space algorithm to findoptimal pattern pair with bounded distance αEfficient implementation with suffix arrays



Biologically relevant patterns discoveredIt can be extended to more advanced versionsof bounded distance:B) O(m N ) time & O(m N) space
222C) O(N ) time & O(N ) space
32D) O(m N ) time & O(N +m N) space
232224