Mining Spatial Association Rules for Composite Motif Discovery - Mathematical Approaches to Polymer Sequence Analysis and Related Problems - page 97

Fig. 5.2 A three-level hierarchy defined on motifs

reference to the sequence described in ( 5.2 ), it is possible to define a three-level
hierarchy H 1 (Fig. 5.2 ), where the top level represents a generic single motif, the
middle level represents distinct single motifs in M and the lowest level represents
specific occurrences of motifs. In this example, the function 1 simply maps the

root to 1, x, y,and z to 2 and m 1 , m 2 and m 3 to 3.
The set of predicates used in SPADA can be categorized into four classes. The
key predicate identifies the reference objects in S (e.g., sequence is the key predicate
in description ( 5.2 )). The property predicates are binary predicates which define
the value taken by an attribute of an object (e.g., length of a motif, not reported
in description ( 5.2 )). The structural predicates are binary predicates which relate
task-relevant objects (e.g., distance ) as well as reference objects with task-relevant
objects (e.g., part of ). The is a predicate is a binary taxonomic predicate which
associates a task-relevant object with a value of some H k .
The units of analysis DŒs, one for each reference object s 2 S, are subsets of
ground facts in D E , defined as follows:
DŒs D is a.R.s// [ DŒs j R.s/ [ [
r i 2R.s/

DŒr i j R.s/; (5.6)

where:

R.s/ is the set of task-relevant objects directly or indirectly related to s;

is a.R.s// is the set of is a atoms specified for each r i 2 R.s/;
DŒs j R.s/ contains both properties of s and relations between s and some
r i 2 R.s/;
DŒr i j R.s/ contains both properties of r i and relations between r i and some

r j 2 R.s/.
This notion of unit of analysis is coherent with the individual-centered represen-
tation [ 7 ], which has some nice properties, both theoretical (e.g., PAC-learnability
[ 49 ]) and computational (e.g., smaller hypothesis space and more efficient search).
The set of units of analysis is a partitioning of D E into a number of subsets DŒs,
each of which includes ground atoms concerning the task-relevant objects (transi-
tively) related to the reference object s. With reference to the sequence described
in ( 5.2 ), R.t 2 / Df m 1 ;m 2 ;m 3 g ,andDŒt 2 coincides with the whole set of ground