ALVIE - Longest Common Subsequence

Collection:   AlgoViz
Format:   Java Application
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: Pilu Crescenzi  
Publisher: University of Florence  
Subject:   bioinformatics  Dynamic programming  
Language: english  
Audience:   Educator  Learner  Professional/Practitioner  Researcher  
Education Level:   Higher Education  
Education Material Type:   Instructional Material  Tool  
Rights: Source code available on request
ACM CCS 2012:
Computing methodologies Applied computing Theory of computation Artificial intelligence Life and medical sciences Design and analysis of algorithms Computer vision Bioinformatics Algorithm design techniques Computer vision problems Dynamic programming Matching