Encyclopedia > Subsequence

  Article Content

Subsequence

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

ORG1 = ACGGTGTCGTGCTATGCTGATGCTGACTTATATGCTA
ORG2 = CGTTCGGCTATCGTACGTTCTATTCTATGATTTCTAA

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
Bullying

... for any period of time without a legitimate basis of authority. The first to have the title of "Tyrant" was Pisistratus in 560 BC. In modern times Tyrant has come ...

 
 
 
This page was created in 24.5 ms