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
Canadian Music Hall of Fame

... 1978 Oscar Peterson 1979 Hank Snow 1980 Paul Anka 1981 Joni Mitchell 1982 Neil Young 1983 Glenn Gould 1986 Gordon Lightfoot 1987 The Guess Who[?] 1989 ...

 
 
 
This page was created in 25.5 ms