An Algorithm for Finding the Largest Approximately Common Substructures of Two Trees.
AbstractOrdered, labeled trees are trees in which each node has a label and the left-to-right order of its children (if it has any) is fixed. Such trees have many applications in vision, pattern recognition, molecular biology and natural language processing. We consider a substructure of an ordered labeled tree T to be a connected subgraph of T. Given two ordered labeled trees and an integer d, the largest approximately common substructure problem is to find a substructure U1 of T1 and a substructure U2 of T2 such that U1 is within edit distance d of U2 and where there does not exist any other substructure V1 of T1 and V2 of T2 such that V1 and V2 satisfy the distance constraint and the sum of the sizes of V1 and V2 is greater than the sum of the sizes of U1 and U2. We present a dynamic programming algorithm to solve this problem, which runs as fast as the fastest known algorithm for computing the edit distance of two trees when the distance allowed in the common substructures is a constant independent of the input trees. To demonstrate the utility of our algorithm, we discuss its application to discovering motifs in multiple RNA secondary structures (which are ordered labeled trees).
Introduction
Ordered, labeled trees are trees in which each node has a label and the left-to-right order of its children (if
it has any) is fixed. 1 Such trees have many applications in vision, pattern recognition, molecular biology
and natural language processing, including the representation of images [12], patterns [2, 10] and secondary
structures of RNA [14]. They are frequently used in other disciplines as well.
A large amount of work has been performed for comparing two trees based on various distance measures
recently generalized one of the most commonly used distance measures, namely
the edit distance, for both rooted and unrooted unordered trees. These works laid out a foundation that
is useful for comparing graphs [15, 24].
In this paper we extend the previous work by considering the largest approximately common sub-structure
problem for ordered labeled trees. Various biologists [5, 14] represent RNA secondary structures
as trees. Finding common patterns (also known as motifs) in these secondary structures helps both in
predicting RNA folding [5] and in functional studies of RNA processing mechanisms [14].
Previous methods for detecting motifs in the RNA molecules (trees) are based on one of the following
two approaches: (1) transforming the trees to sequences and then using sequence algorithms [13]; (2)
representing the molecules using a highly simplified tree structure and then searching for common nodes
in the trees [5]. Neither of the two approaches satisfactorily takes the full tree structure into account. By
contrast, utilizing the proposed algorithm for pairs of trees enables one to locate tree-structured motifs
occurring in multiple RNA secondary structures. Our experimental results concerning RNA classification
show the significance of these motifs [23].
Preliminaries
2.1 Edit Distance and Mappings
We use the edit distance [17] to measure the dissimilarity of two trees. There are three types of edit
operations, i.e., relabeling, delete, and insert a node. Relabeling node n means changing the label on n.
Deleting a node n means making the children of n become the children of the parent of n and removing n.
Insert is the inverse of delete. Inserting node n as the child of node n 0 makes n the parent of a consecutive
subsequence of the current children of n 0 . Fig. 1 illustrates the edit operations. For the purpose of this
work, we assume that all edit operations have a unit cost. The edit distance, or simply the distance, from
tree T 1 to tree T 2 , denoted is the cost of a minimum cost sequence of edit operations transforming
to T 2
[17].
The notion of edit distance is best illustrated through the concept of mappings. A mapping is a
graphical specification of which edit operations apply to each node in the two trees. For example, the
mapping in Fig. 2 shows a way to transform T 1 to T 2 . The transformation includes deleting the two nodes
labeled a and m in T 1
and inserting them into T 2
1 Throughout the paper, we shall refer to ordered labeled trees simply as trees when no ambiguity occurs.
a c
r
a b
r
r
r
a f c
r
r
f
e
f
f
Fig. 1. (i) Relabeling: To change one node label (a) to another (b). (ii) Delete: To delete a node;
all children of the deleted node (labeled b) become children of the parent (labeled r). (iii) Insert:
To insert a node; a consecutive sequence of siblings among the children of the node labeled r (here,
f and the left g) become the children of the newly inserted node labeled b.
r
a m
b c d e pT
r
a m
b c d e pT
Fig. 2. A mapping from tree T1 to tree T2 .
We use a postorder numbering of nodes in the trees. Let t[i] represent the node of T whose position in
the left-to-right postorder traversal of T is i. When there is no confusion, we also use t[i] to represent the
label of node t[i]. Formally, a mapping from T 1
to T 2
is a triple (M;
simply M if the context is
clear), where M is any set of ordered pairs of integers (i;
(ii) For any pair of (i
(one-to-one
is
to the left of t 1
] is to the left of t 2
preservation
is an
ancestor of t 1 is an ancestor of t 2 [j 2 ] (ancestor order preservation condition). The cost of M is
the cost of deleting nodes of T 1
not touched by a mapping line plus the cost of inserting nodes of T 2
not
touched by a mapping line plus the cost of relabeling nodes in those pairs related by mapping lines with
different labels. It can be proved [17] that ffi(T 1
equals the cost of a minimum cost mapping from tree
T 1 to tree T 2 .
2.2 Cut Operations
We define a substructure U of tree T to be a connected subgraph of T . That is, U is rooted at a node n
in T and is generated by cutting off some subtrees in the subtree rooted at n. Formally, let T [i] represent
the subtree rooted at t[i]. The operation of cutting at node t[i] means removing T [i]. A set S of nodes of
T [k] is said to be a set of consistent subtree cuts in T [k] if (i) t[i] 2 S implies that t[i] is a node in T [k],
and (ii) t[i]; t[j] 2 S implies that neither is an ancestor of the other in T [k]. Intuitively, S is the set of all
roots of the removed subtrees in T [k].
We use Cut(T ; S) to represent the tree T with subtree removals at all nodes in S. Let Subtrees(T )
be the set of all possible sets of consistent subtree cuts in T . Given two trees T 1
and T 2
and an integer
d, the size of the largest approximately common root-containing substructures within distance
[i] and T 2
[j], denoted fi(T 1
[j]; (or simply fi(i; j; when the context is
clear), is maxfjCut(T 1
)jg subject to ffi(Cut(T 1
[j]). Finding the largest approximately common substructure (LACS),
within distance d, of T 1
[i] and T 2
[j] amounts to calculating max 1-u-i;1-v-j ffi(T 1
[v]; d)g and locating
the Cut(T 1
[v]) that achieve the
maximum size. The size of LACS, within distance d, of T 1
and T 2
is
d)g.
We shall focus on computing the maximum size. By memorizing the size information during the computation
and by a simple backtracking technique, one can find both the maximum size and one of the
corresponding substructure pairs yielding the size in the same time and space complexity.
3 Our Algorithm
3.1 Notation
We use desc(i) to represent the set of postorder numbers of the descendants of the node t[i] and l(i)
denotes the postorder number of the leftmost leaf of the subtree T [i]. When T [i] is a leaf,
is an ordered forest of tree T induced by the nodes numbered i to j inclusive (see Fig. 3). If i ? j, then
;. The definition of mappings for ordered forests is the same as for trees. Let F 1
and F 2
be two
forests. The distance from F 1 to F 2 , denoted \Delta(F 1 the cost of a minimum cost mapping from
to F 2
[25].
set S of nodes of F is said to be a set of consistent subtree cuts in F if (i) t[p] 2 S
implies that i - p - j, and (ii) t[p]; t[q] 2 S implies that neither is an ancestor of the other in F . We
use Cut(F; S) to represent the sub-forest F with subtree removals at all nodes in S. Let Subtrees(F )
be the set of all possible sets of consistent subtree cuts in F . Define the size of the largest approximately
common root-containing substructures, within distance k, of F 1
and F 2
, denoted \Psi(F 1
; k), to
be subject to \Delta(C ut(F 1
[l(i)::s] and F 2
[l(j)::t], we also represent
there is no confusion.
[10]
[3]
[5] [6]
[8]
[6]
[3]
Fig. 3. An induced ordered forest.
3.2 Basic Properties
Lemma 3.1. Suppose s 2 desc(i) and t 2 desc(j). Then
Proof. Immediate from definitions.
Lemma 3.2. Suppose s 2 desc(i) and t 2 desc(j). Then for all k, 1 - k - d,
ae \Psi(T 1
ae \Psi(;; T 2
Proof. (i) follows from the definition. For (ii), suppose
[l(i)::s]) is a smallest set of
consistent subtree cuts that maximizes jCut(T 1
)j where \Delta(Cut(T 1
of the following two cases must hold: (1) t 1
. If (1) is true, then \Psi(T 1
[l(i)::s], ;,
1. (iii) is proved
similarly as for (ii).
Lemma 3.3. Suppose s 2 desc(i) and t 2 desc(j). If (l(s) 6= l(i) or l(t) 6= l(j)), then
Proof. Suppose
[l(i)::s]) and S 2 2 Subtrees(T 2
[l(j)::t]) are two smallest sets of consistent
subtree cuts that maximize jCut(T 1
)j where \Delta(C ut(T 1
at least one of the following cases must hold:
Case 1. t 1
(i.e., the subtree T 1
[s] is removed). So, \Psi(l(i)::s; l(j)::t;
Case 2. t 2
(i.e., the subtree T 2
[t] is removed). So, \Psi(l(i)::s; l(j)::t;
Case 3. t 1
and t 2
[t]
(i.e., neither T 1
[t] is removed) (Fig. 4). Let M be the
mapping (with cost 0) from Cut(T 1
) to Cut(T 2
In M , T 1
[s] must be mapped to
[t] because otherwise we cannot have distance zero between Cut(T 1
Therefore \Psi(l(i)::s; l(j)::t;
Since these three cases exhaust all possible mappings yielding \Psi(l(i)::s; l(j)::t; 0), we take the maximum
of the corresponding sizes, which gives the formula asserted by the lemma.
Fig. 4. Illustration of the case in which one of T1 [l(i)::s] and T2 [l(j)::t] is a forest and neither
nor T2 [t] is removed.
Lemma 3.4. Suppose s 2 desc(i) and t 2 desc(j). Suppose both T 1
[l(j)::t] are trees (i.e.,
Proof. Since
[t]. First, consider the
case where t 1 are two smallest sets of
consistent subtree cuts that maximize jCut(T 1
)j where ffi(Cut(T 1
[t],
M be the mapping (with cost 0) from Cut(T 1 Fig. 5). Clearly,
in M , t 1
[s] must be mapped to t 2
[t]. Furthermore, the largest common root-containing substructure of
must be the largest common root-containing substructure
of T 1 [s] and T 2 [t]. This means that \Psi(l(i)::s; l(j)::t; 2, where the 2 is
obtained by including the two nodes t 1
[t].
Next consider the case where t 1 [s] 6= t 2 [t] (i.e., the roots of the two trees T 1 [s] and T 2 [t] differ). In
order to get distance zero between the two trees after applying cut operations to them, we have to remove
both trees entirely. Thus, \Psi(l(i)::s; l(j)::t;
Fig. 5. Illustration of the case in which both T1 [l(i)::s] and T2 [l(j)::t] are trees and t1
Lemma 3.5. Suppose s 2 desc(i) and t 2 desc(j). If (l(s) 6= l(i) or l(t) 6= l(j)), then for all k, 1 - k - d,
Proof. Suppose are two smallest sets of consistent
subtree cuts that maximize jCut(T 1
)j where \Delta(C ut(T 1
k. Then at least one of the following cases must hold:
Case 1. t 1
. So, \Psi(l(i)::s; l(j)::t;
Case 2.
Case 3. t 1
and t 2
[t]
. Let M be a minimum cost mapping from Cut(T 1
) to
There are three subcases to examine:
[s] is not touched by a line in M . Then, \Psi(l(i)::s; l(j)::t;
(b) t 2 [t] is not touched by a line in M . Then, \Psi(l(i)::s; l(j)::t;
are both touched by lines in M . Then (s; . So, there exists an h
such that \Psi(l(i)::s; l(j)::t; h). The value of h ranges
from 0 to k. Therefore we take the maximum of the corresponding sizes, i.e., \Psi(l(i)::s; l(j)::t;
h)g.
Lemma 3.6. Suppose s 2 desc(i) and t 2 desc(j). Suppose both T 1 [l(i)::s] and T 2 [l(j)::t] are trees
(i.e.,
where
ae
Proof. Since
[l(j)::t] are trees, T 1
[t]. We first show that
removing either T 1
[s] or T 2
[t] would not yield the maximum size. There are three cases to be considered:
Case 1. Both T 1
are removed. Then, \Psi(l(i)::s; l(j)::t; cutting
at just the children of t 1
[t] would cause \Psi(l(i)::s; l(j)::t; 2. Therefore removing both T 1
and T 2
cannot yield the maximum size.
Case 2. Only T 1
[s] is removed. Then, \Psi(l(i)::s; l(j)::t;
[t]; k). Assume without loss of
generality that jT 2
k. The above equation implies that we have to remove some subtrees from T 2
so that there are no more than k nodes left in T 2
[t]. Thus, \Psi(l(i)::s; l(j)::t;
On the
other hand, if we just cut at the children of t 1
[s] and leave t 1
[s] in the tree, we would map t 1
[s] to t 2
[t].
This would lead to \Psi(l(i)::s; l(j)::t;
1. Thus, removing T 1
alone
cannot yield the maximum size.
Case 3. Only T 2
[t] is removed. The proof is similar to that in Case 2.
The above arguments lead to the conclusion that in order to obtain the maximum size, neither T 1
nor
[t] can be removed. Now suppose
[s]) and S 2 2 Subtrees(T 2
[t]) are two smallest
sets of consistent subtree cuts that maximize jCut(T 1
)j where ffi(Cut(T 1
be a minimum cost mapping from Cut(T 1
) to Cut(T 2
). Then at
least one of the following cases must hold:
Case 1. t 1
[s] is not touched by a line in M . So, \Psi(l(i)::s; l(j)::t;
Case 2. t 2
[t] is not touched by a line in M . So, \Psi(l(i)::s; l(j)::t;
Case 3. Both t 1
are touched by lines in M . By the ancestor order preservation and sibling
order preservation conditions on mappings (cf. Section 2.1), (s; t) must be in M . Thus, if t 1
[t], we
have \Psi(l(i)::s; l(j)::t; mapping t 1
[s] to t 2
costs 1,
we have \Psi(l(i)::s; l(j)::t; 2.
3.3 The Algorithm
From Lemma 3.4 and Lemma 3.6, we observe that when s is on the path from l(i) to i and t is on
the path from l(j) to j, we need not compute fi(s; t; k), 0 - k - d, separately, since they can be
obtained during the computation of fi(i; j; k). Thus, we will only consider nodes that are either the
roots of the trees or having a left sibling. Let keynodes(T ) contain all such nodes of a tree T , i.e.,
? k such that
)g. For each
Fig. 6 computes fi(s; t;
Procedure Find-Largest-2 in Fig. 6 computes fi(s; t; d. The main algorithm is summarized
in Fig. 6.
Now, to calculate the size of the largest approximately common substructures (LACSs), within distance
d, of T 1
[i] and T 2
[j], we build, in a bottom-up fashion, another array fl(i;
using fi(i; j; d) as follows. Let are the postorder numbers of the
children of t 1
[i] or
[i] is a leaf. Let
are the postorder
numbers of the children of t 2 [j] or Rg. The
size of LACSs, within distance d, of T 1
[i] and T 2
[j] is fl(i; j; d). The size of LACSs, within distance d, of
Consider the complexity of the algorithm. We use an array to hold \Psi, fi and fl, respectively. These
arrays require O(d \Theta jT 1 j \Theta jT 2 space. Regarding the time complexity, given fi(i;
calculating fl(i; j; d) requires O(jT 1 j \Theta jT 2 time. For a fixed i and j, Procedure Find-Largest-
the total time is bounded by
O(
[i]j \Theta jT 2
[i]j \Theta
From [25, Theorem 2], the last term above is bounded by O(d 2 \Theta jT 1 j \Theta jT 2 j \Theta min(H 1
is the height of T i
and L i
is the number of leaves in T i
. When d is a constant, this
is the same as the complexity of the best current algorithm for tree matching based on the edit distance
[11, 25], even though the problem at hand appears to be harder than tree matching.
Note that to calculate max 1-i-jT1 j;1-j-jT2 j ffi(i; j; 0)g, one could use a faster algorithm that runs in
time O(jT 1 j \Theta jT 2 j). However, the reason for considering the keynodes and the formulas as specified in
Lemmas 3.3 and 3.4 is to prepare the optimal sizes from forests to forests and store these size values in the
array to be used in calculating fi(s; t; could incorporate the faster algorithm into
the Find-Largest algorithm, the overall time complexity would not be changed, because the calculation of
fi(s; t; dominates the cost.
4 Implementation and Discussion
We have applied our algorithm to find motifs in multiple RNA secondary structures. In this experiment, we
examined three phylogenetically related families of mRNA sequences chosen from GenBank [1] pertaining
to the poliovirus, human rhinovirus and coxsackievirus. Each family contained two sequences, as shown
in

Table

1.
Algorithm Find-Largest
Input: Trees T 1
and an integer d.
Output: fi(i; j;
:= 1 to jkeynodes(T1)j do
:= 1 to jkeynodes(T2)j do
begin
run Procedure Find-Largest-1 on input (i; j; 0);
run Procedure Find-Largest-2 on input (i; j; d);
Procedure Find-Largest-1
Input:
Output: fi(s; t;
for s := l(i) to i do
for t := l(j) to j do
for s := l(i) to i do
for t := l(j) to j do
if (l(s) 6= l(i) or l(t) 6= l(j)) then
compute \Psi(l(i)::s; l(j)::t; 0) as in Lemma 3.3;
else begin /*
compute \Psi(l(i)::s; l(j)::t; 0) as in Lemma 3.4;
fi(s; t;
Procedure Find-Largest-2
Input:
Output: fi(s; t;
for k := 1 to d do
for k := 1 to d do
for s := l(i) to i do
compute \Psi(T 1 [l(i)::s]; ;; k) as in Lemma 3.2 (ii);
for k := 1 to d do
for t := l(j) to j do
compute \Psi(;; T2 [l(j)::t]; k) as in Lemma 3.2 (iii);
for k := 1 to d do
for s := l(i) to i do
for t := l(j) to j do
if (l(s) 6= l(i) or l(t) 6= l(j)) then
compute \Psi(l(i)::s; l(j)::t; k) as in Lemma 3.5;
else begin /*
compute \Psi(l(i)::s; l(j)::t; k) as in Lemma 3.6;
fi(s; t;
Fig. 6. Algorithm for computing fi(i; j; k).
Family Sequence # of trees File #
poliovirus polio3 sabin strain 3,026 file 1
pol3mut 3,000 file 2
human rhinovirus rhino 2 3,000 file 3
coxsackievirus cox5 3,000 file 5

Table

1. Data used in the experiment.
Under physiological conditions, i.e., at or above the room temperature, these RNA molecules do not
take on only a single structure. They may change their conformation between structures with similar free
energies or be trapped in local minima. Thus, one has to consider not only the optimal structure but all
structures within a certain range of free energies. On the other hand, a loose rule of thumb is that the
"real" structure of an RNA molecule appears in the top 5% - 10% of suboptimal structures of the sequence
based on the ranking of their energies with the minimum energy one (i.e. the optimal one) being at the
top. Therefore, we folded the 5' non-coding region of the selected mRNA sequences and collected (roughly)
the top 3,000 suboptimal structures for each sequence. We then transformed these suboptimal structures
into trees using the algorithms described in [13, 14]. Fig. 7 illustrates an RNA secondary structure and
its tree representation.
The structure is decomposed into five terms: stem, hairpin, bulge, internal loop and multi-branch loop
[14]. In the tree, H represents hairpin nodes, I represents internal loops, B represents bulge loops, M
represents multi-branch loops, R represents helical stem regions (shown as connecting arcs) and N is a
special node used to make sure the tree is connected. The tree is considered to be an ordered one where
the ordering is imposed based upon the 5' to 3' nature of the molecule. The resulting trees for each mRNA
sequence selected from GenBank were stored in a separate file, where the trees had between 70 and 180
nodes (cf. Table 1). Each tree is represented by a fully parenthesized notation where the root of every
subtree precedes all the nodes contained in the subtree. Thus, for example, the tree depicted in Fig. 7(ii)
is represented as (N(R(I(R(M(R(B(R(M(R(H))(R(H))))))(R(H))))))).
For each pair of trees T 1
in a file, we ran the algorithm Find-Largest on T 1
, finding the size of
the largest approximately common substructures, within distance 1, for each subtree pair T 1
[i] and T 2
[j],
locating one of the corresponding substructure pairs yielding the size.
These substructures constituted candidate motifs. Then we calculated the occurrence number 2 of each
candidate motif M by adding variable length don't cares (VLDCs) to M as the new root and leaves to
form a VLDC pattern V and then comparing V with each tree T in the file using the pattern matching
technique developed in [26]. (conventionally denoted by " ") can be matched, at no cost, with
a path or portion of a path in T . The technique calculates the minimum distance between V and T after
implicitly computing an optimal substitution for the VLDCs in V , allowing zero or more cuttings at nodes
from T (see Fig. 8).) This way we can locate the motifs approximately occurring in all (or the majority
2 The occurrence number of a motif M with respect to distance k refers to the number of trees of the file in which M
approximately occurs (i.e. these trees approximately contain M) within distance k.
of) the trees in the file. 3U A
U
A
A
A U
G C
A
U
U
A
A
U
A
U
G
U
A
U
A
A
A
U
U A
G
G
A
A
G
A
G
G
G
G
U
U
G
U
U
G
A C C
G
U
A
G
A
U A
U
GU
U
A A
U
U
I
A
A A G C A A G U U C A U U U C G C C A U U A A GFig. 7. Illustration of a typical RNA secondary structure and its tree representation. (i)
Normal polygonal representation of the structure. (ii) Tree representation of the structure.

Table

2 summarizes the results where the motifs occur within distance 0 in at least 350 trees in the
corresponding file. The table shows the number of motifs discovered for each sequence, the number of
distinct motifs found in common between both sequences of each family, and the minimum and maximum
sizes of these common motifs. Table 3 shows some big motifs found in common in all the three families
and the number of each sequence's secondary structures that contain the motifs. These motifs serve as a
starting point to conduct further study of common motif analysis [3, 22].
3 One can speed up this method by encoding the candidate motifs into a suffix tree and then using the statistical sampling
and optimization techniques described in [23] to find the motifs.
a
r
a
b d

Fig. 8. Matching a VLDC pattern V and a tree T (both the pattern and tree are hypothetical
ones solely used for illustration purposes). The root   in V would be matched
with nodes and the two leaves   in V would be matched with nodes
in T , respectively. Nodes would be cut. The distance of V and T would be
1 (representing the cost of changing c in V to d in T ).
Family Sequence # of motifs found # of common motifs min size max size
poliovirus polio3 sabin strain 836 347 3 101
pol3mut 793
rhinovirus rhino 2 287
coxsackievirus cox5 306 136 3 20
cvb305pr 391

Table

2. Statistics concerning motifs discovered from the secondary structures of the mRNA sequences used in
the experiment.
Motifs found polio3 pol3mut rhino 2 rhino 14 cox 5 cvb305pr
(R(B(R(B(R(B(R))))))) 2,272 1,822 3,000 2,252 2,997 2,979

Table

3. Motifs found in common in the secondary structures of the poliovirus, human rhinovirus and coxsack-
ievirus sequences. The motifs are represented in a fully parenthesized notation where the root of every subtree
precedes all the nodes contained in the subtree. For each motif, the table also shows the number of each sequence's
suboptimal structures that contain the motif.
The proposed algorithm and the discovered motifs have also been applied to RNA classification successfully
[23]. Our experimental results showed that one can get more intersections of motifs from sequences
of the same family. This indicates that closeness in motif corresponds to closeness in family. Another
application of our algorithm is to apply it to a tree T and itself and calculate fi(i; j;
This allows one to find repeatedly occurring substructures (or repeats for short) in T . Finding repeats in
secondary structures across different RNA sequences may help understand the structures of RNA. Readers
interested in obtaining these programs may send a written request to any one of the authors.
Our work is based on the edit distance originated in [17]. This metric is more permissive than other
worthy metrics (e.g. [18, 19, 20]) and therefore helps to locate subtle motifs existing in RNA secondary
structures. The algorithm presented here assumes a unit cost for all edit operations. In practice, a more
refined non-unit cost function can reflect more subtle differences in the RNA secondary structures [14]. It
would then be interesting to score the measures in detecting common substructures or repeats in trees.
Another interesting problem is to find a largest consensus motif T 3 in two input trees T 1 and T 2 where T 3
is a largest tree such that each of T 1
and T 2
has a substructure that is within a given distance to T 3
. A
comparison of the different types of common substructures (see also [6, 7, 8]), probably based on different
metrics (e.g. [18, 19, 20]), as well as their applications remains to be explored.

Acknowledgments

We wish to thank the anonymous reviewers for their constructive suggestions and pointers to some relevant
papers. We also thank Wojcieok Kasprzak (National Cancer Institute), Nat Goodman (Whitehead
Institute of MIT) and Chia-Yo Chang for their useful comments and implementation efforts. This work
was supported by the National Science Foundation under Grants IRI-9224601, IRI-9224602, IRI-9531548,
IRI-9531554, and by the Natural Sciences and Engineering Research Council of Canada under Grant
OGP0046373.



--R

Nucleic Acids Research
Waveform correlation by tree matching.
Secondary structure computer prediction of the polio virus 5
Alignment of trees - An alternative to tree edit
RNA secondary struc- tures: Comparison and determination of frequently recurring substructures by consensus
A largest common similar substructure problem for trees embedded in a plane.
Largest common similar substructures of rooted and unordered trees.
The largest common similar substructure problem.

A tree system approach for fingerprint pattern recognition.
A unified view on tree metrics.
Distance transform for images represented by quadtrees.
An algorithm for comparing multiple RNA secondary structures.
Comparing multiple RNA secondary structures using tree comparisons.
Structural descriptions and inexact matching.
Exact and approximate algorithms for unordered tree matching.
The tree-to-tree correction problem
The metric between rooted and ordered trees based on strongly structure preserving mapping and its computing method.
A metric between unrooted and unordered trees and its bottom-up computing method
"A metric on trees and its computing method."
The tree-to-tree editing problem
The cardiovirulent phenotype of coxsackievirus B3 is determined at a single site in the genomic 5
Automated discovery of active motifs in multiple RNA secondary structures.
An algorithm for graph optimal monomorphism.
Simple fast algorithms for the editing distance between trees and related problems.
Approximate tree matching in the presence of variable length don't cares.
On the editing distance between undirected acyclic graphs.
--TR

--CTR
Roger Keays , Andry Rakotonirainy, Context-oriented programming, Proceedings of the 3rd ACM international workshop on Data engineering for wireless and mobile access, September 19-19, 2003, San Diego, CA, USA
M. Vilares , F. J. Ribadas , J. Graa, Approximately common patterns in shared-forests, Proceedings of the tenth international conference on Information and knowledge management, October 05-10, 2001, Atlanta, Georgia, USA
Rolf Backofen , Sven Siebert, Fast detection of common sequence structure patterns in RNAs, Journal of Discrete Algorithms, v.5 n.2, p.212-228, June, 2007
S. Bhowmick , Wee Keong Ng , Sanjay Madria, Constraint-driven join processing in a web warehouse, Data & Knowledge Engineering, v.45 n.1, p.33-78, April
D. C. Reis , P. B. Golgher , A. S. Silva , A. F. Laender, Automatic web news extraction using tree edit distance, Proceedings of the 13th international conference on World Wide Web, May 17-20, 2004, New York, NY, USA
Ada Ouangraoua , Pascal Ferraro , Laurent Tichit , Serge Dulucq, Local similarity between quotiented ordered trees, Journal of Discrete Algorithms, v.5 n.1, p.23-35, March, 2007
Thomas Kmpke, Distance Patterns in Structural Similarity, The Journal of Machine Learning Research, 7, p.2065-2086, 12/1/2006
N. Bourbakis , P. Yuan , S. Makrogiannis, Object recognition using wavelets, L-G graphs and synthesis of regions, Pattern Recognition, v.40 n.7, p.2077-2096, July, 2007
S. Bhowmick , Sanjay Kumar Madria , Wee Keong Ng, Detecting and Representing Relevant Web Deltas in WHOWEDA, IEEE Transactions on Knowledge and Data Engineering, v.15 n.2, p.423-441, February
Dmitriy Bespalov , Ali Shokoufandeh , William C. Regli , Wei Sun, Scale-space representation of 3D models and topological matching, Proceedings of the eighth ACM symposium on Solid modeling and applications, June 16-20, 2003, Seattle, Washington, USA
Jiang , Andreas Munger , Horst Bunke, On Median Graphs: Properties, Algorithms, and Applications, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.23 n.10, p.1144-1151, October 2001
Yanhong Zhai , Bing Liu, Web data extraction based on partial tree alignment, Proceedings of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan
Jun Huan , Wei Wang , Deepak Bandyopadhyay , Jack Snoeyink , Jan Prins , Alexander Tropsha, Mining protein family specific residue packing patterns from protein structure graphs, Proceedings of the eighth annual international conference on Resaerch in computational molecular biology, p.308-315, March 27-31, 2004, San Diego, California, USA
trees;pattern recognition;dynamic programming;pattern matching;computational biology