In mathematics, a subsequence of a given sequence The relation of one sequence being the subsequence of another is a partial order.

is a substring. 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", "" (empty string).

Common subsequence

is said to be a common subsequence

This would be the longest common subsequence has length

Applications

Subsequences have applications to computer science, 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:

1. SEQ1 = ACGGTGTCGTGCTATGCTGATGCTGACTTATATGCTA

2. SEQ2 = CGTTCGGCTATCGTACGTTCTATTCTATGATTTCTAA

The longest common subsequence of sequences 1 and 2 is:

1. LCS(SEQ1,SEQ2) = CGTTCGGCTATGCTTCTACTTATTCTA

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

1. SEQ1 = AGGTGAGGAG

2. SEQ2 = CTAGTTAGTA

Another way to show this is to align the two sequences, that is, 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) for padding of arisen empty subsequences:

1. SEQ1 = ACGGTGTCGTGCTAT-G--C-TGATGCTGA--CT-T-ATATG-CTA-

2. |||||||||||||||||||||||||||

3. SEQ2 = -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 has a convergent subsequence. (This is the Bolzano–Weierstrass theorem.)

• For all integers contains a monotonically increasing subsequence of length a monotonically decreasing subsequence of length. (This is the Erdős–Szekeres theorem.)

• .

See also

• Subsequential limit

• Limit superior and limit inferior

• Longest increasing subsequence

• Longest alternating subsequence

• Longest common subsequence

Notes