Subsequence

In mathematics, a subsequence of some sequence is a new sequence which is formed from the original sequence by deleting some of the elements without disturbing the relative positions of the remaining elements.

Formally, suppose that X is a set and that (a_k)_{k ∈ K} is a sequence in X, where K = {1,2,3,...,n} if (a_k) is a finite sequence and K = N if (a_k) is an infinite sequence. Then, a subsequence of (a_k) is a sequence of the form

where (n_r) is a strictly increasing sequence in the index set K.

Example

As an example,

< B,C,D,B >

is a subsequence of

< A,C,B,D,E,G,C,E,D,B,G > ,

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. For example, if

X = < A,C,B,D,E,G,C,E,D,B,G > and

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

then common subsequence of X and Y could be

G = < B,E,E >

This would not be the longest common subsequence, since G only has length 3, and the common subsequence < B,E,E,B > has length 4. The longest common subsequence of X and Y is < B,E,G,C,E,B >

Applications

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

ORG₁ = ACGGTGTCGTGCTATGCTGATGCTGACTTATATGCTA
ORG₂ = CGTTCGGCTATCGTACGTTCTATTCTATGATTTCTAA

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

See also

• subsequential limits
• limsup
• liminf