This article has multiple issues. Please helpimprove it or discuss these issues on thetalk page.(Learn how and when to remove these messages) This article includes a list ofgeneral references, butit lacks sufficient correspondinginline citations. Please help toimprove this article byintroducing more precise citations.(November 2018) (Learn how and when to remove this message) This articleneeds additional citations forverification. Please helpimprove this article byadding citations to reliable sources. Unsourced material may be challenged and removed. Find sources: "Subsequence" – news ·newspapers ·books ·scholar ·JSTOR(November 2018) (Learn how and when to remove this message) (Learn how and when to remove this message)

Inmathematics, asubsequence of a givensequence is a sequence that can be derived from the given sequence by deleting some or no elements without changing the order of the remaining elements. For example, the sequence${\displaystyle ⟨A,B,D⟩}$ is a subsequence of${\displaystyle ⟨A,B,C,D,E,F⟩}$ obtained after removal of elements${\displaystyle C,}$${\displaystyle E,}$ and${\displaystyle F.}$ The relation of one sequence being the subsequence of another is apartial order.

Subsequences can contain consecutive elements which were not consecutive in the original sequence. A subsequence which consists of a consecutive run of elements from the original sequence, such as${\displaystyle ⟨B,C,D⟩,}$ from${\displaystyle ⟨A,B,C,D,E,F⟩,}$ is asubstring. 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).

Given two sequences${\displaystyle X}$ and${\displaystyle Y,}$ a sequence${\displaystyle Z}$ is said to be acommon subsequence of${\displaystyle X}$ and${\displaystyle Y,}$ if${\displaystyle Z}$ is a subsequence of both${\displaystyle X}$ and${\displaystyle Y.}$ For example, if$${\displaystyle X=⟨A,C,B,D,E,G,C,E,D,B,G⟩\text{ and}}$$$${\displaystyle Y=⟨B,E,G,J,C,F,E,K,B⟩\text{ and}}$$$${\displaystyle Z=⟨B,E,E⟩.}$$then${\displaystyle Z}$ is said to be a common subsequence of${\displaystyle X}$ and${\displaystyle Y.}$

This wouldnot be thelongest common subsequence, since${\displaystyle Z}$ only has length 3, and the common subsequence${\displaystyle ⟨B,E,E,B⟩}$ has length 4. The longest common subsequence of${\displaystyle X}$ and${\displaystyle Y}$ is${\displaystyle ⟨B,E,G,C,E,B⟩.}$

Subsequences have applications tocomputer science,^[1] especially in the discipline ofbioinformatics, where computers are used to compare, analyze, and storeDNA,RNA, andprotein 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 toalign 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:

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 andthymine.

• Every infinite sequence ofreal numbers has an infinitemonotone subsequence. (This is a lemma used in theproof of the Bolzano–Weierstrass theorem.)
• Every infinitebounded sequence in${\displaystyle {\mathbb{R}}^n}$ has aconvergent subsequence. (This is theBolzano–Weierstrass theorem.)
• For allintegers${\displaystyle r}$ and${\displaystyle s,}$ every finite sequence of length at least${\displaystyle (r-1)(s-1)+1}$ contains a monotonically increasing subsequence of length ${\displaystyle r}$or a monotonically decreasing subsequence of length ${\displaystyle s}$. (This is theErdős–Szekeres theorem.)
• A metric space${\displaystyle (X,d)}$ is compact if every sequence in${\displaystyle X}$ has a convergent subsequence whose limit is in${\displaystyle X}$.

• Subsequential limit – Limit of some subsequence
• Limit superior and limit inferior – Bounds of a sequencePages displaying short descriptions of redirect targets
• Longest increasing subsequence problem – Computer science problemPages displaying short descriptions of redirect targets

This article incorporates material from subsequence onPlanetMath, which is licensed under theCreative Commons Attribution/Share-Alike License.

• Elementary mathematics
• Sequences and series

• Articles with short description
• Short description is different from Wikidata
• Articles lacking in-text citations from November 2018
• All articles lacking in-text citations
• Articles needing additional references from November 2018
• All articles needing additional references
• Articles with multiple maintenance issues
• Pages displaying short descriptions of redirect targets via Module:Annotated link
• Wikipedia articles incorporating text from PlanetMath