A Data Structure for Circular String Analysis and Visualization.
A csdawg for circular strings, which is obtained by making simple modifications to the compact symmetric directed acyclic word graph (csdawg) for linear strings, is proposed. This data structure does not contain extraneous vertices and, consequently, avoids the disadvantages of previous methods. Using this method, algorithms which make use of the csdawg for linear strings can then be extended to circular strings with trivial modifications. The extended algorithms continue to have the same time and space complexities. Moreover, the extensions take the form of postprocessing or preprocessing steps which are simple to add on to a system built for linear strings, particularly in an object-oriented language.
Introduction
The circular string data type is used to represent a number of objects such as circular
genomes, polygons, and closed curves. Research in molecular biology involves the identification
of recurring patterns in data and hypothesizing about their causes and/or effects
[1, 2]. Research in pattern recognition and computer vision involves detecting similarities
within an object or between objects [3].
Detecting patterns visually is tedious and prone to error. In [4], a model was proposed
to alleviate this problem. The model consists of identifying all recurring patterns in a string
and highlighting identical patterns in the same color.
[4] also listed a number of queries that the model would support. In [5], efficient (mostly
optimal) algorithms were proposed for some of these queries for linear strings. These algorithms
perform operations and traversals on the symmetric compact directed acyclic word
graph (scdawg) [6] of the linear string. The scdawg, which is used to represent a string or a
set of strings, evolved from other string data structures such as position trees, suffix trees,
directed acyclic word graphs, etc [7, 8, 9, 10].
One approach for extending these techniques to circular strings is to arbitrarily break
the circular string at some point so that it becomes a linear string. Techniques for linear
strings may then be applied to it. However, this has the disadvantage that some significant
patterns in the circular string may be lost because the patterns were broken when linearizing
the string. Indeed, this would defeat the purpose of representing objects by circular strings.
[3] defined a polygon structure graph, which is an extension of suffix trees to circular
strings. However, the suffix tree is not as powerful as the scdawg and cannot be used to
solve some of the problems that the scdawg can solve. In this paper, we define an scdawg
for circular strings. Algorithms in [5] and [6] which make use of the scdawg for linear strings
can then be extended to circular strings with minor modifications. The extended algorithms
continue to have the same efficient time and space complexities. Further, the extensions
take the form of postprocessing or preprocessing steps which are simple to add on to a
system built for linear strings, particularly in an object oriented language.
e
c
a
d
c
a

Figure

1: Circular string
Section 2 contains definitions. Section 3 describes the scdawg for linear strings while
Section 4 describes its extension to circular strings. Section 5 deals with the computation
of occurrences of displayable entities. Section 6 introduces the notion of conflicts and
Section 7 lists other queries that are to be implemented. Section 6 also explains how the
algorithms implementing queries for linear strings can be modified so that they work with
circular strings. Finally, Section 8 mentions some applications for the visualization and
analysis of circular strings.
Let s denote a circular string of size n consisting of characters from a fixed alphabet, \Sigma,
of constant size. Figure 1 shows an example circular string of size 8. We shall represent a
circular string by a linear string enclosed in angle brackets "!?" (this distinguishes it from
a linear string) . The linear string is obtained by traversing the circular string in clockwise
order and listing each element as it is traversed. The starting point of the traversal is chosen
arbitrarily. Consequently, there are up to n equivalent representations of s. In the example,
s could be represented as !abcdabce?, !bcdabcea?, etc.
We characterize the relationship between circular strings and linear strings by defining
the functions, linearize and circularize. linearize maps circular strings to linear strings. It
is a one-many mapping as a circular string can, in general, be mapped to more than one
linear string. For example, dabcg. We will assume,
for the purpose of this paper, that linearize arbitrarily chooses one of the linear strings; for
convenience we assume that it chooses the representation obtained by removing the angle
brackets "!?". So, linearize(!abcd?) = abcd. circularize maps linear strings to circular
strings. It is a many-one function and represents the inverse of linearize.
We use lower case letters to represent circular strings and upper case letters to represent
linear strings. Further, if a lower case letter (say, s) is used to represent a particular circular
string, then the corresponding upper case letter (S) is assumed to be linearize(s). A single
character in s or S occurring in the i th position is denoted by s i or S i , respectively. A
substring of S is denoted by S i;j where i - j. S substring of s is denoted
by s i;j , where s j. For example, if
We use the symbol, fl, to
denote either a circular string or a linear string. In the example,
The predecessor, pred(fl,i,j) of a substring fl i;j of fl is defined as
linear
The successor, succ(fl,i,j) of a substring fl i;j of fl is defined as
and fl is linear
and fl is circular
The immediate context, context(fl,i,j) of a substring fl i;j of fl is the ordered pair
The predecessor, pred(fl; ff), and successor, succ(fl; ff), sets of a pattern, ff, in a string fl
are defined as below:
pred(fl; g. succ(fl; g.
The immediate context set, context(fl,ff) of a pattern, ff, in fl is the set
g.
In the example string of Figure 1, succ(s;
A pattern occurring in fl is said to be maximal iff its occurrences are not all preceded
by the same character nor all followed by the same character. So, a pattern ff of length !
n in fl is maximal iff jpred(fl; ff)j - 2 and jsucc(fl; ff)j - 2. This is not necessarily true for
patterns of length greater than or equal to n. For example, S is maximal in S (since it is
neither preceded nor followed by a character), but jpred(S;
A pattern is said to be a displayable entity (or displayable) of fl iff it is maximal and
occurs at least twice in fl. Note that if fl represents a circular string, then a pattern can
be arbitrarily long. In the rest of our discussion, we will assume that displayable entities of
circular strings have length less than n.
3 Scdawgs For Linear Strings
An scdawg, corresponding to a string S is a directed acyclic
graph defined by a set of vertices, V (S), a set, R(S), of labeled directed edges called right
extension (re) edges, and a set of labeled directed edges, L(S) called left extension (le)
edges. Each vertex of V (S) represents a substring of S. Specifically, V (S) consists of a
source (which represents the empty word, -), a sink (which represents S), and a vertex
corresponding to each displayable entity of S.
Let de(v) denote the string represented by vertex, v, v ffl V (S). Define the implication,
imp(S; ff), of a string, ff of S to be the smallest superword of ff in fde(v)j v ffl V (S)g, if
such a superword exists. Otherwise, imp(S; ff) does not exist. Re edges from v 1 (v
are obtained as follows: for each letter, x, in \Sigma, if imp(S; de(v 1 )x) exists and is equal to
there is an re edge from v 1 to v 2 with label xfl. If fi is the empty
string, then the edge is known as a prefix extension edge. Le edges from v 1 (v are
obtained as follows: for each letter, x, in \Sigma, if imp(S; xde(v 1 exists and is equal to de(v 2
gabcde
de
e
de
c
abc
bc
de
gabcde
fabcgabcde
gabcde
fabcgabcde
cde
sink
abc
c
source

Figure

2: SCDAWG for re edges are shown
there is an le edge from v 1 to v 2 with label flx. If fi is the empty string, then
the edge is known as a suffix extension edge. Figure 2 shows (V (S),R(S)) corresponding
to cde, and c are the displayable entities of S. There are two re
edges from the vertex representing abc. These correspond to g. imp(S,abcd)
Consequently, both edges are incident on the sink. There are no edges
corresponding to the other letters of the alphabet as imp(S,abcx) does not exist for x ffl
fg.
Notice that the number of re edges from a vertex, v, equals jsucc(S; de(v)) - f1gj and
the number of le edges equals jpred(S; de(v)) - f1gj. In the example,
So, the number of right edges leaving the vertex corresponding to it is 1.
The space required for SCD(S) is O(n) and the time needed to construct it is O(n) [7, 6].
While we have defined the scdawg data structure for a single string, it can be extended to
represent a set of strings [6].
4 Extension to Circular Strings
In Section 4.1, we present a constructive definition of an scdawg for circular strings. Section
4.2 analyzes the complexity of the algorithm of Section 4.1 to construct the scdawg of
a circular string and Section 4.3 identifies and proves some properties of this scdawg.
4.1 SCDAWGs For Circular Strings
The notion of an scdawg may be extended to circular strings. The scdawg for circular
strings is defined constructively by the algorithm of Figure 3. The scdawg for the circular
string s is obtained by first constructing the scdawg for the linear string
that linearize(s)). A bit is associated with each re edge in R(T ) indicating whether it
is a prefix extension edge or not. Similarly, a bit is associated with each le edge in L(T )
to identify suffix extension edges. Two pointers, a suffix pointer and a prefix pointer are
associated with each vertex, v in V (T ). The suffix (prefix) pointer points to a vertex, w,
in V (T ) such that de(w) is the largest suffix (prefix) of de(v) represented by any vertex
in V (T ). Suffix (prefix) pointers are the reverse of suffix (prefix) extension edges and are
derived from them. Figure 4 shows SCD(T cabcbab. The broken
edge from vertex c to vertex abc is a suffix extension edge, while the solid edge from vertex
ab to vertex abc is a prefix extension edge.
Next, in step 2, suffix and prefix redundant vertices of SCD(T ) are identified. A suffix
(prefix) redundant vertex is a vertex v that satisfies the following properties:
(a) v has exactly one outgoing re (le) edge.
A vertex is said to be redundant if it is either prefix redundant or suffix redundant or both.
In

Figure

4, vertex c is prefix redundant only, while vertex ab is suffix redundant only. No
other vertices in the figure are redundant (in particular, the vertex representing S is not
redundant even though it has one re and one le out edge as n). The fact that step 2
does, in fact, identify all redundant vertices is established later.
Vertices of SCD(T ) are processed in reverse topological order in step 3 and redundant
Algorithm A
Step1: Construct SCD(T ) for
fIdentify Suffix Redundant Verticesg
while v 6= source do
begin
if v has exactly one outgoing re edge
then
then mark v suffix redundant;
else
exit Step 2(a);
fIdentify Prefix Redundant verticesg
fSimilar to Step 2 (a)g
Step3:
while (v !? source) do
begin
case v of
suffix redundant but not prefix redundant: ProcessSuffixRedundant(v);
prefix redundant but not suffix redundant: ProcessPrefixRedundant(v);
suffix redundant and prefix redundant : ProcessBothRedundant(v);
not redundant : fDo nothing

Figure

3: Algorithm for constructing the scdawg for a circular string
T=S.S
c
cabcbab
cabcbab
cabcb
abcbab
c
bab
cabcb
c
a
c
ab
cabc
abcbab
bab
ab
c
c
a
ab
c
abc
ab

Figure

4: SCD(T ) for T=cabcbabcabcbab
Procedure ProcessSuffixRedundant(v)
1. Eliminate all left extension edges leaving v (there are at least two of these).
2. There is exactly one right extension edge, e, leaving v. Let the vertex that it leads to
be w. Let the label on the right extension edge be xfl. Delete the edge.
3. All right edges incident on v are updated so that they point to w. Their labels are
modified so that they represent the concatenation of their original labels with xfl.
4. All left edges incident on v are updated so that they point to w. Their labels are not
modified. However, if any of these were suffix extension edges, the bit which indicates
this should be reset as these edges are no longer suffix extension edges.
5. Delete v.

Figure

5: Algorithm for processing a vertex which is suffix redundant
vertices are eliminated. When a vertex is eliminated, the edges incident to/from it are
redirected and relabeled as described in Figures 5 to 10. The resulting graph is CSCD(s).
The set of vertices of CSCD(s) is denoted by CV (s). The set of right (left) edges of
is denoted by CR(s) (CL(s)). Figure 11 shows CSCD(s) for
Notice that vertices c and ab have been eliminated and that the two incoming edges to c
and the three incoming edges to ab of Figure 4 now point to abc.
uL
uR
uR uL
U s
U s

Figure

Procedure ProcessPrefixRedundant(v)
1. Eliminate all right extension edges leaving v (there are at least two of these).
2. There is exactly one left extension edge, e, leaving v. Let the vertex that it leads to
be w. Let the label on the left extension edge be flx. Delete the edge.
3. All left edges incident on v are updated so that they point to w. Their labels are
modified so that they represent the concatenation of flx with their original labels.
4. All right edges incident on v are updated so that they point to w. Their labels are not
modified. However, if any of these were prefix extension edges, the bit which indicates
this should be reset as these edges are no longer prefix extension edges.
5. Delete v.

Figure

7: Algorithm for processing a vertex which is prefix redundant
uL
uR
uR uL
U s
U s

Figure

8: v is prefix redundant
Procedure ProcessBothRedundant(v)
1. There is exactly one right extension edge, e 1 , leaving v. Let the vertex that it leads
to be w 1 . Let the label on the edge be xfl. Delete the edge.
2. There is exactly one left extension edge, e 2 , leaving v. Let the vertex that it leads to
be w 2 . Let the label on the edge be flx. Delete the edge.
fWe establish later that w 1 and w 2 are, in fact, the same vertex.g
3. All right edges incident on v are updated so that they point to w 1 . Their labels are
modified so that they represent the concatenation with xfl. If any of these edges were
prefix edges, the bit which indicates this should be reset.
4. Similarly, left edges incident on v are updated so that they point to w 2 . Their labels
are modified so that they represent the concatenation with flx. If any of these edges
were suffix extension edges, the bit which indicates this should be reset.
5. Delete v.

Figure

9: Algorithm for processing a vertex which is prefix and suffix redundant
e L (l L fiy)
e R (l R xfl)
e L (l L )
uL
uR
uR uL
U s
U s

Figure

10: v is suffix and prefix redundant
Lemma 1 For every substring s i;j of length ! n of s, there exists a substring, T l;m (= s i;j ),
of T such that context(T ;
Proof
Case
Case
Subcase
context(s;
Subcase
Subcase
possible since the length of s
Corollary 1 For every pattern, ff, of length ! n in s, context(s; ff) ' context(T ; ff).
Corollary 2 For every pattern, ff, of length ! n in s, pred(s; ff) ' pred(T ; ff) and succ(s; ff)
be a substring of T . If i 6= 1, then there is a substring s l;m (=T i;j ) of s
such that pred(s; l; m)
Proof If the result follows from the definition of pred(T ; choose s l;m
so that
the length of T i;j is greater than n, s l;m is assumed to wrap around once). So, pred(s; l; m)
Corollary 3 For every pattern, ff, of length ! n in T , pred(T
Theorem 1 For every pattern ff of length less than n, pred(s;
Proof From Corollary 2 we have pred(s; ff) ' pred(T ; ff). So, pred(s; ff) - f1g '
pred(T ; ff) - f1g and hence pred(s; ff) ' pred(T ; ff) - f1g (since pred(s; ff) does not contain
cabc
ab
T=S.S
source
abcbab
cabcb
cabcbab
cabcbab
bab
c
a
c
c
abc
a
abc
abc

Figure

11: Scdawg for
1). From Corollary 3 we have pred(s; ff) ' pred(T ; ff) - f1g. So, pred(s;
f1g. The proof that succ(s;
Theorem 2 A vertex, v with jde(v)j ! n in V (T ) is non redundant iff de(v) is a displayable
entity of s.
Proof Suppose ff is a displayable entity of s. Then, we have jpred(s; ff)j - 2 and jsucc(s; ff)j
2. From Theorem 1 we have jpred(T 2. So, ff
is a displayable entity in T and the corresponding vertex in V (T ) has at least two le and
two re edges leaving it. Hence, v is not redundant.
Next, suppose there is a non redundant vertex, v, in SCD(T ) with
de(v). Since v is not redundant, jpred(T 2. From
Theorem 1 we have jpred(s; ff)j - 2 and jsucc(s; ff)j - 2. So, ff is a displayable entity of s.Corollary 4 A redundant vertex in V (T ) is not a displayable entity of s.
Lemma 3 (a) A vertex, v, in V (T ) will have exactly one re (le) out edge only if de(v) is
a suffix (prefix) of T .
(b) If a vertex, v, such that de(v) (jde(v)j ! n) is a suffix (prefix) of T has more than one
re (le) out edge, then no vertex, w, such that de(w) is a suffix (prefix) of de(v) can be suffix
(prefix) redundant.
Proof (a) Suppose de(v) is not a suffix of T . Then 1 is not an element of succ(T ; de(v)).
2. So, v has at least two re out edges, which
is a contradiction. Hence, de(v) must be a suffix of T .
(b) Since de(w) is a suffix of de(v), a successor of de(v) must also be a successor of de(w). So,
(de(v) has at least two re out edges). So, w must have at least two re out edges
and cannot be suffix redundant. 2
We can now show that step 2(a) of Algorithm A identifies all suffix redundant vertices in
it is sufficient to examine vertices corresponding to suffixes of T (Lemma 3(a)),
step 2(a) follows the chain of suffix pointers starting from the sink. If a vertex on this chain
representing a displayable entity of length ! n has one re out edge, then it is marked suffix
redundant. The traversal of the chain terminates either when the source is reached or a
vertex with more than one re out edge is encountered (Lemma 3(b)). Similarly, step 2(b)
identifies all prefix redundant vertices in V (T ).
4.2 Complexity Analysis
will in the worst case traverse all the vertices in SCD(T )
spending O(1) time at each. The number of vertices is bounded by O(n) [6]. So, step 2
takes O(n) time. Step 3 traverses SCD(T ). Each vertex is processed once; each edge is
processed at most twice (once when it is an incoming edge to the vertex being currently
processed, and once when it is the out edge from the vertex currently being processed. So,
Step 3 takes O(n) time (note that SCD(T ) has O(n) edges).
4.3 Properties of CSCD(s)
Define the implication, imp(s; ff), of a string, ff, with respect to CSCD(s) to be the smallest
superword, fifffl, of ff represented by a vertex in CV (s), such that there does not exist a
substring fi 1 fffl 1 of T where the length of the least common suffix,
is less than min(jfij; or the length of the least common prefix, lcp(fl;
is less than min(jflj; jfl 1 j), if such a superword exists. Otherwise, imp(s; ff) does not exist.
The additional condition (which is referred to as the uniqueness condition) that is imposed
on imp(s; ff) is guaranteed for imp(T ; ff) by the definition of SCD(T ).
be the smallest set of superword displayable entities
of abc in s such that any superword displayable entity of abc in s is a superword of an
element of R. Then, de(s; abc) must be one of the elements of R. We have jlcs(b;
abc) is neither babcaa nor cabcaa. Further, since jlcs(aaaa; aa)j
abcaaaa.
Lemma 4 Let v be a suffix and prefix redundant vertex in SCDINT (T ), where SCDINT (T )
represents an intermediate configuration between SCD(T ) and CSCD(s) just after the while
statement in Step 3 of Algorithm A. Let the le and re out edges be incident on w 1 and w 2
respectively, where de(w 1
are not redundant, then w
Proof Case 1. jde(w 1
cannot be nil (if it is, then w 1 is prefix redundant since jde(w 1 )j ! n and all occurrences
of de(v) except the prefix of S are preceded by y). Similarly, must be
of the form fi 3 yde(v)xfl 1 , since y is the only letter that precedes de(v). Similarly, de(w 2 )
must be of the form fi 2 yde(v)xfl 3 . We now show that fi Assume that
this is not the case. Since jde(w 1 are not redundant,
are all at least 2.
So, there must exist a displayable entity, fi m yde(v)xfl m , of s where fi m is the largest common
suffix of fi 3 and fi 2 and fl m is the largest common prefix of fl 1 and fl 3 . Further, fi
de(v)
de(v)
de(v)
de(v)642S

Figure

12: Illustration of proof of prefix/suffix redundancy invariant
imp(s; yde(v)), which contradicts statements made above.
Case 2. jde(w 1 )j - n,
cannot be nil, otherwise w 2 is suffix redundant. So, de(w 2 as x is the
only letter that follows de(v). Arguments similar to those in Case 1 show that since jde(w 2 )j
must be a prefix of fl 3 and fi 1 a suffix of fi 2 y. But, then
a contradiction. Hence, Case 2 cannot exist.
Case 3. jde(w 2 )j - n,
Similar to Case 2.
Case 4. jde(w 2 )j - n,

Figure

12 shows that for this case to occur,
this the prefix/suffix redundancy invariant. The figure assumes that jde(w 1
de(v) is a prefix of de(w 1 ), and that jde(v)j ! n=2 and divides n. However, the prefix/suffix
redundancy invariant can be shown to be true in all other cases. Two copies of T are shown
in the figure. The first copy shades the occurrence (n of de(v) and its
ff 2m
ff
Vertices
Other
ff
ff
ff
ff
ff
ff
ff
ff
ff

Figure

13: SCD(ff 2m )
extension to de(w 1 ). The second shades the occurrence (n+1; n+ jde(v)j) and its extension
to de(w 1 ). Since the shaded regions in both strings represent
Next, we assume without loss of generality that there is no fi such that
Call this the smallest repetition assumption.
The only occurrences of ff in T are at ((1; jffj); (jffj+1; 2jffj); :::; ((m \Gamma 1)ff+1; 2n)) (if not,
an argument similar to the one of Figure 12 contradicts the smallest repetition assumption).
takes the form of Figure 13. Each vertex representing ff
exactly one le and one re out edge as shown.
All remaining displayable entities of T are subwords of ff 2 and are of size less than jffj
(if not, an argument identical to the one in Figure 12 contradicts the smallest repetition
assumption). The vertices representing these displayable entities are represented by the box
in

Figure

13.
None of the vertices in the box has out edges incident on vertices representing the displayable
entities g. In particular, no out edges from the vertices in the box
are incident on vertices representing displayable entities of length greater than n. After
2m ) has been processed by Algorithm A, all incoming edges to vertices corresponding
to ff and ff 2 in SCD(ff 2m ) are incident on the vertex corresponding to
CSCD(ff 2m ). It follows that any prefix and suffix redundant vertex in SCD(ff 2m ), when
processed by Step 3 of Algorithm A can have both edges incident on w 1 and w 2 such that
are at least n only if de(w 1
properties P1, P2, and P3 stated below (Theorem 3). These properties
ensure that the algorithms of [5] can be extended to circular strings.
consists of a source and a sink. For each v of CV (s) that is not the source or
sink, the following are true:
(a) jde(v)j ! n iff de(v) is a displayable entity of s.
(b) if jde(v)j - n, then de(v) is a displayable entity of T .
There exists an re out edge corresponding to letter x in \Sigma from vertex v 1 in CV (s) to
vertex exists and is equal to de(v 2 ). If de(v 2
then the label on the re edge is xfl. If then the edge is a prefix extension edge.
3: Similar to P2 but for le edges.
Theorem 3 CSCD(s) satisfies P1, P2, and P3.
Proof Property P1 is established by the knowledge that SCD(T ) contains all displayable
entities of T and that Algorithm A only eliminates those displayable entities of T of length
less than n, which are not displayable entities of s (Corollary 4).
P2 and P3 are proved by induction. The induction hypothesis is:
Let U s be the subset of U T that remains after the vertex set U T ' V (T ) has been processed
by step 3 of Algorithm A.
Let RUs be the set of re edges which are incident on vertices in U s . For any re edge r ffl
RUs from vertex u to w with label xfl, imp(s;
condition holds for le edges.
(II) For each vertex u in U s [ there is an re out edge corresponding to each
letter x in succ(T ; incident on a vertex in U s [
condition holds for le edges.
When U by definition. So, R CV
establishes that these edges are incident on the correct vertices and that their labels are
correct. (II) establishes that CR(s) is complete. So P2 holds. Similarly, P3 holds.
Induction Base: U fg. RUs and LUs are empty so (I) does not apply. (II) is
established from the definition of SCD(T ).
Induction Step: Consider vertex, v (v ffl V (T )), which is about to be processed by step 3
of algorithm A. Let U 0
T and U 0
s denote U T and U s respectively after v has been processed.
We must show that (I) and (II) hold for U 0
s and U 0
T . Since the vertices are processed in
reverse topological order, all out edges from v are incident on vertices in U s and are therefore
elements of RUs or LUs . So, they must satisfy (I).
Case 1: v is not redundant. U 0
since v is not eliminated.
We must show that (I) is true for incoming edges to v as these are the only additions to
RUs and LUs . I.e., R U 0
s
fincoming right edges to vg, L U 0
s
fincoming left
edges to vg.
Let e be an re edge with label xfl from u to v. From the definition of SCD(T ), we have
is the smallest superword
of de(u)x in fde(w)jw ffl V (T )g. Since CV
(s)g. But,
this is true since v ffl CV (s). So,
symmetric argument can be made for incoming le edges to v.
The letter of the alphabet to which an re (le) out edge corresponds is the first (last)
character in its label. Since no out edges are added, deleted, or redirected and the labels
of all out edges are unchanged, each vertex has an re/le out edge corresponding to the
same letter of the alphabet as it had prior to processing vertex v. So, (II) holds (induction
hypothesis).
Case 2: v is redundant. U 0
since v is eliminated.
Subcase (a): v is suffix redundant only. By definition, v consists of a single re
out edge, e, to a vertex w in U s . Let label(e) = xfl. From the induction hypothesis,
imp(s; first establish that (i)
(ii) de(v) is a prefix of de(w).
imp(s; de(v)) 6= de(v) as v is redundant. So, imp(s; de(v)) must correspond to a vertex
on which one of the out edges from v is incident, since there is an out edge corresponding
to each element in pred(s; de(v)) [ succ(s; de(v)) (from (II)). The single re edge is incident
on w, which represents imp(s; de(v)x). The left out edges from v are incident on vertices
which represent imp(s; x i de(v)) for 2. From the definition of
imp(s; de(v)), none of these vertices can possibly represent imp(s; de(v)). For instance, if
imp(s; x i de(v)) is imp(s; de(v)), then the string, imp(s; x j de(v)), i 6= j, would invalidate
the definition.
So, imp(s; de(v)) must be de(w). However, for this to be true, we must show that
nil and therefore that de(v) is a prefix of de(w). All occurrences of de(v) in s are followed
by x. So, jpred(T 2. An argument
similar to the one in the previous paragraph shows that for imp(s; de(v)x) to exist,
We have RU 0
s
re out edge from vg fincoming re edges to vg and LU 0
s
out edges from vg fincoming le edges to vg. (I) and (II) do not apply to the
edges deleted from RUs and LUs . So, we only need to prove (I) and (II) for incoming edges
to v.
Let e R be an re edge incident on v from vertex uR with label yfl 1 so that
must be redirected to imp(s; de(u R )y) for (I) to
hold. imp(T ; de(u R de(v) is the smallest superword of de(u R )y in fde(a)j a ffl V (T )g.
imp(s; de(u R )y) is the smallest superword of de(u R )y that satisfies the uniqueness condition
in fde(a)j a ffl CV (s)g ' fde(a)j a ffl V (T )g. Since v
imp(s; de(u R )y) is the
smallest superword of de(v) that satisfies the uniqueness condition in fde(a)j a ffl CV (s)g.
imp(s; de(u R xfl. The updated re edge, e R ,
is incident on w and has label yfl 1 xfl which was obtained in step 3 of Algorithm A by concatenating
continues to be a prefix extension
edge. e R satisfies (I).
Let e L be an le edge incident on v from uL so that
z). Using the same argument that was used for e R , we have imp(s; zde(u L
is redirected to w and its label remains unchanged. Clearly,
e L is no longer a suffix edge even if fi
Notice that (II) continues to be satisfied as each out edge corresponding to any vertex
in U 0
continues to be associated with the same character (in particular,
label(e R ) continues to begin with y and label(e L ) continues to end with z); and each out
edge continues to leave the same vertex (in particular, e R continues to leave uR , e L continues
to leave uL ).
Subcase (b): v is prefix redundant only. Symmetric to subcase (a).
Subcase (c): v is prefix and suffix redundant. So, v has one re out edge, e 1 , to
vertex w 1 in CV (s). Let label(e 1 Also, v has one le out edge, e 2 , to vertex w 2 in
y.
From the induction hypothesis, de(w 1
imp(s;
The conditions for Lemma 4 are satisfied since w 1 and w 2 are not redundant (otherwise
they would have been eliminated). Thus, de(w 1 imp(s; de(v)) can
either be imp(s; de(v)x) or imp(s; yde(v)). But, both these expressions are equal to de(w).
So, imp(s;
The proof that (I) and (II) are satisfied is similar to that for subcase (a). Note, however,
that any incoming prefix/suffix extension edges to v will no longer remain prefix/suffix
extension edges as xfl and fiy are not nil. 2
Computing Occurrences of Displayable Entities
Procedure LinearOccurrences(S; v) of Figure 14, which is based on the outline in [6], reports
the end position of each occurrence of de(v), v ffl V (S), in the linear string S . However,
invoking LinearOccurrences(T; v), v ffl CV (s), does not immediately yield all occurrences
of de(v) in T . In Section 5.1 we present a modification which obtains all occurrences of
displayable entities of s. In Section 5.2 we show that this modification is correct and that
its time complexity is optimal.
5.1 Algorithm
An auxiliary boolean array , reported[1.n], is used in conjunction with CSCD(s). Initially,
all elements of this array are set to false. Procedure CircOccurrences(s; v) of Figure 15
computes the end positions of each de(v) (v ffl CV (s)) in s. LinearOccurrences(T; v) of
line 1 will not necessarily compute all occurrences of de(v) in T , since it is being executed
on CSCD(s) and not on SCD(T ). Note, also, that an occurrence of de(v) ending at
position i (i - n) in T has an identical occurrence ending at position n
occurrences correspond to the same occurrence of de(v) in s. So,
reports both occurrences, then only the single corresponding
occurrence of de(v) in s must eventually be reported.
Lines 4-7 transform the occurrence l, if necessary, so that it represents a value between
1 and n. If this occurrence has not already been listed, then it is added to the list of
occurrences and the corresponding element of reported is set to true. If the occurrence has
been listed then it is a duplicate (lines 8-12). After all occurrences have been computed,
all elements of reported are reset to false (lines 14,15) so that reported can subsequently be
reused to compute the occurrences of some other displayable entity in s.
In the example of Figure 11, LinearOccurrences(T ; v), where v represents abc, does report
the end positions of all occurrences of abc in T (i.e., 4, 8, and 11). Lines 2 to 12 transform
this into the list of end positions of abc in s (i.e., 1 and 4) corresponding to s 6;1 and s 2;4
respectively.

Figure

shows the de(v)'s, de(w)'s, and de(x)'s for a hypothetical string

Figure

shows some fragments of its scdawg. v is suffix redundant in SCD(T ) and its
single re out edge is incident on w. There is an re edge from x to v and x is not redundant.
By construction, the re edge from x to v in SCD(T ) becomes an re edge from x to w
in CSCD(s). Procedure LinearOccurrences(T; x), x in CSCD(s) will fail to yield the
rightmost occurrence of de(x) in T , since that occurrence is neither a subword of de(w)
Procedure LinearOccurrences(S:string, v:vertex)
fObtain all occurrences of de(v), v ffl V (S), in Sg
Procedure Occurrences(S:linear string, v:vertex, i:integer)
begin
if de(v) is a suffix of S
for each re out edge, e, from v in SCD(S) do
begin
let w be the vertex on which e is incident;

Figure

14: Obtaining all occurrences of a displayable entity in a linear string
Procedure CircOccurrences(s:circular string, v:vertex)
fv is a vertex in CSCD(s)g
2 for each reported occurrence l of de(v) do
6 else
8 if not reported[k] then
9 begin
add k to final list of occurrences
14 for each occurrence, l, of de(v) in s do

Figure

15: Obtaining all occurrences of a displayable entity in a circular string
de(v)
de(w)

Figure

Example string
nor a suffix of T . In the next section, we show that CircOccurrences(s; x) computes all
occurrences of de(x) in s in spite of the fact that LinearOccurrences(T; v) does not compute
all occurrences of de(x) in T .
5.2 Proof of Correctness
substring of T . Assume that T i;j is not a suffix of T
define the immediate
right extension IRE(SCD(T ); T i;j ) of T i;j in SCD(T ) to be the occurrence T i\Gammajfij;j+jflj+1 of
displayable entity, y.
(s), be a substring of T . Assume that T i;j is not a suffix of
define the immediate
right extension IRE(CSCD(s);T i;j ) of T i;j in CSCD(s) to be the occurrence T i\Gammajfij;j+jflj+1
of displayable entity, y.
So, if in Figure 16,
which is the occurrence of de(v) corresponding to the suffix of T . However,
which does not represent a valid
substring of T .
ff

Figure

17: Fragments of scdawgs corresponding to Figure 16
IRE(DAWG; IRE
An occurrence T said to be Right Retrievable (RR) in SCD(T )
iff one of the following is true:
RR in SCD(T ).
Similarly, an occurrence T is said to be Right Retrievable (RR) in
iff one of the following is true:
RR in CSCD(s).
defined for any occurrence, T
i;j is not RR in CSCD(s) only if (i) IRE(CSCD(s);T i;j ) does not represent
a substring of T or (ii)IRE(CSCD(s); T i;j ) is a valid substring of T , but is not RR in
CSCD(s).
In the example of Figure 16, T 2n\Gammajde(x)ffj+1;2n\Gammajffj is RR in SCD(T ), but not RR in
CSCD(s).
Notice that (i is not a substring of T iff
Lemma 5 For k - 1, if IRE
substrings of T and if (i
then
Proof Assume that there exists a pair of substrings
and
of T , such that
are assuming that their IRE's are defined).
By symmetry, both occurrences represent the same displayable entity (say, de(v)). Further,
), then from the definition
of IRE, we have n. Applying this argument repeatedly
proves the lemma 2
Lemma 6 The RR occurrences of de(v), v in V (T ) (CV (s)) in SCD(T ) (CSCD(s)) are
exactly those occurrences of de(v) which are obtained by LinearOccurrences(T ,v).
Proof Follows from the definition of RR occurrences. 2
Corollary 5 All occurrences of a pattern de(v) (v ffl V (T )) in T are obtained by LinearOccurrences(T ; v).
Lemma 7 All occurrences of de(v) in T , v ffl CV (s), where jde(v)j - n are obtained by
Proof This follows from Corollary 5 and the construction of CSCD(s) in which no right
out edges from vertices representing displayable entities of size - n were modified.
are RR in CSCD(s).
Proof Assume that the lemma is false and that there exists an occurrence, T i;j , of de(v)
with which is not RR in CSCD(s).
Clearly, j 6= 2n, otherwise T i;j would be RR in CSCD(s). Let last denote the smallest
value of k for which IRE k (CSCD(s); T i;j ) is not a substring of T . Such a last - 1 must
exist since T i;j is not RR. Let (i last ; j last ) denote IRE last (CSCD(s); T i;j ) . Let z be the
vertex in CV (s) to which T i last ;j last
corresponds.
Case 1. last
last ! 2n. Consider the string T 1;j last
in T . Its length is greater than n. If there
were two occurrences of this string in T , then it would be a displayable entity of length ? n
(because (i) T i;j last
does not have a predecessor and (ii) de(z) is maximal and its occurrences
are not all followed by the same letter). A vertex corresponding to this displayable entity
would not have been eliminated by Algorithm A since its length would be - n and T 1;j last
would be RR in CSCD(s) (Lemma 7). So, there must exist only one occurrence of the
string represented by T i;j last
. But, this string is a proper suffix of de(z) which means that
one of its occurrences is preceded by a character. So, there are two occurrences of this
string. This leads to a contradiction.
Case 2. last ? 2n
The proof is similar to the one for Case 1. 2
Lemma 9 At least one of the two occurrences, T i;j and T i+n;j+n , of de(v),
ffl CV (s), with is RR in CSCD(s).
Proof Assume that the lemma is false. Let last be the smallest value of k for which either
not a substring of T . Let (i
last (CSCD(s); T i;j ) and (i q last (CSCD(s); T i+n;j+n ).
Case 1. IRE last (CSCD(s); T i;j ) is not a substring of T; IRE last (CSCD(s); T i+n;j+n ) is a
substring of T.
I.e, RR in CSCD(s),
since (i q ; j q ) satisfies the conditions of Lemma 8.
Case 2. IRE last (CSCD(s); T i;j ) is a substring of T ; IRE last (CSCD(s); T i+n;j+n ) is not a
substring of T .
Symmetric to Case 1.
Case 3. IRE last (CSCD(s); T i;j ) is not a substring of T ; IRE last (CSCD(s); T i+n;j+n ) is
not a substring of T .
5). This is shown to cause a
contradiction by an argument similar to the one in Lemma 8. 2
Theorem 4 Procedure CircOccurrences(s,v) correctly obtains all occurrences of de(v) in s
shows that LinearOccurrences(T; v) computes all RR occurrences of de(v)
in CSCD(s). Lemmas 8 and 9 show that each occurrence of de(v) in s has at least one
corresponding occurrence in T , which is RR in CSCD(s). CircOccurrences computes these
occurrences in T and transforms them so that they represent occurrences in s, removing
duplicates if any. So, the output is a list of all occurrences of de(v) in s. 2
Theorem 5 Procedure CircOccurrences is optimal.
Proof Procedure CircOccurrences(s; v) takes O(jocc(T ; v)j) time, where jocc(T ; v)j is the
number of occurrences of de(v) in T . Each for loop takes O(jocc(T ; v)j) time.
is the number of occurrences of de(v) in
s. So, the complexity is O(jocc(s; v)j). jocc(s; v)j is the size of the output, so the algorithm
is optimal. 2
6 Computing Conflicts Efficiently
[4] defines the concept of conflicts and explains its importance in the analysis and visualization
of strings. Formally,
(i) A subword conflict between two displayable entities, D 1 and D 2 , in S exists iff D 1 is a
substring of D 2 .
(ii) A prefix-suffix conflict between two displayable entities, D 1 and D 2 , in S exists iff there
exist substrings, S s in S such that S p SmS s occurs in S and S p
. The string, Sm is known as the intersection of the conflict; the conflict is said to
occur between D 1 and D 2 with respect to Sm .
[4] also identified a number of problems relating to the computation of conflicts in a linear
string, while [5] presented efficient algorithms for most of these problems (some of which
are listed in the next section). These algorithms typically involve sophisticated traversals
or operations on the scdawg for linear strings. Our extension of scdawgs to circular strings
makes it possible to use the same algorithms to solve the corresponding problems for circular
strings with some minor modifications which are outlined below.
There are conceptually two kinds of traversals that the algorithms of [5] perform on an
scdawg corresponding to a linear string:
(i) Traversal of displayable entities of the string. In these traversals, a vertex is traversed
specifically because it represents a displayable entity of the string.
(ii) Incidental traversals. In these traversals, a vertex is not traversed because it is a
displayable entity, but because it performs some other function. For example, this includes
vertices traversed by LinearOccurrences(T; v).
Traversals of type (i) in CSCD(s) are not required to traverse vertices which represent
displayable entities of size greater than or equal to n. This may be achieved simply by
disabling edges in CSCD(s) which leave a vertex representing a displayable entity of size
less than n and are incident on a vertex representing a displayable entity of size greater
than or equal to n. Traversals of type (ii), however, may be required to traverse vertices
representing displayable entities of size greater than or equal to n. This is achieved by
associating a bit for each edge which is set to 1 if it represents an edge from a vertex whose
displayable entity is of size less than n to a vertex whose displayable entity is of size greater
than or equal to n. Otherwise, it is set to 0. Type (i) traversals check the bit, while type
(ii) traversals ignore it.
Finally, all calls to LinearOccurrences are replaced by calls to CircOccurrences.
7 Other Queries
In this section, we list queries that a system for the visualization and analysis of circular
strings would support. [5] contains algorithms for these same queries for linear strings. In
the previous section, we showed how these algorithms could be modified to support these
queries.
Size Restricted Queries: Experimental data show that random strings contain a large
number of displayable entities whose lengths are small. In most applications, small displayable
entities are uninteresting. Hence, it is useful to list only those displayable entities
whose lengths are greater than some integer, k. Similarly, it is useful to report exactly those
conflicts in which the conflicting displayable entities have length greater than k. This gives
rise to the following problems:
(1) List all occurrences of displayable entities whose length is greater than k.
(2) Compute all prefix suffix conflicts involving displayable entities of length greater than
k.
(3) Compute all subword conflicts involving displayable entities of length greater than k.
An alternative formulation of the problem which also seeks to achieve the goal outlined
above is based on reporting only those conflicts whose size is greater than k. The size of a
conflict is defined below:
The overlap of a conflict is defined as the string common to the conflicting displayable
entities. The overlap of a subword conflict is the subword displayable entity. The overlap of
a prefix-suffix conflict is its intersection. The size of a conflict is the length of the overlap.
This formulation of the problem is particularly relevant when the conflicts are of more
interest than the displayable entities. It also ensures that all conflicting displayable entities
reported have size greater than k. We have the following problems:
(4) Obtain all prefix-suffix conflicts of size greater than some integer k.
(5) Obtain all subword conflicts of size greater than some integer k.
Pattern Restricted Queries: These queries are useful in applications where the fact
that two patterns have a conflict is more important than the number or location of the
conflicts. The following problems arise as a result:
List all pairs of displayable entities which have subword conflicts.
List all triplets of displayable entities (D 1 ,D 2 ,Dm ) such that there is a prefix suffix
conflict between D 1 and D 2 with respect to Dm .
Same as 6, but size restricted as in 5.
Same as 7, but size restricted as in 4.
Statistical Queries: These queries are useful when conclusions are to be drawn from
the data based on statistical facts.
(10) For each pair of displayable entities, D 1 and D 2 , involved in a subword conflict (D 1
is the subword of D 2 ), obtain (number of occurrences of D 1 which occur as
subwords of D 2 )=(number of occurrences of D 1 ).
(11) For each pair of displayable entities, D 1 and D 2 , involved in a prefix-suffix conflict,
(number of occurrences of D 1 which have prefix-suffix conflicts with
/(number of occurrences of D 1 ).
greater than a statistically determined threshold, then the following
could be be said with some confidence: Presence of D 1 implies presence of D 2 .
Applications
Circular strings may be used to represent circular genomes [1] such as G4 and OEX174. The
detection and analysis of patterns in genomes helps to provide insights into the evolution,
structure, and function of organisms. [1] analyzes G4 and OEX174 by linearizing and then
constructing their scdawg. Our work improves upon [1] by :
(i) analyzing circular strings without risking the "loss" of patterns.
(ii) extending the analysis and visualization techniques of [5] for linear strings to circular
strings.
Circular strings in the form of chain codes are also used to represent closed curves in
computer vision [11]. The objects of Figure 18(a) are represented in chain code as follows:
(1) Arbitrarily choose a pixel through which the curve passes. In the diagram, the starting
pixels for the chain code representation of objects 1 and 2 are marked by arrows.
(2) Traverse the curve in the clockwise direction. At each move from one pixel to the next,
the direction of the move is recorded according to the convention shown in Figure 18(b).
Objects 1 and 2 are represented by 1122102243244666666666 and 666666661122002242242446
respectively. The alphabet is f0, 1, 2, 3, 4, 5, 6, 7g which is fixed and of constant size (8) and
therefore satisfies the condition of Section 2. We may now use the visualization techniques of
[5] to compare the two objects. For example, our methods would show that objects 1 and 2
share the segments S1 and S2 (Figure 18(c)) corresponding to 0224 and 2446666666661122
respectively. Information on other common segments would also be available. The techniques
of this paper make it possible to detect all patterns irrespective of the starting pixels
chosen for the two objects.
Circular strings may also be used to represent polygons in computer graphics and computational
geometry [3]. Figure 19 shows a polygon which is represented by the following
alternating sequence of lines and angles: bfiaffeffeffcficfiefiaffeffeffcficfibffcffdffcff, where ff
denotes a 90 degree angle and fi, a 270 degree angle.
The techniques of this paper would point out all instances of self similarity in the polygon,
such as affeffeffcfic. Note, however, that for the methods to work efficiently, the number of
lines and angles that are used to represent the polygons must be small and fixed.
9 Conclusions
In this paper, we have defined the scdawg for circular strings and shown how it can be used
to solve problems in the visualization and analysis of patterns in circular strings. We expect
that it can also be used for other string matching applications involving circular strings.
An important feature of the scdawg for circular strings is that it is easy to implement and
use when corresponding techniques for scdawgs for linear strings are already available.
(c)
(b)
(a) Starting position for object 2
Starting position for object 16420
Chain code representations of directions

Figure

Representing closed curves by circular strings
e
d
c c
c
c
c
c
e
e
a
a

Figure

19: Representing polygons by circular strings

Acknowledgement

We are grateful to Professor Gerhard Ritter for pointing out the application of circular
strings to the representation of closed curves.



--R

"Sequence Landscapes,"
"The Matching of Protein Sequences using Color Intrasequence Homology Displays,"
"A method for detecting structure in polygons,"
"String Visualization,"
"Computing Display Conflicts in String Visualization,"
"Complete Inverted Files for Efficient Text Retrieval and Analysis,"
"The Smallest Automaton Recognizing the Subwords of a Text,"
"Efficient on-line construction and correction of position trees,"
"A space-economical suffix tree construction algorithm,"
"Efficient and elegant subword tree construction,"
Processing, 2nd Edition.
--TR
Digital image processing (2nd ed.)
Complete inverted files for efficient text retrieval and analysis
The matching of protein sequences using color intrasequence homology displays
Computer graphics: principles and practice (2nd ed.)
Models and techniques for the visualization of labeled discrete objects
A Space-Economical Suffix Tree Construction Algorithm

--CTR
D. P. Mehta , S. Sahni, Computing Display Conflicts in String Visualization, IEEE Transactions on Computers, v.43 n.3, p.350-361, March 1994
space complexities;data structure;linear strings;computational geometry;visualization;circular string analysis;compact symmetric directed acyclic word graph;time complexity;data structures;data visualisation;object-oriented language;computational complexity;directed graphs