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\; =\; \backslash langle\; A,C,B,D,E,G,C,E,D,B,G\; \backslash rangle\; \backslash qquad\; \backslash text\{\; and\}$$

$$Y\; =\; \backslash langle\; B,E,G,J,C,F,E,K,B\; \backslash rangle\; \backslash qquad\; \backslash text\{\; and\}$$

$$Z\; =\; \backslash langle\; B,E,E\; \backslash rangle.$$

then $Z$ is said to be a common subsequence of $X$ and $Y.$

This would {{em|not}} be the longest common subsequence, since $Z$ only has length 3, and the common subsequence $\backslash langle\; B,E,E,B\; \backslash rangle$ has length 4. The longest common subsequence of $X$ and $Y$ is $\backslash langle\; B,E,G,C,E,B\; \backslash rangle.$

Subsequences have applications to computer science,In computer science, string is often used as a synonym for sequence, but it is important to note that substring and subsequence are not synonyms. Substrings are consecutive parts of a string, while subsequences need not be. This means that a substring of a string is always a subsequence of the string, but a subsequence of a string is not always a substring of the string, see: {{cite book | last = Gusfield | first = Dan | orig-year = 1997 | year = 1999 | title = Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology | publisher = Cambridge University Press | location = USA | isbn = 0-521-58519-8 | pages = 4}} 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₁ = A{{font color|red|CG}}G{{font color|red|T}}G{{font color|red|TCG}}T{{font color|red|GCTATGCT}}GA{{font color|red|T}}G{{font color|red|CT}}G{{font color|red|ACTTAT}}A{{font color|red|T}}G{{font color|red|CTA}}

:SEQ₂ = {{font color|red|CGTTCGGCTAT}}C{{font color|red|G}}TA{{font color|red|C}}G{{font color|red|TTCTA}}TT{{font color|red|CT}}A{{font color|red|T}}G{{font color|red|ATT}}T{{font color|red|CTA}}A

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:

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

• 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 $\backslash R^n$ 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$ {{em|or}} a monotonically decreasing subsequence of length $s$ (This is the Erdős–Szekeres theorem).
• A metric space $(X,d)$ is compact if every sequence in $X$ has a convergent subsequence whose limit is in $X$.

• {{annotated link|Subsequential limit}}
• {{annotated link|Limit superior and limit inferior}}
• {{annotated link|Longest increasing subsequence problem}}

{{reflist}}

{{reflist|group=note}}

{{PlanetMath attribution|id=3300|title=subsequence}}

Category:Elementary mathematics

Category:Sequences and series