Computing Display Conflicts in String Visualization.
Strings are used to represent a variety of objects such as DNA sequences, text, and numerical sequences. A model for a system for the visualization and analysis of strings was proposed by D. Mehta and S. Sahni (1992). The problem of display conflicts that arise in this model was identified and methods to overcome it were suggested. These methods require the computation of display conflicts. We present efficient algorithms to compute display conflicts.
Introduction
The string data type is used to represent a number of objects such as text strings, DNA
or protein sequences in molecular biology, numerical sequences, etc. Research in molecular
biology, text analysis, and interpretation of numerical data involves the identification of
recurring patterns in data and hypothesizing about their causes and/or effects [2, 3]. Detecting
patterns visually in long strings is tedious and prone to error. In [1], 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.
We first discuss the notion of maximal patterns. Let abc be a pattern occurring m times
in a string S. Let the only occurrences of ab be those which occur in abc. Then, the
pattern ab is not maximal in S as it is always followed by c. The notion of maximality is
motivated by the assumption that in most applications, longer patterns are more significant
than shorter ones. Maximal patterns that occur at least twice are known as displayable
entities.
The problem of identifying all displayable entities and their occurrences in S can be solved
from the results in [4]. Once all displayable entities and their occurrences are obtained, we
are confronted with the problem of color coding them. In the string,
abc and def are the only displayable entities. So, S would be displayed by highlighting abc
in one color and def in another as shown in Figure 1.
In most strings, we encounter the problem of conflicts: Consider the string
cdefcdegabchabcde and its displayable entities, abc and cde (both are maximal and occur
thrice). So, they must be highlighted in different colors. Notice, however, that abc and cde
both occur in the substring abcde, which occurs as a suffix of S. Clearly, both displayable
entities cannot be highlighted in different colors in abcde as required by the model. This is

Figure

2: Alternative display model
a consequence of the fact that the letter c occurs in both displayable entities. This situation
is known as a prefix-suffix conflict (because a prefix of one displayable entity is a suffix of
the other). Note, also, that c is a displayable entity in S. Consequently, all occurrences
of c must be highlighted in a color different from those used for abc and cde. But this is
impossible as c is a subword of both abc and cde. This situation is referred to as a subword
conflict. The problem of subword conflicts may be partially alleviated by employing more
sophisticated display models as in Figure 2.
Irrespective of the display model used, it is usually not possible to display all occurrences
of all displayable entities. We are therefore forced into having to choose which ones
to display. There are three ways of achieving this:
Interactive : The user selects occurrences interactively by using his/her judgement. Typi-
cally, this would be done by examining the occurrences which are involved in a conflict and
choosing one that is the most meaningful.
weight is assigned to each occurrence. The higher the weight, the
greater the desirability of displaying the corresponding occurrence. Criteria that could be
used in assigning weights to occurrences include: length, position, number of occurrences
of the pattern, semantic value of the displayable entity, information on conflicts, etc. The
information is then fed to a routine which selects a set of occurrences so that the sum of
their weights is maximized (algorithms for these are discussed in [1]).
In a practical environment, the most appropriate method would be a
hybrid of the interactive and automatic approaches described above. The user could select
some occurrences that he/she wants included in the final display. The selection of the
remaining occurrences can then be performed by a routine which maximizes the display
information.
All the methods described above require knowledge about the conflicts, either to choose
which occurrences to display (interactive) or to assign weights to the occurrences (au-
tomatic). Automatic methods would require a list of all the conflicts, while interactive
methods require information about conflicts local to a particular segment of the string.
Since prefix suffix and subword conflicts are handled differently by different display models,
separate lists for each are required.
In this paper we identify a family of problems relating to the identification of conflicts
at various levels of detail. Problems relating to statistical information about conflicts are
also identified. Efficient algorithms for these problems are presented. All algorithms make
use of the symmetric compact directed acyclic word graph (scdawg) data structure [4] and
may be thought of as operations or traversals of the scdawg. The scdawg, which is used
to represent strings and sets of strings evolved from other string data structures such as
position trees, suffix trees, and directed acyclic word graphs [5, 6, 7, 8].
Section 2 contains preliminaries including definitions of displayable entities, conflicts,
and scdawgs. Section 3 presents optimal algorithms to determine whether a string has
conflicts and to compute subword and prefix suffix conflicts in a string. Sections 4, 5, and
6 discuss related size restricted, pattern restricted, and statistical problems and show how
to implement these by modifying the algorithms of Section 3. Finally, Section 7 presents
experimental data on the run times of some of these algorithms.
Preliminaries
2.1 Definitions
string of length n, whose characters are chosen from a fixed alphabet,
\Sigma, of constant size. A pattern in S is said to be maximal iff its occurrences are not all
preceded by the same letter, nor all followed by the same letter. Consider the string
abczdefydefxabc. Here, abc and def are the only maximal patterns. The occurrences of def
are preceded by different letters (z and y) and followed by different letters (y and x). The
occurrences of abc are not preceded by the same letter (the first occurrence does not have
a predecessor) nor followed by the same letter. However, de is not maximal because all its
occurrences in S are followed by f .
A pattern is said to be a displayable entity (or displayable) iff it is maximal and occurs
more than once in S (all maximal patterns are displayable entities with the exception of S,
which occurs once in itself).
(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, 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 .
2.2 Symmetric Compact Directed Acyclic Word Graphs (SCDAWGs)
An scdawg, SCD(S), 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, L(S), of labeled directed edges 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 in S to be the smallest superword of ff in fde(v): v ffl V (S)g, if such
a superword exists. Otherwise, imp(S; ff) does not exist.
Re edges from a vertex, v 1 , are obtained as follows: for each letter, x, in \Sigma, if imp(S; de(v 1 )x)
exists and is equal to de(v 2 there exists 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 a vertex, v 1 , are obtained as follows: for each letter, x, in \Sigma, if imp(S; xde(v 1
exists and is equal to de(v 2 there exists 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

3 shows V (S) and R(S) corresponding to are
gabcde
de
e
de
c
abc
bc
de
gabcde
fabcgabcde
gabcde
fabcgabcde
cde
sink
abc
c
source

Figure

3: Scdawg for
the displayable entities of S. There are two outgoing re edges from the vertex representing
abc. These edges correspond to g. imp(S;
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 fa; b; c; e; fg.
The space required for SCD(S) is O(n) and the time needed to construct it is O(n)
[5, 4]. While we have defined the scdawg data structure for a single string, S, it can be
extended to represent a set of strings.
2.3 Computing Occurrences of Displayable Entities

Figure

4 presents an algorithm for computing the end positions of all the occurrences of
de(v) in S. This is based on the outline provided in [4]. The complexity of Occurrences(S; v;
is proportional to the number of occurrences of de(v) in S.
Algorithm A
Procedure Occurrences(S:string,u:vertex,i:integer)
begin
if de(u) is a suffix of S
for each right out edge, e, from u do
begin
Let w be the vertex on which e is incident;

Figure

4: Algorithm for obtaining occurrences of displayable entities
2.4 Prefix and Suffix Extension Trees
The prefix extension tree, PET (S; v), at vertex v in V (S) is a subgraph of SCD(S) consisting
of (i) the root, v, (ii) PET (S; w) defined recursively for each vertex w in V (S) such
that there exists a prefix extension edge from v to w, and (iii) the prefix extension edges
leaving v. The suffix extension tree, SET (S; v), at v is defined analogously.
In

Figure

consists of the vertices representing c and cde, and
the sink. It also includes the prefix extension edges from c to cde and from cde to the sink.
Similarly, SET (S; v), consists of the vertices representing c and abc and the suffix
extension edge from c to abc (not shown in the figure).
contains a directed path from v to a vertex, w, in V (S)
iff de(v) is a prefix (suffix) of de(w).
Proof If there is a directed path in PET (S; v), from v to some vertex, w, then from the
definition of a prefix extension edge and the transitivity of the "prefix of " relation, de(v)
must be a prefix of de(w).
If de(v) is a prefix of de(w), then there exists a series of re edges from v to w, such that
de(v), when concatenated with the labels on these edges yields de(w). But, each of these
re edges must be a prefix extension edge. So a directed path from v to w exists in the
The proof for SET (S; v) is analogous. 2
Computing Conflicts
3.1 Algorithm to determine whether a string is conflict free
Before describing our algorithm to determine if a string is free of conflicts, we establish
some properties of conflict free strings that will be used in this algorithm.
Lemma 2 If a prefix-suffix conflict occurs in a string S, then a subword conflict must occur
in S.
Proof If a prefix-suffix conflict occurs between two displayable entities, W 1 and W 2 then
there exists W p WmW s such that W p are
followed by the same letter and W 2 isn't always preceded by the
same letter. I.e., Wm isn't always followed by the same letter and Wm isn't always preceded
by the same letter. So, Wm is maximal. But, W 1 occurs at least twice in S (since W 1 is a
displayable entity). So Wm occurs at least twice (since Wm is a subword of W 1 ) and is a
displayable entity. But, Wm is a subword of W 1 . So a subword conflict occurs between Wm
and W 1 . 2
Corollary 1 If string S is free of subword conflicts, then it is free of conflicts.
Lemma 3 de(w) is a subword of de(v) in S iff there is a path comprising right extension
and suffix extension edges from w to v.
Proof From the definition of SCD(S), if there exists an re edge from u to v, then de(u)
is a subword of de(v). If there exists a suffix extension edge from u to v, then de(u) is a
suffix (and therefore a subword) of de(v). If there exists a path comprising right and suffix
extension edges from w to v, then by transitivity, de(w) is a subword of de(v).
Algorithm NoConflicts(S)
1. Construct SCD(S).
2. Compute
3. Scan all right and suffix extension out edges from each element of V source . If any edge points to
a vertex other than the sink, then a conflict exists. Otherwise, S is conflict free.

Figure

5: Algorithm to determine whether a string is Conflict Free
If de(w) is a suffix of de(v), then there is a path (Lemma 1) of suffix extension edges
from w to v. If de(w) is a subword, but not a suffix of de(v), then from the definition of an
scdawg, there is a path of re edges from w to a vertex representing a suffix of de(v). 2
source denote all vertices in V (S) such that an re or suffix extension edge exists
between the source vertex of SCD(S) and each element of V source .
Lemma 4 String S is conflict free iff all right extension or suffix extension edges leaving
vertices in V source end at the sink vertex of SCD(S).
Proof A string, S is conflict free iff there does not exist a right or suffix extension edge
between two vertices, neither of which is the source or sink of SCD(S) (Corollary 1 and
Lemma 3).
Assume that S is conflict free. Consider a vertex, v, in V source . If v has right or suffix
extension out edge ! v; w ?, then v 6= sink. If w 6= sink, then de(v) is a subword of de(w)
and the string is not conflict free. This contradicts the assumption on S.
Next, assume that all right and suffix extension edges leaving vertices in V source end at
the sink vertex. Clearly, there cannot exist right or suffix extension edges between any two
vertices, v and w (v 6= sink, w 6= sink) in V source . Further, there cannot exist a vertex, x,
in V (S) (x 6= source, x 6= sink) such that x
source . For such a vertex to exist, there
must exist a path consisting of right and suffix extension edges from a vertex in V source to
x. Clearly, this is not true. So, S is conflict free. 2
The preceding development leads to algorithm NoConflicts (Figure 5).
Theorem 1 Algorithm NoConflicts is both correct and optimal.
Proof Correctness is an immediate consequence of Lemma 4. Step 1 takes O(n) time
[4]. Step 2 takes O(1) time since jV source j ! 2j\Sigmaj. Step 3 takes O(1) time since the number
of out edges leaving V source is less than 4j\Sigma 2 j. So, NoConflicts takes O(n) time, which is
optimal. Actually, steps 2 and 3 can be merged into step 1 and the construction of SCD(S)
aborted as soon as an edge that violates Lemma 4 is created. 2
3.2 Subword Conflicts
Consider the problem of finding all subword conflicts in string S. Let k s be the number
of subword conflicts in S. Any algorithm to solve this problem requires (i) O(n) time to
read in the input string and (ii) O(k s ) time to output all subword conflicts. So, O(n
is a lower bound on the time complexity for this problem. For the string
This is an upper bound on the number of
conflicts as the maximum number of substring occurrences is O(n 2 ) and in the worst case,
all occurrences conflict with each other. In this section, a compact method for representing
conflicts is presented. Let k sc be the size of this representation. k sc is n 3 =6
or O(n 3 ), for a n . Compaction never increases the size of the output and may yield up to a
factor of n reduction, as in the example. The compaction method is described below.
Consider S= abcdbcgabcdbchbc. The displayable entities are D
The ending positions of D 1 are 6 and 13 while those of D 2 are 3, 6, 10, 13, and 16. A
list of the subword conflicts between D 1 and D 2 can be written as: f(6,3), (6,6), (13,10),
(13,13)g. The first element of each ordered pair is the last position of the instance of the
superstring (here, D 1 ) involved in the conflict; the second element of each ordered pair is
the last position of the instance of the substring (here, D 2 ) involved in the conflict.
The cardinality of the set is the number of subword conflicts between D 1 and D 2 . This
is given by: frequency(D 1 )\Lambdanumber of occurrences of D 2 in D 1 . Since each conflict is represented
by an ordered pair, the size of the output is 2(frequency(D 1 )\Lambdanumber of occurrences
of D 2 in D 1 ).
Observe that the occurrences of D 2 in D 1 are in the same relative positions in all instances
of D 1 . It is therefore possible to write the list of subword conflicts between D 1 and D 2 as:
(6,13):(0,-3). The first list gives all the occurrences in S of the superstring (D 1 ), and the
second gives the relative positions of all the occurrences of the substring (D 2 ) in the superstring
(D 1 ) from the right end of D 1 . The size of the output is now: frequency(D 1 )+number
of occurrences of D 2 in D 1 . This is more economical than our earlier representation.
In general, a substring, D i , of S will have conflicts with many instances of a number of
displayable entities (say, D z ) of which it (D i ) is the superword. We would then
write the conflicts of D i as:
(l 1
z ).
Here, the l i 's represent all the occurrences of D i in S; the l 0
z s represent the
relative positions of all the occurrences of D z in D i . One such list will be required
for each displayable entity that contains other displayable entities as subwords. The
following equalities are easily obtained:
Size of Compact Representation =
Size of Original Representation
f i is the frequency of D i (only D i 's that have conflicts are considered). r ij is the frequency
of D j in one instance of D i . D represents the set of all displayable entities of S. D s
represents
the set of all displayable entities that are subwords of D i .
defined as the subgraph of SCD(S) which consists of the set of
vertices, SV (S; v) ae V (S) which represents displayable entities that are subwords of de(v)
and the set SE(S; v) of all re and suffix extension edges that connect any pair of vertices
in SV (S; v). Define SGR (S; v) as SG(S; v) with the directions of all the edges in SE(S; v)
reversed.
Lemma 5 SG(S; v) consists of all vertices, w, such that a path comprising right or suffix
extension edges joins w to v in SCD(S).
Proof Follows from Lemma 3. 2
2 for each vertex, v, in SCD(S) do
5 for all vertices, u, such that a right or suffix extension edge, ! u; v ?, is incident on v do
6 if u 6= source then
8 for each vertex, v, in SCD(S) such that v 6= sink and v:subword is true do
9 GetSubwords(v);
Procedure GetSubwords(v)
7 for each vertex, x (6= source), in reverse topological order of SG(S; v) do
9 if de(x) is a suffix of de(v) then x:sublist = f0g else x:sublist = fg;
for each vertex, w, in SG(S; v) on which an re edge, e from x is incident do
12 for each element, l, in w:sublist do
x:sublist
14 end;

Figure

Optimal algorithm to compute all subword conflicts
Algorithm B of Figure 6 computes the subword conflicts of S. The subword conflicts are
computed for precisely those displayable entities which have subword displayable entities.
Lines 4 to 6 of Algorithm B determine whether de(v) has subword displayable entities. Each
incoming right or suffix extension edge to v is checked to see whether it originates at the
source. If any incoming edge originates at a vertex other than source, then v.subword is set
to true (Lemma 3). If all incoming edges originate from source, then v.subword is set to
false. Procedure Getsubwords(v), which computes the subword conflicts of de(v) is invoked
if v:subword is true.
Procedure Occurrences(S; v; (line 2 of GetSubwords) computes the occurrences of de(v)
in S and places them in v.list. Procedure SetUp in line 5 traverses SGR (S; v) and initializes
fields in each vertex of SGR (S; v) so that a reverse topological traversal of SG(S; v) may be
subsequently performed. Procedure SetSuffixes in line 6 marks vertices whose displayable
entities are suffixes of de(v). This is accomplished by following the chain of reverse suffix
extension pointers starting at v and marking the vertices encountered as suffixes of v.
A list of relative occurrences, sublist, is associated with each vertex, x, in SG(S; v).
x.sublist represents the relative positions of de(x) in an occurrence of de(v). Each relative
occurence is denoted by its position relative to the last position of de(v) which is represented
by 0. If de(x) is a suffix of de(v) then x.sublist is initialized with the element, 0.
The remaining elements of x.sublist are computed from the sublist fields of vertices, w, in
v) such that a right extension edge goes from x to w. Consequently, w.sublist must
be computed before x.sublist. This is achieved by traversing SG(S; v) in reverse topological
order [9].
Lemma 6 x:sublist for vertex, x, in SG(S; v) contains all relative occurrences of de(x) in
de(v) on completion of GetSubwords(v).
Proof The correctness of this lemma follows from the correctness of procedure Occurrences(S; v;
of Section 2.3 and the observation that lines 7 to 15 of procedure GetSubwords achieve the
same effect as Occurrences(S; v; 0) in SG(S; v). 2
Theorem space and is therefore optimal.
Proof Computing v:subword for each vertex, v, in V (S) takes O(n) time as constant time
is spent at each vertex and edge in SCD(S). Consider the complexity of GetSubwords(v).
Lines 2 and 3 take O(jv:listj) time. Let the number of vertices in SG(S; v) be m. Then the
number of edges in SG(S; v) is O(m). Line 5 traverses SG(S; v) and therefore consumes
O(m) time. Line 6, in the worst case, could involve traversing SG(S; v) which takes O(m)
time. Computing the relative occurrences of de(x) in de(v) (lines 9-15) takes O(jx:sublistj)
time for each vertex, x, in SG(S; v). So, the total complexity of GetSubwords(v) is O(jv:listj+
However, m is O(
xfflSV (S;v);x6=v jx:sublistj), since jx:sublistj  1 for each x ffl SG(S; v).
xfflSV (S;v);x6=v jx:sublistj is the size of the output for GetSubwords(v).
So, the over all complexity of algorithm B is O(n
for
3.3 Prefix Suffix Conflicts
As with subword conflicts, the lower bound for the problem of computing prefix-suffix
conflicts is O(n+ k p ), where k p is the number of prefix-suffix conflicts in S. For
is which is also the upper bound on k p .
Unlike subword conflicts, it is not possible to compact the output representation.
Let w and x, respectively, be vertices in SET (S; v) and PET (S; v). Let
to be the vertex representing
imp(S; WwW v W x ), if such a vertex exists. Otherwise, Pshadow(w; v;
define Pimage(w; v;
W a WwW v W x for some (possibly empty) string, W a . Otherwise, Pimage(w; v;
For each vertex, w in SET (S; v), a shadow prefix dag, SPD(w; v), rooted at vertex w is
comprised of the set of vertices fPshadow(w; v; x)j x on PET (S; v), Pshadow(w; v; x) 6=
nilg.

Figure

7 illustrates these concepts. Broken lines represent suffix extension edges, dotted
lines represent right extension edges, and solid lines represent prefix extension edges.
ff
l
c
a
s
r
z
x

Figure

7: Illustration of prefix and suffix trees and a shadow prefix dag
SET (S; v), PET (S; v), and SPD(w; v) have been enclosed by dashed, solid, and dotted
lines respectively. We have: Pshadow(w; v;
Lemma 7 A prefix-suffix conflict occurs between two displayable entities, W
and with respect to a third displayable entity
in SET (S; v) and x occurs in PET (S; v), and (ii) Pshadow(w; v; x) 6= nil. The number of
conflicts between de(w) and de(x) with respect to de(v) is equal to the number of occurrences
of de(Pshadow(w; v; x)) in S.
Proof By definition, a prefix-suffix conflict occurs between displayable entities W 1 and
with respect to Wm iff there exists W p WmW s in S, where W
WmW s .
Clearly, Wm is a suffix of W 1 and Wm a prefix of W 2 iff w occurs in SET (S; v) and x
occurs in PET (S; v). W p WmW s occurs in S iff imp(S; W p WmW s
nil. The number of conflicts between de(w) and de(x) is equal to the number of occurrences
of imp(S; W p WmW s
Lemma 8 If a prefix-suffix conflict does not occur between de(w) and de(x) with respect
to de(v), where w occurs in SET (S; v) and x occurs in PET (S; v), then there are no
prefix-suffix conflicts between any displayable entity which represents a descendant of w
in SET (S; v) and any displayable entity which represents a descendant of x in PET (S; v)
with respect to de(v).
Proof Since w is in SET (S; v) and x is in PET (S; v), we can represent de(w) by W p de(v)
and de(x) by de(v)W s . If no conflicts occur, then W p de(v)W s does not occur in S. The
descendants of w in SET (S; v) will represent displayable entities of the form W a
W a W p de(v), while the descendants of x in PET (S; v) will represent displayable entities
of the form de(x)W are substrings of S. For a prefix-suffix
e
f
r
y
z
x

Figure

8: Illustration of conditions for Lemma 9
conflict to occur between W a de(w) and de(x)W b with respect to de(v), W a W p de(v)W s W b
must exist in S. However, this is not possible as W p de(v)W s does not occur in S and the
result follows. 2
Lemma 9 In SCD(S), if (i) there is a prefix extension edge, e,
from x to z with label aff. (iii) there is a right extension edge, f , from y to u with label afi,
then Pshadow(w; v;
Proof Let
for some possibly empty string W a .
W b W a Ww de(v)W x afi for some string W b .
To prove the lemma, we must show that
u. I.e., that (i) Ww de(v)W x aff is a subword of de(u) and (ii) de(u) is
the smallest superword of Ww de(v)W x aff represented by a vertex in SCD(S).
(i) Assume that Ww de(v)W x aff is not a subword of
ff is not a prefix of fi.
Case 1: fi is a proper prefix of ff.
Since W b W a Ww de(v)W x afi is maximal, its occurrences are not all followed by the same
letter. This is true for any of its suffixes. In particular all occurrences of de(v)W x afi cannot
be followed by the same letter. Similarly, all occurrences of de(v)W x afi cannot be preceded
by the same letter as it is a prefix of de(v)W x de(z). So, de(v)W x afi is a displayable
entity of S. Consequently, the prefix extension edge from x corresponding to the letter a
must be directed to the vertex representing de(v)W x afi. This is a contradiction.
Case 2: afi matches aff in the first k characters, but not in the th character (1  k
We have 1. Clearly, the strings de(v)W x aflff 1 and
W b W a Ww de(v)W x aflfi 1 occur in S. I.e., all occurrences of de(v)W x afl cannot be followed
by the same letter. Further, all occurrences of de(v)W x afl cannot be preceded by the same
letter as it is a prefix of de(v)W x it is a displayable entity of S. Consequently,
the prefix extension edge from x corresponding to the letter a must be directed to the vertex
representing de(v)W x afl. This results in a contradiction. Thus, ff is a prefix of fi.
(ii) From (i), ff is a prefix of fi. Assume that W b W a Ww de(v)W x afi is not the smallest su-
perword of Ww de(v)W x aff. Since x is the smallest
superword of Ww de(v)W x , the smallest superword of Ww de(v)W x aff must be of the form
W a Ww de(v)W x afl where ff is a prefix of fl which is a proper prefix of fi and/or W b 1
is a
proper suffix of W b . But, the right out edge, f , from z points to the smallest superword of
W a Ww de(v)W x a (from the definition of SCD(S)) which is W b W a Ww de(v)W x afi. So, W b 1
which is a contradiction. 2
In SCD(S), if (i) there is a path of prefix extension
edges from x to x 1 (let the concatenation of their labels be aff), (iii) there is a prefix extension
edge from x 1 to z with label bfl, and (iv) there is a right extension edge, f from y to u with
label affbfi, then
Proof Similar to proof of Lemma 9. 2
Path P
aff
z
x
f
r
y

Figure

9: Illustration of conditions for Lemmas 10 and 11
Algorithm C
Construct SCD(S).
2 for each vertex, v, in SCD(S) do
Procedure NextSuffix(current,v);
1 for each suffix extension edge ! current; w ? do
2 fthere can only be one suffix extension edge from current to wg
6 if exist then NextSuffix(w,v);

Figure

10: Optimal algorithm to compute all prefix-suffix conflicts
Lemma 11 In Lemma 9 or Lemma 10, if jlabel(f)j  sum of the lengths of the labels of
of the edges on the prefix extension edge path P from x to z, then label(f) = concatenation
of the labels on P and
Proof From Lemma 10, the concatenation of the labels of the edges of P is a prefix of
label(f ). But, jlabel(f)j  sum of the lengths of the labels of the edges on P . I.e., label(f)
concatenation of the labels of the series edges on P . y,
of x in PET (S; v).
Proof Follows from Lemmas 7 and 8. 2
Algorithm C in Figure 10 computes all prefix-suffix conflicts of S. Line 1 constructs
SCD(S). Lines 2 and 3 compute all prefix-suffix conflicts in S by separately computing for
each displayable entity, de(v), all the prefix-suffix conflicts of which it is the intersection.
Procedure NextSuffix(current,v) computes all prefix-suffix conflicts between displayable
entities represented by descendants of current in SET (S; v) and displayable entities represented
by descendants of v in PET (S; v) with respect to de(v) (so the call to NextSuffix(v,v)
in line 3 of Algorithm C computes all prefix-suffix conflicts with respect to de(v)). It does
so by identifying SPD(w; v) for each child, w, of current in SET (S; v). The call to Shad-
owSearch(v,w,v,w) in line 5 identifies SPD(w; v) and computes all prefix-suffix conflicts
between de(w) and displayable entities represented by descendants of v in PET (S; v) with
respect to de(v). If ShadowSearch(v,w,v,w) does not report any prefix-suffix conflicts then
the global variable exist is unchanged by ShadowSearch(v,w,v,w) (i.e., exist = false, from
line 4). Otherwise, it is set to true by ShadowSearch. Line 6 ensures that NextSuffix(w,v)
is called only if ShadowSearch(v,w,v,w) detected prefix suffix conflicts between de(w) and
displayable entities represented by descendants of v in PET (S; v) with respect to de(v)
(Lemma 8).
For each descendant, q, of vertex x in PET (S; v), procedure ShadowSearch(v,w,x,y)
computes all prefix suffix conflicts between de(w) and de(q) with respect to de(v). y represents
Pshadow(w; v; x). We will show that all calls to ShadowSearch maintain the invariant
(which is referred to as the image invariant hereafter) that
nil. Notice that the invariant holds when ShadowSearch is called from NextSuffix as
v). The for statement in line 1 examines each prefix out edge from x. Lines 3
to 28 compute all prefix suffix conflicts between de(w) and displayable entities represented
by vertices in PET (S; z), where z is the vertex on which the prefix extension edge from x
is incident. The truth of the condition in the for statement of line 1, line 4 and the truth
of the condition inside the if statement of line 5 establish that the conditions of Lemma 9
are satisfied prior to the execution of lines 8 and 9. The truth of the comment in line 8
and the correctness of line 9 are established by Lemma 9. Procedure ListConflicts of line 9
lists all prefix suffix conflicts between de(w) and de(z) with respect to de(v). Similarly, the
truth of the condition inside the while statement of line 11, lines 13 and 14, and the truth
of the condition inside the if statement of line 15 establish that the conditions of Lemma
are satisfied prior to the execution of lines 18-20. Again, the correctness of lines 18-20 are
established by Lemma 10. If done remains false on exiting the while loop, the condition
of the if statement of line 15 must have evaluated to true. Consequently, the conditions of
apply. Further, since the while loop of line 11 terminated, the additional condition
of Lemma 11 is also satisfied. Hence, from Lemma 11, and the
Procedure ShadowSearch(v; w; x; y);
1 for each prefix extension edge do
2 fThere can only be one prefix extension edge from x to zg
first character in label(e);
5 if there is a right extension edge, whose label starts with fc
6 then
9
while (not done) and (jlabel(f)j ? jlabel(e)j do
14 th character in label(f).
15 if there is a prefix extension edge starting with nc
22 else
26 ShadowSearch(v,w,z,u);
28 end
29 end

Figure

11: Algorithm for shadow search
image invariant for the recursive call to ShadowSearch(v; w; z; u) is maintained. Line 27 sets
the global variable exist to true since the execution of the then clause of the if statement of
line 5 ensures that at least one prefix-suffix conflict is reported by ShadowSearch(v; w; v; w)
(Lemmas 7 and 9). exist remains false only if the then clause of the if statement (line 5)
is never executed.
Theorem 3 Algorithm C computes all prefix-suffix conflicts of S in O(n
time, which is optimal.
Proof Line 1 of Algorithm C takes O(n) time [4]. The cost of lines 2 and 3 without
including the execution time of NextSuffix(v; v) is O(n).
Next, we show that NextSuffix(v; v) takes O(k v ) time, where k v is the number of prefix
suffix conflicts with respect to v (i.e., k v represents the size of the output of NextSuffix(v; v)).
Assume that NextSuffix is invoked p times in the computation. Let S T be the set of invocations
of NextSuffix which do not call NextSuffix recursively. Let p j. Let S F be the
set of invocations of NextSuffix which do call NextSuffix recursively. Let p Each
element of S F can directly call at most j\Sigmaj elements of S T . So, p T =p F  j\Sigmaj. From lines
4-6 in NextSuffix(current,v), each element of S F yields at least one distinct conflict from
its call to ShadowSearch. Thus, p F  k v . So,
cost of execution of NextSuffix without including the costs of recursive calls to NextSuffix
and ShadowSearch is O(j\Sigmaj) (= O(1)) as there are at most j\Sigmaj suffix edges leaving a vertex.
So, the total cost of execution of all invocations of NextSuffix spawned by NextSuffix(v; v)
without including the cost of recursive calls to ShadowSearch is
Next, we consider the calls to ShadowSearch that were spawned by NextSuffix(v; v). Let
be the set of invocations of ShadowSearch which do not call ShadowSearch recursively.
Let q A = jT A j. Let TB be the set of invocations of ShadowSearch which do call ShadowSearch
recursively. Let q We have q A
(j\Sigmaj+1)q B+j\Sigmajp. From the algorithm, each element of TB yields a distinct conflict. So, q B
The cost of execution of a single call to ShadowSearch
without including the cost of executing recursive calls to ShadowSearch is O(1)
O(complexity of ListConflicts of line
(complexity of ListConflicts of line 20
in the i th iteration of the while loop)), where w denotes the number of iterations of the
while loop. The complexity of ListConflicts is proportional to the number of conflicts
it reports. Since ListConflicts always yields at least one distinct conflict, the complexity
of ShadowSearch is O(1 Summing over all calls to ShadowSearch spawned by
NextSuffix(v; v), we obtain O(q Thus, the total complexity of Algorithm C
is O(n
3.4 Alternative Algorithms
In this section, an algorithm for computing all conflicts (i.e., both subword and prefix-suffix
conflicts) is presented. This solution is relatively simple and has competitive run times.
However, it lacks the flexibility required to efficiently solve many of the problems listed
in Sections 4, 5, and 6 . The algorithm (Algorithm D) is presented in Figure 12. Step 1
computes a list of all occurrences of all displayable entities in S. This list is obtained by first
computing the lists of occurrences corresponding to each vertex of V (S) (except the source
and the sink) and then concatenating these lists. Each occurrence is represented by its start
and end positions. Step 2 sorts the list of occurrences obtained in step 1 in increasing order
of their start positions. Occurrences with the same start positions are sorted in decreasing
order of their end positions. This is done using radix sort. Step 3 computes for the i'th
occurrence, occ i , all its prefix suffix conflicts with occurrences whose starting positions are
greater than its own, and all its subword conflicts with its subwords. occ i is checked against
conflict. Here, c is the smallest integer for which there is no
conflict between occ i and occ i+c . The start position of occ i+c is greater than the ending
position of occ i . The start position of the occ j (j  c) will also be greater than the
end position of occ i , since the list of occurrences was sorted on increasing order of start
positions. The start positions of occ i+1 ,., occ are greater than or equal to the start
positions of occ i but are less than or equal to its end position. Those occurrences among
whose start positions are equal to that of occ i have end positions that
are smaller (since occurrences with the same start position are sorted in decreasing order
of their end positions). The remaining conflicts of occ i (i.e., subword conflicts with its
superwords, prefix suffix conflicts with occurrences whose start positions are less than that
of occ i ) have already been computed in earlier iterations of the for statement in Algorithm
D.
For example, let the input to step 3 be the following list of ordered pairs:((1,6), (1,3),
(1,1), (2,2), (3,8), (3,5), (4,6), (5,8), (6,10)), where the first element of the ordered pair
denotes the start position and the second element denotes the end position of the occurrence.
Consider the occurrence (3,5). Its conflicts with (1,6), (1,3), and (3,8) are computed in
iterations 1, 2, and 5 of the for loop. Its conflicts with (4,6) and (5,8) are computed in
iteration 6 of the for loop.
Theorem 4 Algorithm D takes O(n
Proof Step 1 takes O(n is the number of occurrences of displayable
entities of S. Step 2 also takes O(n elements are to be sorted using radix
sort with n buckets. Step 3 takes O(o time: the for loop executes O(o) times; each
iteration of the while loop yields a distinct conflict. So, the total complexity is O(n+o+k).
We now show that be the number of occurrences not involved in a
conflict. Then be the number of occurrences involved in at least one conflict.
A single conflict occurs between two occurrences. So 2k
Algorithm D can be modified so that the size of the output is This may be
achieved by checking whether an occurrence is the first representative of its pattern in the
for loop of step 3. The subword conflicts are only reported for the first occurence of the
pattern. However, the time complexity of Algorithm D remains O(n + k). In this sense, it
is suboptimal.
Algorithm D
Step 1: Obtain a list of all occurrences of all displayable entities in the string. This list is obtained
by first computing the lists of occurrences corresponding to each vertex of the scdawg (except the
source and the sink) and then concatenating these lists.
Step 2: Sort the list of occurrences using the start positions of the occurrences as the primary key
(increasing order) and the end position as the secondary key (decreasing order). This is done using
Step3:
for i:= 1 to (number of occurrences) do
begin
begin
then occ i is a superword of occ j
else have a prefix-suffix conflict;

Figure

12: A simple algorithm for computing conflicts
4 Size Restricted Queries
Experimental data show that random strings contain a large number of displayable entities
of small length. In most applications, small displayable entities are less interesting than
large ones. 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:
P1: List all occurrences of displayable entities whose lengths are greater than k.
P2: Compute all prefix suffix conflicts involving displayable entities of length greater than
k.
P3: Compute all subword conflicts involving displayable entities of length greater than k.
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.
An alternative formulation of the size restricted problem which also seeks to achieve the
goal outlined above is based on reporting only those conflicts whose size is greater than
k. This formulation of the problem is particularly relevant when the conflicts are of more
interest than the displayable entities. It also establishes that all conflicting displayable
entities reported have size greater than k. We have the following problems:
P4: Obtain all prefix-suffix conflicts of size greater than some integer k.
P5: Obtain all subword conflicts of size greater than some integer k.
P1 is solved optimally by invoking Occurrences(S; v; 0) for each vertex, v, in V (S), where
combined solution to P2 and P3 uses the approach of Section 3.4. The only
modification to the algorithm of Figure 12 is in step 1 which now becomes:
Obtain all occurrences of displayable entities whose lengths are greater than k.
The resulting algorithm is optimal with respect to the expanded representation of subword
conflicts. However, as with the general problem, it is not possible to obtain separate optimal
solutions to P2 and P3 by using the techniques of Section 3.4. An optimal solution to P4 is
obtained by executing line 3 of Algorithm C of Figure 10 for only those vertices, v, in V (S)
which have jde(v)j ? k. An optimal solution to P5 is obtaind by the following modification
to Algorithm B of Figure 6:
(i) Right extension or suffix extension edges
are marked "disabled".
(ii) The definition of SG(S; v) is modified so that SG(S; v), v ffl V (S), is defined as the
subgraph of SCD(S) which consists of the set of vertices, SV (S; v) ae V (S) which represent
displayable entities of length greater than k that are subwords of de(v) and the set of all re
and suffix extension edges that connect any pair of vertices in SV (S; v).
Algorithm B is modified. The modified algorithm is shown in Figure 13.
We note that P2 and P5 are identical, since the overlap of a subword conflict is the same
as the subword displayable entity.
Algorithm B
2 for each vertex, v, in SCD(S) do
4 for each vertex, v, in SCD(S) such that jde(v)j ? k do
5 for all vertices, u, such that a non disabled right or suffix extension edge, ! u; v ? exists do
7 for each vertex, v, in SCD(S) such that v 6= sink and v:subword is true do
9 end

Figure

13: Modified version of algorithm B
5 Pattern Oriented Queries
These queries are useful in applications where the fact that two patterns have a conflict is
more important than the number and location of conflicts. The following problems arise as
a result:
List all pairs of displayable entities which have subword conflicts.
P7: 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 .
P8: Same as P6, but size restricted as in P5.
P9: Same as P7, but size restricted as in P4.
P6 may be solved optimally by reporting for each vertex v in V (S), where v does not
represent the sink of CSD(s), the subword displayable entities of de(v), if any. This is
accomplished by reporting de(w), for each vertex w, w 6= source, in SG(S; v). P7 may also
be solved optimally by modifying procedure ListConflicts of Figure 11 so that it reports
the conflicting displayable entiities and their intersection. P8 and P9 may also be solved by
making similar modifications to the algorithms of the previous section.
6 Statistical Queries
These queries are useful when conclusions are to be drawn from the data based on statistical
facts. Let f(D) denote the frequency (number of occurrences) of D in the string and
the number of occurrences of displayable entity D 1 in displayable entity D 2 .
The following queries may then be defined.
P10: 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
P11: 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
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 .
the number of prefix suffix conflicts between D 1 and D 2 with
respect to Dm and psf(D 1 ; D 2 ), the number of prefix suffix conflicts between D 1 and D 2 .
We can approximate p(D The two quantities are
identical unless a single occurrence of D 1 is a subword of two or more distinct occurrences
of D 2 . Similarly, we can approximate q(D The two quantities
are identical unless a single occurrence of D 1 has prefix suffix conflicts with two or more
distinct occurrences of D 2 . f(D 1 ) can be computed for all displayable entities in SCD(S)
in O(n) time by a single traversal of SCD(S) in reverse topological order.
be computed optimally for all D 1 , D 2 , by modifying procedure GetSubwords(v) as shown
in

Figure

14.
computed optimally, for all D 1 , D 2 , and Dm , where D 1 has a prefix
suffix conflict with D 2 with respect to Dm , by modifying ListConflicts(u; z; w) of Figure 11
so that it returns f(de(u)), since this is the number of conflicts between de(w) and de(z)
with respect to de(v). psf(D calculated by summing psf(D 1 ; D 2 ; Dm ) over all
intersections, Dm , of prefix suffix conflicts between D 1 and D 2 . p(D
may be computed by simple modifications to the algorithms used to compute rf(D
Procedure GetSubwords(v)
5 for each vertex, x (6= source), in reverse topological order of SG(S; v) do
6 begin
7 if de(x) is a suffix of de(v) then rf(de(x);
8 for each vertex, w,in SG(S; v) on which an re edge, e from x is incident do
9

Figure

14: Modification to GetSubwords(v) for computing relative frequencies
and These problems may be solved under the size restrictions of P4 and P5
by modifications similar to those made in Section 4.
7 Experimental Results
Algorithms B (Section 3.2), C (Section 3.3), and D (Section 3.4) were programmed in GNU
C++ and run on a SUN SPARCstation 1. For test data we used 120 randomly generated
strings. The alphabet size was chosen to be one of f5, 15, 25, 35g and the string length was
500, 1000, or 2000. The test set of strings consisted of 10 different strings for each of the
possible combinations of input size and alphabet size. For each of these combinations,
the average run times for the 10 strings is given in Figures 15-18.

Figure

15 gives the average times for computing all conflicts by combining algorithms
B and C.

Figure

gives the average times for computing all prefix-suffix conflicts using
Algorithm C. Figure 17 gives the average times for computing all the pattern restricted
prefix-suffix conflicts (problem P7 of Section 5) by modifying Algorithm C as described in
Section 5. Figure 18 represents the average times for Algorithm D.

Figures

15 to 17 represent the theoretically superior solutions to the corresponding prob-
lems, while Figure represents Algorithm D which provides a simpler, but suboptimal,
Size of Size of String
Alphabet 500 1000 2000

Figure

15: Time in ms for computing all conflicts using the optimal algorithm
solution to the three problems. In all cases the time for constructing scdawgs and writing
the results to a file were not included as these steps are common to all the solutions.
The results show that the suboptimal Algorithm D is superior to the optimal solution for
computing all conflicts or all prefix-suffix conflicts for a randomly generated string. This is
due to the simplicity of Algorithm D and the fact that the number of conflicts in a randomly
generated string is small. However, on a string such as a 100 which represents the worst case
scenario in terms of the number of conflicts reported, the following run times were obtained:
All conflicts, optimal algorithm: 14,190 ms
All prefix-suffix conflicts, optimal algorithm: 10,840 ms
All pattern restricted prefix-suffix conflicts, optimal algorithm: 5,000 ms
Algorithm D: 26,942 ms
The experimental results using random strings also show that, as expected, the optimal
algorithm fares better than Algorithm D for the more restricted problem of computing
pattern oriented prefix-suffix conflicts.
We conclude that Algorithm D should be used for the more general problems of computing
conflicts while the optimal solutions should be used for the restricted versions. Hence,
Algorithm D should be used in an automatic environment, while the optimal solutions
should be used in interactive or semi-automatic environments.
Size of Size of String
Alphabet 500 1000 2000

Figure

Time in ms for computing all prefix suffix conflicts using the optimal algorithm
Size of Size of String
Alphabet 500 1000 2000

Figure

17: Time in ms for computing all pattern restricted prefix suffix conflicts using the
optimal algorithm
Size of Size of String
Alphabet 500 1000 2000

Figure

18: Time in ms for algorithm D
Conclusions
In this paper, we have described efficient algorithms for the analysis and visualization of
patterns in strings. We are currently extending these to other discrete objects such as
circular strings and graphs. Extending these techniques to the domain of approximate
string matching would be useful, but appears to be difficult.



--R

"String Visualization,"
"Sequence Landscapes,"
"The Matching of Protein Sequences using Color Intrasequence Homology Displays,"
"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,"
Fundamentals of Data Structures in Pascal
--TR
Transducers and repetitions
Complete inverted files for efficient text retrieval and analysis
The matching of protein sequences using color intrasequence homology displays
Models and techniques for the visualization of labeled discrete objects
A Space-Economical Suffix Tree Construction Algorithm
Fundamentals of Data Structures in Pascal
A Data Structure for Circular String Analysis and Visualization

--CTR
Hsuan T. Chang , Neng-Wen Lo , Wei C. Lu , Chung J. Kuo, Visualization and comparison of DNA sequences by use of three-dimensional trajectories, Proceedings of the First Asia-Pacific bioinformatics conference on Bioinformatics 2003, p.81-85, February 01, 2003, Adelaide, Australia
DNA sequences;display conflicts;data visualisation;directed graphs;numerical sequences;string visualization