Microsoft Excel Implementation of a Longest Common Subsequence Algorithm

This Excel worksheet template runs Hirschberg’s longest common subsequence (LCS) algorithm for sequence alignment.

One sequence is entered into the topmost row, and the other sequence is entered into the leftmost column. This algorithm can be applied to any character set, but for demonstration purposes, random letters chosen from the set {A, C, G, T} make up the sequences in the template. Press F9 if you want to generate new random sequences.

Cells are colored with one of three colors indicating the path for the traceback step. The cell coloring gives a visual perspective to the algorithm.

Key

Red: Diagonal up and left

Green: Up

Blue: Left

Screenshot of the Excel LCS algorithm template.

Download Link

Longest Common Subsequence Algorithm Template

(Works for Excel 97-2003, Excel 2007, and Excel 2010)