Approximate Pattern Matching Using Suffix Trees


This applet is product of the Analysis of Algorithms undergraduate course project at the University of Brasilia, Brazil. It was developed by the Computer Science students (in alphabetical order):

Fabrício César Ferreira Anastácio
Leon Sólon da Silva
Maya Haridasan

The course was offered in the second semester of 2001 by Professor Mauricio Ayala Rincón.

This implementation is based on the online suffix tree construction [2] and aproximate string matching [1] algorithms proposed by Esko Ukkonen.

March 2002

Please, enable Java in your browser or download the Sun Java Plug-In.

Running the Matcher:

1) Opening the Matcher: Press the "Launch Matcher" button;

2) Setting the Alphabet: Press the "Set..." button and select the alphabet symbols in the Alphabet Editor frame, pressing the "OK" button after the selection is complete;

3) Setting the Text: Select the "text" radio button, set the total number of symbols for the text, select the construction method (random, fibonacci or file - for the fibonacci option the number given is its order and for the file option this value isn´t necessary) and press the "Construct" button (P.S.: In the applet version, the "File" radio button is disabled);

4) Setting the Pattern: Select the "pattern" radio button and do as was done for setting the text (item 3);

5) Constructing the Suffix Tree: After setting the text, press the "Construct" button in the suffix tree panel (about in the middle on the right);

6) Searching for the Pattern: After constructing the suffix tree for the text (the tree image is green) and setting the pattern string, set the k-approximation value (number of symbols which can be different from the pattern in an occurrence) and press the "Search" button;

7) Checking the occurrences: The search result appears in the "Output" text area and each occurrence can be viewed sequentially (forward and reward) in the text using the arrow buttons placed below the text area;

8) Searching Again: For a new search on the same text without having to construct the suffix tree again, press the "Reset" button in the suffix tree panel, set a new value for the k-approximation and press the "Search" button;

9) Getting Information: Press the info ("i") button at the bottom left side of the screen for more information about the project and its developers;

10) Closing the Matcher: Press the "X" button at the upper right corner of the frame window or press the "Launch Matcher" button again.

Last update: May 16, 2002

Main References:

[1] UKKONEN, E. Approximate String-Matching over Suffix-Trees. In: A. Apostolico, M. Crochemore, Z. Galil, and U. Manber, editors, Fourth Annual Sysmposium on Combinatorial Matching, Padova, Italy, volume 684 of LNCS, pages 228-242. Springer, June 1993.
[2] UKKONEN, E. On-line Construction of Suffix-Trees. Algorithmica, 14:249-260, 1995.