Rearuh

This article includes a list of references, related reading or external links, but its sources remain unclear because it lacks inline citations. Please help to improve this article by introducing more precise citations. (November 2018) (Learn how and when to remove this template message)

In mathematics, a subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements. For example, the sequence ⟨A,B,D⟩{displaystyle langle A,B,Drangle } is a subsequence of ⟨A,B,C,D,E,F⟩{displaystyle langle A,B,C,D,E,Frangle } obtained after removal of elements C{displaystyle C}, E{displaystyle E}, and F{displaystyle F}. The relation of one sequence being the subsequence of another is a preorder.

The subsequence should not be confused with substring ⟨A,B,C,D⟩{displaystyle langle A,B,C,Drangle } which can be derived from the above string ⟨A,B,C,D,E,F⟩{displaystyle langle A,B,C,D,E,Frangle } by deleting substring ⟨E,F⟩{displaystyle langle E,Frangle }. The substring is a refinement of the subsequence.

The list of all subsequences for the word "apple" would be "a, ap, al, ae, app, apl, ape, ale, appl, appe, aple, apple, p, pp, pl, pe, ppl, ppe, ple, pple, l, le, e".

Common subsequence

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

X=⟨A,C,B,D,E,G,C,E,D,B,G⟩{displaystyle X=langle A,C,B,D,E,G,C,E,D,B,Grangle } and

Y=⟨B,E,G,C,F,E,U,B,K⟩{displaystyle Y=langle B,E,G,C,F,E,U,B,Krangle }

then a common subsequence of X and Y could be

Z=⟨B,E,E⟩.{displaystyle Z=langle B,E,Erangle .}

This would not be the longest common subsequence, since Z only has length 3, and the common subsequence ⟨B,E,E,B⟩{displaystyle langle B,E,E,Brangle } has length 4. The longest common subsequence of X and Y is ⟨B,E,G,C,E,B⟩{displaystyle langle B,E,G,C,E,Brangle }.

Applications

Subsequences have applications to computer science,^[1] especially in the discipline of bioinformatics, where computers are used to compare, analyze, and store DNA, RNA, and protein sequences.

Take two sequences of DNA containing 37 elements, say:

SEQ₁ = ACGGTGTCGTGCTATGCTGATGCTGACTTATATGCTA

SEQ₂ = CGTTCGGCTATCGTACGTTCTATTCTATGATTTCTAA

The longest common subsequence of sequences 1 and 2 is:

LCS_(SEQ1,SEQ2) = CGTTCGGCTATGCTTCTACTTATTCTA

This can be illustrated by highlighting the 27 elements of the longest common subsequence into the initial sequences:

SEQ₁ = ACGGTGTCGTGCTATGCTGATGCTGACTTATATGCTA

SEQ₂ = CGTTCGGCTATCGTACGTTCTATTCTATGATTTCTAA

Another way to show this is to align the two sequences, i.e., to position elements of the longest common subsequence in a same column (indicated by the vertical bar) and to introduce a special character (here, a dash) in one sequence when two elements in the same column differ:

SEQ₁ = ACGGTGTCGTGCTAT-G--C-TGATGCTGA--CT-T-ATATG-CTA-

        | || ||| ||||| |  | |  | || |  || | || |  |||

SEQ₂ = -C-GT-TCG-GCTATCGTACGT--T-CT-ATTCTATGAT-T-TCTAA

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

Theorems

• Every infinite sequence of real numbers has an infinite monotone subsequence (This is a lemma used in the proof of the Bolzano–Weierstrass theorem).


• Every infinite bounded sequence in Rⁿ has a convergent subsequence (This is the Bolzano–Weierstrass theorem).


• For all integers r and s, every finite sequence of length at least (r − 1)(s − 1) + 1 contains a monotonically increasing subsequence of length r or a monotonically decreasing subsequence of length s (This is the Erdős–Szekeres theorem).

See also

• 
  Subsequential limit - the limit of some subsequence.


• Limit superior and limit inferior


• Longest increasing subsequence problem

Notes

This article incorporates material from subsequence on PlanetMath, which is licensed under the Creative Commons Attribution/Share-Alike License.