Main Page | See live article | Alphabetical index


A subsequence is a sequence which omits some members, for instance,
is a subsequence of X where X is
, with corresponding index sequence <3,7,9,10>

Given two sequences X and Y, a sequence G is said to be a common subsequence of X and Y, if G is a subsequence of both X and Y.

Given X as above, and

A common subsequence of X and Y could be

This would not be the longest common subsequence, since G only has length 3, and the sequence < B,E,E,B > has length 4.

It turns out the longest common subsequence of X and Y would be < B,E,G,C,E,B >

Subsequences have applications to computer science, especially in the discipline of Bioinformatics, where computers are used to compare, analyze, and store DNA strands.

Take two strands of DNA, say


Subsequences are used to determine how similar the two strands of DNA are, using the DNA bases: adenine, guanine, cytosine and thymine.

A common problem in subsequences is the Longest-common subsequence problem, where we use dynamic programming to find a maximum length subsequence of two or more sequences.