ALVIE - Longest Common Subsequence
| Collection: | AlgoViz |
| Source: | http://algoviz.org/node/1921 |
| Format: | Java Application, Flash |
This visualization shows the behavior of a dynamic programming algorithm for solving the longest common subsequence of two strings. The implemented algorithm is described and analyzed in the associated PDF file (which can be viewed within ALVIE itself): the presentation is mainly based on Chapter 6 of the book Introduction to Bioinformatics Algorithms by Jones and Pevzner. The problem is presented as a longest path problem on grids: for this reason, the dynamic programming table is visualized as a grid-like graph (and not as a matrix). Each time the longest path corresponding to a node must be computed, the node itself and its predecessors (involved in the computation) are shown with different colors: moreover, the corresponding characters in the two strings are emphasized by using colors. Each node contains not only the length of its longest path but also the direction towards the origin (that is, North, West, or North-West). This further information is used at the end of the algorithm to reconstruct (and to show) the longest common subsequence. The visualization includes a C-like pseudocode whose lines are emphasized according to the step which is executed (the pseudo-code can be hidden, if desired). Simple-to-use user interface for walking through the example. Simply open up the AV (see directions below) and step through the example with pseudo-code. As you go through the example, you are directed to the corresponding line in the pseudocode and given a line or two of explanation in the message window. Attractive layout of the data, including colors.
| Creator(s): | Pilu Crescenzi |
| Publisher: | University of Florence |
| Subject: | Dynamic programming, bioinformatics |
| Language: | english |
| Rights: | Source code available on request |
| Audience: | Educator, Learner, Professional/Practitioner, Researcher |
| Education Level: | Higher Education |
| Material Type: | Instructional Material, Tool |

