Mining RNA Families with Structure Histograms
Yudai Kawai

Mahito Sugiyama

Akihiro Yamamoto

Grad. Sch. of Informatics
Kyoto University
Kyoto, 606-8501, Japan

Grad. Sch. of Informatics
Kyoto University
Kyoto, 606-8501, Japan
JSPS Research Fellow

Grad. Sch. of Informatics
Kyoto University
Kyoto, 606-8501, Japankawai@iip.ist.i.kyotou.ac.jp

mahito@iip.ist.i.kyotou.ac.jp

ABSTRACTIn this paper we present the idea of mining RNA families
with structure histograms. A structure histogram is a histogram employing structures of some type as attributes. As
structures of RNA sequences we adopt their secondary structures which are not pseudo-knots. Unfortunately to obtain
the histogram for an RNA sequence of its length l needs
more than the (l/2)-th Catalan number time, but show thatthe value for every structure in the histogram is calculated
in the time O(l3 ). We also give some experimental results
by applying structure histograms obtained from real RNA
data to some mining methods and demonstrated the casesthat structure histograms works eﬀectively.

Keywords
RNA sequences, RNA families, Secondary structure, Datamining

1. INTRODUCTION
In this paper, we present an idea of mining RNA sequenceswith structure histograms. RNA is a kind of nucleic acidsimilar to DNA. In analyzing RNA molecules their structures are important because they are considered to aﬀect
the functions of the molecules. An RNA molecule forms awind three-dimensional structure and the structure is basedon its secondary structure, which is formed by the role of
Watson-Crick complementary base pairs in it. In this paper
we pay our attention to the secondary structures, and use
them for mining of RNA data.
The secondary structure of a RNA molecule is obtained byrepresenting it as a sequence, which we call an RNA sequence, consisting of four symbols A, U, C, and G, where U
is used instead of T for DNA sequences. Pairs of A-U and
C-G in the RNA sequence are called Watson-Crick complementary base pairs and some of them are used in forming
the secondary structure. RNA sequences are stored in somedatabase, e.g, Rfam database, and published through the

RNA sequence

RNA secondary structure

loop
stem

CAGCACUUGACU

C

5'

C

A

G

C

A

U

A
U

G

C
U
3'

branch point

Figure 1: An example of secondary structure of an
RNAInternet. Note that not all base pairs are used for secondary
structure. This means that there can be theoretical secondary structures in an RNA sequence, and our idea is touse such theoretical ones as attributes in data mining. In
this paper the word “secondary structure includes such theoretical structures. Because secondary structures are formed
with the base pairs, some of them can be formalized with acontext free grammar and we use only such type of structures. A type of structures which cannot be represented
with the grammar is “pseudo-knot .
Our idea is to make histogram of structures for every RNA
sequences. We intend to measure the strength of each structure in a given RNA sequences, by counting how many times
the structure can occur as a theoretical structure in the sequences. In this paper we give a method of the number ofoccurrences of structures. Because the total time complexity of counting occurrences of all structures would be represented with the Catalan numbers, we propose an eﬃcientof the method for each structure. We also give some experimental results by applying structure histograms obtained
from real RNA data to some mining methods.
This paper is organized as follows: In Section 2 we give ourdeﬁnitions of structures and their instances. In Section 3 wegive the method of calculating the numbers of occurrencesof every structure. In Section 4 we give some experimental
results by using structure histograms, and we conclude in
the last section.

2.
The 5th International Workshop on Data-Mining and Statistical Science(DMSS2011) Osaka, Japan, March 2011

akihiro@i.kyoto-u.ac.jp

STRUCTURES AND INSTANCES

We treat every RNA as a non-empty sequence of an alphabet Σ = {A, U, C, G}, that is, an element of Σ+ and call it
an RNA-sequence. The length n of an RNA-sequence σ =a1 a2 · · · an is denoted by n =| σ |. A number i (1 ≤ i ≤ n)

is called an occurrence if it denotes the index of the symbol
xi , and σ[i] denotes the symbol ai , and σ[i : j] denotes thecontinuous subsequence σ = ai ai+1 · · · aj . A pair (i, j) of
occurrences of σ such that i < j is called a candidate pair ,or c-pair for short, if (σ[i], σ[j]) is either of (A, U ), (U, A),(C, G), and (G, C). A c-pair represents the indices of σ theelements at which may construct a Watson-Crick complementary base pair.

CAGCACUUGACU112CAGCACUUGACU112CAGCACUUGACU
2
12For two c-pairs p = (ai1 , aj1 ) and q = (ai2 , aj2 ) in σ, wedeﬁne two binary relations < and ≺: q < p if i2 < j2 < i1 <
j1 , and q ≺ p if i1 < i2 < j2 < j1 .
We deﬁne structures with a context free grammar G on analphabet X = {x, y} with a non-terminal S and rules:
R1: S → xy,

R2

: S → xSy,

R3

: S → SSb
CAGCACUUGACUcCAGCACUUGACUdCAGCACUUGACUCAGCACUUGACU

Figure 3: Examples of tokens

Cn = {w ∈ L(G) | |w| = 2n}(1)

In order to deﬁne matching of a structure S and a sequenceσ, we distinguish x’s and y’s in S in the following manner:
We give a suﬃx k to each x if the x is the k-th occurrence in
S with scanning it from left to right. We also give a suﬃx
k to the y which matches xk . We regard every xk and yk as
a variable, and call the pair a variable pair . For example, astructure S = xxyyxy is regarded as a sequence of variables
x1 x2 y2 y1 x3 y3 .
A substitution for a structure S = z1 z2 · · · z2n is a mappingθ : {x1 , . . . , xn , y1 , . . . , yn } −→ Σ such that (θ(xk ), θ(yk )) isa c-pair for every k = 1, 2, . . . , n. A sequence τ in Σ+ is an
instance of S if τ = Sθ for some substitution θ. The structure S appears in a sequence σ = a1 a2 · · · an if σ contains
an instance of S as its subsequence, that is, there are indicesi1 < i2 < · · · < im and a substitution such thatai1 ai2 · · · aim = Sθfor some substitution θ. The indices i1 and im are respectively called the left-most position and the right-most of theoccurrence of S in σ.
A continuous subsequence τ of a sequence of σ is a token if
no c-pair (a1 , a2 ) locates outside of τ , like a1 · · · τ · · · a2 . A
continuous subsequence T of a structure S is a token if novariable pair xj and yj locates outside of T . In the sequence
illustrated in Fig. 2, the sets {(A, U ), (G, C)} and {(G, C)}
are tokens. The set of tokens in σ (S) is denoted by T (σ)(resp. T (S)).

3. CONSTRUCTION OF HISTOGRAMS

Figure 2: An example of a structure and its instancesa

We call every word in L(G) a structure. It is well-known thatthe context free language L(G) is, by replacing x with ( andy with ), the set of the sequences of parentheses correctly
matched, and the size of the set

is called the n-th Catalan number and given as
„ «
1
2n
Cn =
.
n n+1

CAGCACUUGACU
2
11For a given sequence σ and a structure S, we let N (σ, S) be
the number of occurrences of S in σ.
In order to calculate N (σ, S) for all S, we generate S recursively according to the rules in G. For the convenienceof explanation, we introduce a parameter p for representing|S|/2, the number of pairs in S, and another i for representing |T (S)|/2. We also deﬁne two operations ρ and ϕ forstructures S and T as
ρ(S) = xSy,
ϕ(S, T ) = ST.
A brief view of the calculation is as follows: In the calculation we use a set Sp consisting of pairs of the form (S, N (σ, S)
such that |S|/2 = p. The calculation starts with putting
S1 = {(xy, N (σ, xy)}, and extend Sp by generating longer
structures.
1. At ﬁrst consider the case p = 1. The only structure
satisfying |S|/2 = p = 1 is a variable pair S = xy
regarded as x1 y1 , we generate S1 for by enumerating
all c-pair as its instances.
2. Next consider the cases p > 1. Generate instances ofall structures S such that |S|/2 = p• For the case i = 1, update Sp by counting N (σ, S)
for every structure S with |T (S)| = i = 1, which
are generated by applying ρ to structures S 0 with
|S 0 |/2 = p − 1.
• For the case i = 1, update Sp by counting N (σ, S)
for every structure S with |T (S)| = i > 1, which
are generated by applying ϕ to structures S1 andS2 with |S1 |/2 + |S2 |/2 = p.

abInside structure

Algorithm 1:
StructureHistogram(a sequence σ, a distance d)

Inside structure

Figure 4: Generating structures S with |T (S)| = 1abLeft structure

Left structure

Figure 5: Generating structures S with |T (S)| > 1

P = 1 17
P=2
P=3

33

34

15
16
I=1

20

13
I⩾2

10

1: S1 = CountP airs(σ)
2: for p = 2 to (|σ| − d)/2 do
3:
Tp1 = ComposeInN est(p)4:
Sp = {Sp1 }5:
for all i such that 2 ≤ i ≤ p do
6:
Tpi = ComposeInP arallel(p, i)
7:
add Tpi to Sp
8:
end for9: if Sp = φ then
10:
break
11:
end if
12: end for
Algorithm 2: CountPairs(a sequence σ, the least distance d)
1: for lef t = 1 to |σ| − 2 do
2:for right = |σ| to lef t + d do
3:
if isPair(σ,lef t, right) then4:add (lef t, right, 1) to Oxy5:
end if
6:
end for
7: end for
8: T11 = {(xy, Oxy )}9: S1 = {T11 }10: return S1

Figure 6: 1 ≤ P ≤ 3
The generation of structures with ρ and ϕ is illustrated inFig. 4 and Fig. 5, respectively.
We explain the calculation method more precisely, by changing the form of the tuples corrected in Sp . In the calculation
we generate tuples of the form(l, r, N (σ[l : r], S)
for every structure S. For example, for the structure andthe sequence illustrated in Fig. 2, tuples(1, 12, 2), (2, 12, 1), (2, 11, 1)
are generated (Fig. 2).
Let us assume that a sequence σ such that |σ| = n is given.
At ﬁrst we set p = 1. Since the only structure that we haveto treat is S = xy, N (σ, xy) means the number of c-pairs in
σ (Algorithm 2). The algorithm is modiﬁed so that we cantake the least distance of c-pairs into account.
Now we set p = 2. The number of structures in this caseis obtained by choosing two structures and instances of thecase p = 1. The methods varies according to the value ofi. At ﬁrst we set i = 1, and apply the ρ operator to every
structure S generated in the case p = 1. We have only one
structure xSy (Fig.4(a)). Next we set i = 2, we apply theoperator ϕ. Choose a structure S of the case p = 1, we put
another structure T with p = 1 and i = 1(Fig.5(a)).
In the case p = 3 and i = 1, we apply the operator ρ in thesame way as in the case p = 2 and i = 1 every structure with

p = 2(Fig.4(b)). In the case p = 3 and i ≥ 2, we ﬁrst apply
the ϕ operator at ﬁrst to every structure S with p = 3−1 = 2
and and every structure T with p = 1 and i = 1. Then weapply ϕ to S with p = 1 and T with p = 3 − 1 = 2 and i = 1(Fig.5(b)). Note that we can choose the structure T withi = 1 in the last case. In Fig. 6 we show the structures of thecases p = 1, 2, 3 and some examples of numbers of instances.
The method is illustrated in Algorithm 1-4. The algorithm
uses three sets OS , Tpi Sp . The set OS is used to store
tuples (l, r, N (σ[l : r], S) for a structure S. If |S|/2 = p and|T (S)| = i, then OS is stored in Tpi . For every p Tpi is storedin Sp . It is important how to implement the OS , Tpi Sp inmaking the algorithms eﬃcient, and we discuss the ways in
the next section.

4.

ANALYSIS OF THE ALGORITHM

The number of structures consisting of n pairs, that is then-th Catalan number Cn , is represented as follows:Cn=an + b n(2)an= (an−1 + bn−1 )a1

(3)

bn

= Σn−1k=1 (an−k + bn−k )ak

(4)

a1

= 1, b1 = 0(5)where an is the number of structures consisting of only one
token, and b is that containing more than one tokens. The
equations (3) and (4) respectively correspond to Algorithm
3 and 4 This means that the order of the total calculation
is diﬃcult to decrease, and we make our eﬀort to make thecalculation for each structure S more eﬃcient,At ﬁrst estimate the complexity of enumerating all instances

Algorithm 3: ComposeInNest(int p)
1: for all S appearning in Sp
2:
OxSy = {(t.lef t, t.right, s.count · t.count) |s ∈ OS , t ∈ Oxy , s ≺ t}(procedure ρ)3:
if OxSy 6= ∅ then4:add (xSy, OxSy ) to Tp1
5:
add Tp1 to Sp
6: return Sp

Left-end
position

Right-end
position# structure
instances

1

4

1

6

2

9

4

5

2

6

3

9

6

2

Algorithm 4: ComposeInParallel(int p, int i)
1: for k = i − 1 to 1 do
2:
for all S appearing in Tk(i−1) , T appearing in T(p−k)i3:
OST = {(s.lef t, t.right, s.count · t.count) |s ∈ Tk(i−1) , t ∈ T(p−k)i , s < t }4:
if OST 6= ∅ then5:add (ST, OST ) to Tpi
6: return Tpi

of a ﬁxed structure by using a naı̈ve method. Assume that|σ| = l for a given sequence. In the case of p = 1, this meansthat all pairs in σ and this takes O(l2 ) steps. For p > 1
every structure is generated by ρ or φ. Since structure isstored in the form of the tuple 2 in OS , it takes O(l2 ) steps
for a ﬁxed argument of ρ and φ．Therefore enumerating its
instances takes O(l2 ) ∗ O(l2 ) = O(l4 ) steps.
In order to reﬁne these computation, we take our attention
how to keep the tuples in OS . At ﬁrst we change OS as alist LS of trees of its depth 1, where every tree represents
a subset consisting of tuples which have the same left-mostposition. The root represents the same left-most position,and leaves are sorted in the ascending order. The trees arealso listed in LS in the ascending order of their roots (Fig. 7).
This data structure for storing them should make the comparison of two occurrences of structures. Consider the casewhen we compare S and S 0 . The left-most position of an
instance p is denoted by p.lef t and its right-most positionis p.right. With every q ∈ S, we compare every p ∈ S 0 . At
ﬁrst we ﬁx q.lef t and q.right, and also p.lef t. We checkp.right in the ascending order. When all p.right is check,we increment p.lef t, and check p.right. After all p.lef t ischecked, we increment q.right. We present this method in
Algorithm 5 and 6.
Now we improve the time complexity of comparison. The
key idea of the improvement is to make another list MS
for OS and use both of LS and MS (Fig. 8)．The list MS
also consisting of trees but every tree represents the set oftuples of the same the right-most position. The constructionof every tree in MS and the list MS is in the symmetricmanner of the construction of LS .
Moreover, each leaf L of a tree in LS , we give an additional
attribute which is the sum of the number of instances above
L in the tree.
We change the method as illustrated in Fig. 9．When weconstruct a new structure S with the φ operator from S1

Figure 7: The method of storing structure and its
instances
Algorithm 5: CompareInNest(Candidate Out,
Candidate In, int p, int i, int j)
1: for o.lef t in {Out.lef ts} do2:for o.right in {Out.rights} do3:for i.lef t in {In.lef ts} do4:
if o.lef t < i.lef t && i.lef t < o.right then5:
for r.right in {R.rights} do
6:
if i.right < o.right then7:hash = {(o.lef t, o.right, i.count)}8:
Cp1j = Cp1j ∪ hash
9: return Cp1jand S2 , we use LS1 and MS1 . At ﬁrst ﬁx the left-mostposition of S1 (Fig. 9 (a) ) and the right-most position of
S2 (Fig. 9 (b) ). Then search the left-most position of S2
in the descending order and simultaneously the right-mostposition of S1 (Fig. 9 (c)(c’) ). In the example illustrated
in Fig. 9, we assume that the left-most position of S1 S2 is
1 and the right-most position of S1 S2 is 15. Then all the
combination of the right-most position of S1 and the leftmost position of S2 are (9 , 10) , (6 , 7) , (4 , 5). The total
number of instances of S is
15 = 7 ∗ 1 + 3 ∗ 2 + 1 ∗ 2This method takes O(2l) for every end-pair of S ，the total
time is O(l3 )．For the operator ρ we can improve in a similarmanner.
Algorithm 7 and 8 includes the improvement.

5.

DATA MINING OF RNA FAMILIES

Here we demonstrate typical data mining tasks, classiﬁcation and clustering of real RNA families, by using the obtained candidates of RNA secondary structures, and analyze
eﬀectivity of our results. In particular, we focus on the minimum length of distance d = |j − i| for a pair of i-th baseand j-th base. We show that dimension reduction is realized
by increasing d experimentally.

5.1

Materials and Methods

All experiments were performed on R version 2.12.1 [10]. We
used Mac OS X version 10.6.5 with 2.93 GHz Intel Xeon and
32 GB memory.

Algorithm 6: CompareInParallel(Candidate L,
Candidate R, int p, int i, int j)

The number of
Left-end Right-end Sum of
position position # instances

1: for l.lef t in {L.lef ts} do2:for l.right in {L.rights} do3:for r.lef t in {R.lef ts} do
4:if l.right < r.lef t then5:
for r.right in {R.rights} do
6:hash = {(l.lef t, r.right,
l.rightcount · r.lef t.count)}
7:
Cpij = Cpij ∪ hash
8: return Cpij

a 1

2

1

3

3

6

3

2

5

9

7

2

7

2

1

10

c’

6

5

9

11

The number of# structure Left-end Right-end Left-end Right-end Sum of
instances position position position position # instances

4

5

φ

< The number of

15 b

c

1

15

15

2

15

3

# structure Left-end Right-end
instances position position

15

1

3

2

15

Figure 9: Comparing structures
Left-end
position

1

2

Right-end # structure
position instances

Sum of# instances# structure
instancesLeft-end Right-end
position position

4

1

1

1

1

4

Algorithm 7: CompareInNest2(Candidate Out,
Candidate In, int p, int i, int j)

6

2

3

2

2

5

9

4

7

2

1

6

5

2

2

3

2

6

3

5

4

1

9

6

11

6

2

1: for o.lef t in {Out.lef ts} do2:{pi.lef t } = 03:for o.right in {Out.rights} do4:for i.lef t in {In.lef ts} do
5:
if o.lef t < i.lef t then6:
if i.lef t < o.right then7:i.right = max(pi.lef t , min(In.rights))
8:while next(i.right) < o.right do
9:i.right = next(i.right)
10:
if pi.lef t 6= min(In.rights) then11:hash = {(o.lef t, o.right, i.right.count)}12:
Cp1j = Cp1j ∪ hash13:
pi.lef t = i.right14:{sum right counts by every left index}
15: return Cp1j

9

Figure 8: New list for improvement
Every data set was constructed from results obtained from
our algorithm (Figure 10). Each row corresponds to each
RNA sequence, and each attribute means the number ofcandidates of secondary structures for the corresponding
RNA sequence. RNA families IRE, Histone3, CRISPRDR2, CRISPR-DR3, and CRISPR-DR4 were collected as
benchmarks from Rfam1 [5] (Table 1), since the number ofsequences of IRE and Histone3 are largest in which the average length of RNA sequences is relatively small (under 40).
Thus we can make data sets in reasonable time. The average
length of sequences in CRISPR-DR2 and CRISPR-DR3 arealmost same, hence we can test classiﬁcation without theeﬀect of the diﬀerence of length of each sequence.
We performed classiﬁcation of RNA families by SVM with
the RBF kernel using our constructed data sets. The R
package e1071 [9] (the R interface to libsvm [1]) was used,
and accuracy was obtained by 10 cross-validation. First weclassiﬁed two families of IRE and Histone3, second CRISPRDR2 and CRISPR-DR3, and third three families IRE, Histone3, and CRISPR-DR4.
For clustering of RNA families, we performed K-means and
DBSCAN [4], since K-means is the standard clustering algorithm and DBSCAN is the typical method to ﬁnd arbitrary
shaped clusters. The R packages fpc was used for DBSCAN.
We used two RNA families IRE and Histone3. To evaluate
results of clustering, we measured the adjusted Rand index(takes values in [−1, 1], to be maximized) [7], which is the
typical external criterion, calculated by the R package clues
1
The newest version 10.0 is available at
http://rfam.sanger.ac.uk/[2]. We tuned parameters for DBSCAN and report the best
results.

5.2

Results and Discussion

We show results of classiﬁcation in Table 2. We can seethat in most of cases, accuracy become higher and higher
when d increases, and the number of attributes decrease
monotonically. This means that dimension reduction can be
performed eﬀectively with the parameter d and, moreover,
our results of RNA secondary structure candidates can beused eﬀectively for learning classiﬁcation rules of RNA families. Average length of RNA sequences in CRISPR-DR2 andthat in CRISPR-DR3 are almost same, thus we can classify
two families with high accuracy even if their average length
are similar. Our results are competitive compared to results
reported in literatures [3, 8, 13, 14]. However, some experimental settings are diﬀerent, thereby more experiments areneeded.
Table 3 shows results of clustering. All adjusted Rand indexes are relatively high, thus this means that our data sets
reﬂect some features of RNA families. Furthermore, theadjusted Rand indexes become higher and higher when dincreases from 1 to 5 in K-means and 1 to 4 in DBSCAN,
hence dimension reduction can be performed eﬀectively.

6.

CONCLUSION

Algorithm 8: CompareInParallel2(Candidate L,
Candidate R, int p, int i, int j)
1: for l.lef t in {L.lef ts} do2:for r.right in {R.rights} do
3:
if l.lef t < r.right then4:
crrtIdx = max({R.lefts})
5:
for r.lef t in {R.lef ts} by desc do
6:
for l.right in {L.rights}(except more than crrtIdx) by desc do
7:
if l.right < r.lef t then8:hash = {(l.lef t, r.right,
l.right.count · r.lef t.count)}
9:
Cpij = Cpij ∪ hash10:
crrtIdx = l.right
11:
break
12:
{sum right count by every left index}
13: return Cpij

Table 1: Benchmark RNA families used for classiﬁcation and clustering.
Family name# RNA sequences Average length
IRE
Histone3
CRISPR-DR2
CRISPR-DR3
CRISPR-DR4

247
381
64
41
61

29.86
30
29.86
30
28

RNA

[]

[[ ]]

[[ ]] [ ][[[[ ]][ ]]]CAGCAUCGAUGA

18

43

36

45

RNA

[]

[[ ]]

[[ ]] [ ][[[[ ][[ ]]]]CAGCAUGGAGAC

17

33

34

3
[[[[ ]]]]

RNA

[]

[[ ]]

[[ ]] [ ]AUUAGUUGUCGA

16

34

39

12

RNA

[]

[[ ]]

[[ ]] [ ][[[[ ]]]][[[[ ]][ ]]]CAGCAUCGAUGA

23

93

47

0

45

0

CAGCAUGGAGAC

17
16

33
34

34
39

0
12

0
0

3
0

AUUAGUUGUCGA[[[[ ][[ ]]]]

Figure 10: Construction of data sets from the number of candidates of secondary structures for each
RNA sequence.

Table 2: Results of classiﬁcation. The parameter dwas increased from 1 to 6, and accuracy of classiﬁcation was calculated.
IRE and Histone3
accuracy (%)# attributes

d=1

2

3

4

5

6

60.7
11144

96.8
2910

96.8
1027

97.9
335

99.0
170

99.7
114

CRISPR-DR2 and CRISPR-DR3
We have presented the method of obtaining structure histograms for RNA sequences. The total amount of the timecomplexity of obtaining the histogram for an RNA sequenceof its length 2n is of the n-th Catalan number, but, by designing new data-structures of keeping instances, we showthat the value for every structure in the histogram is calculated in the time O(l3 ). We also give some experimental
results by applying structure histograms obtained from realRNA data to some mining methods and demonstrated thecases that structure histograms work eﬀectively. For applying structure histograms to more practical problems, wehave to consider about the dimension reduction more seriously and this is one of our future work.
Enormous RNA sequences are accumulated in previous researches, and many methods have been proposed for predicting RNA secondary structures. However, because of thelarge size of the RNA data, predicting secondary structures
does not catch up analyzing RNA sequences. We expectthat our method could contribute semi-automatic predictionof secondary structures and predicting RNA functions.

Acknowledgments
The authors are grateful for valuable discussions and comments to Toshiki Saitoh, Takeaki Uno, and Koichiro Doi.
This work is partially supported by Grant-in-Aid for Scientiﬁc Research (A) 30230535 from JSPS.

7. REFERENCES[1] C. C. Chang and C. J. Lin. LIBSVM: A library forsupport vector machines, 2001.
[2] F. Chang, W. Qiu, R. H. Zamar, R. Lazarus, andaccuracy(%)# attributes

d=1

2

3

4

5

6

61.0
14101

61.0
3851

61.0
1053

92.4
388

91.4
174

88.6
94

IRE, Histone3, and CRISPR-DR4
accuracy (%)# attributes

d=1

2

3

4

5

6

55.3
12633

55.3
2960

90.3
1078

95.2
446

98.3
177

98.8
118

X. Wang. clues: An R package for nonparametricclustering based on local shrinking. Journal of
Statistical Software, 33(4):1–16, 2010.
[3] L. Childs, Z. Nikoloski, P. May, and D. Walther.
Identiﬁcation and classiﬁcation of ncRNA molecules
using graph properties. Nucleic Acids Research,
37(9):1 – 12, 2009.
[4] M. Ester, H. P. Kriegel, J. Sander, and X. Xu. A
density-based algorithm for discovering clusters inlarge spatial databases with noise. In Proceedings of
the Second International Conference on Knowledge
Discovery and Data Mining, volume 96, pages
226–231, 1996.
[5] P. P. Gardner, J. Daub, J. G. Tate, E. P. Nawrocki,
D. L. Kolbe, S. Lindgreen, A. C. Wilkinson, R. D.
Finn, S. Griﬃths-Jones, S. R. Eddy, and A. Bateman.
Rfam: updates to the RNA families database. Nucleic
Acids Research, 2008.
[6] R. L. Graham, D. E. Knuth, and O. Patashnik.
Concrete mathematics: A foundation for computerscience, volume 2. Addison-Wesley Reading, MA,

a

b

400

400

300

300

200

200

100

100

40

50

60

70

80

90

40

50

60

70

80

90

Figure 11: Scatter plots of a data set from Histone3
and IRE with d = 6 (axes are ﬁrst two attributes). In(a), circle points belong to Histone3, and triangles
to IRE, and (b) is a clustering result obtained by
K-means.
Table 3: Results (adjusted Rand index) of clustering
for two families IRE and Histone3.
d=1
2
3
4
5
6
K-means
DBSCAN

0.54
0.14

0.54
0.14

0.56
0.75

0.58
0.78

0.62
0.67

0.59
0.64

1994.
[7] L. Hubert and P. Arabie. Comparing partitions.
Journal of Classiﬁcation, 2(1):193–218, 1985.
[8] Y. Karklin, R. F. Meraz, and S. R. Holbrook.
Classiﬁcation of non-coding RNA using graphrepresentations of secondary structure. In Proceedingsof Paciﬁc Symposium on Biocomputing, volume 10,
pages 4 – 15, 2004.
[9] D. Meyer. Support Vector Machines: The interface tolibsvm in package e1071, 2010.
[10] R Development Core Team. R: A Language andEnvironment for Statistical Computing. R Foundationfor Statistical Computing, 2010.
[11] Y. Sakakibara, M. Brown, R. Hughey, I. Mian,
K. Sjölander, R. C. Underwood, and D. Haussler.
Stochastic context-free grammers for tRNA modeling.
Nucleic Acids Research, 22(23):5112, 1994.
[12] Y. Tabei, K. Tsuda, T. Kin, and K. Asai. SCARNA:
fast and accurate structural alignment of RNA
sequences by matching ﬁxed-length stem fragments.
Bioinformatics, 22(14):1723, 2006.
[13] J. P. Vert. Classiﬁcation of biological sequences withkernel methods. In Y. Sakakibara, S. Kobayashi,
K. Sato, T. Nishino, and E. Tomita, editors,
Grammatical Inference: Algorithms and Applications,volume 4201 of Lecture Notes in Computer Science,
pages 7–18. Springer, 2006.
[14] J. T. Wang and X. Wu. Kernel design for RNA
classiﬁcation using support vector machines.
International Journal of Data Mining andBioinformatics, 1(1):57 – 76, 2006.