Encyclopedia > Subsequence

  Article Content


A subsequence is a sequence which omits some members, for instance,
<math> Z_{yorick} = < B,C,D,B > </math>
is a subsequence of X where X is
<math> X = < A,C,B,D,E,G,C,E,D,B,G > </math>, 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

<math> Y = < B,E,G,C,F,E,U,B,K > </math>

A common subsequence of X and Y could be

<math> G = < B,E,E > </math>

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.

All Wikipedia text is available under the terms of the GNU Free Documentation License

  Search Encyclopedia

Search over one million articles, find something about almost anything!
  Featured Article

... generated, their look became fashionable in a toned-down form among even "respectable" women. Most significantly, the flappers removed the corset from female fashio ...

This page was created in 28.3 ms