Related methods

I've come across a few other methods to turn sequences into pictures. The most appealing and broadly applicable technique is called a "dotplot." (quick intro; detailed description.) Dotplots display a kind of graphical auto-correlation matrix for a sequence; they exploit the viewer's ability to spot patterns rather than relying on an explicit algorithm as matching diagrams do. That makes dotplots especially good for visualizing corrupted data, since the eye is excellent at spotting inexact matches.

On the other hand, in some situations it makes sense to have the computer do the matching. For instance, a dotplot of a melody would highlight repeated passages but not transposed parts--whereas a custom pattern recognition algorithm can easily find transposed passages. Furthermore, since matching diagrams "know" about patterns, it's easy to add a filtering capability by hiding repetitions that are smaller than some threshold.

Dotplots have another weakness, caused by their matrix format. If a pattern is repeated n times in a sequence, it will create n^2 "features" in the diagram. Obviously this becomes unwieldy for large numbers of repetitions. The last diagram on this dotplot page is a good example of this problem.

Other methods to visualize sequences include "H-curve" and "Chaos game" representations. (I don't know of web-based descriptions of these methods, but you can find references here.) Both methods have been used by biologists studying DNA. They each work by mapping a sequence of symbols to a sequence of geometric transformations and then drawing the orbit of a single point as it is acted on by the transformations. This is a natural idea, but I find the results uninformative. Deducing relationships between geometry and movement in dynamical systems is just plain hard.

A completely different approach is to look for a "grammar" of repetitions. Two people who tried this describe the results here. They even briefly touch on music. This work is not visually oriented, though it's impressive (at least to me) that they found a linear-time algorithm to deduce grammars.

I'd like to hear about other techniques for visualizing sequences... if you know of others, mail me at:

Intro | Musical structure | Patterns in encoded data | Related methods | Implementation
Martin Wattenberg, July 1999