134.60.67.135: /* Theorems */

2025-07-01T09:57:56Z

Theorems

New page

{{Short description|Mathematical binary relation}}
{{Multiple issues|
{{more footnotes|date=November 2018}}
{{more citations needed|date=November 2018}}
}}

In [[mathematics]], a '''subsequence''' of a given [[sequence]] 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 <math>\langle A,B,D \rangle</math> is a subsequence of <math>\langle A,B,C,D,E,F \rangle</math> obtained after removal of elements <math>C,</math> <math>E,</math> and <math>F.</math> The relation of one sequence being the subsequence of another is a [[partial 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 <math>\langle B,C,D \rangle,</math> from <math>\langle A,B,C,D,E,F \rangle,</math> 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 ==

Given two sequences <math>X</math> and <math>Y,</math> a sequence <math>Z</math> is said to be a ''common subsequence'' of <math>X</math> and <math>Y,</math> if <math>Z</math> is a subsequence of both <math>X</math> and <math>Y.</math> For example, if
<math display=block>X = \langle A,C,B,D,E,G,C,E,D,B,G \rangle \qquad \text{ and}</math>
<math display=block>Y = \langle B,E,G,J,C,F,E,K,B \rangle \qquad \text{ and}</math>
<math display=block>Z = \langle B,E,E \rangle.</math>
then <math>Z</math> is said to be a common subsequence of <math>X</math> and <math>Y.</math>

This would {{em|not}} be the ''[[Longest-common subsequence problem|longest common subsequence]]'', since <math>Z</math> only has length 3, and the common subsequence <math>\langle B,E,E,B \rangle</math> has length 4. The longest common subsequence of <math>X</math> and <math>Y</math> is <math>\langle B,E,G,C,E,B \rangle.</math>

== Applications ==

Subsequences have applications to [[computer science]],<ref name="substrVsSubseq">In computer science, ''[[string (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}}</ref> 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:

:<samp>SEQ1 = ACGGTGTCGTGCTATGCTGATGCTGACTTATATGCTA</samp>
:<samp>SEQ2 = CGTTCGGCTATCGTACGTTCTATTCTATGATTTCTAA</samp>

The longest common subsequence of sequences 1 and 2 is:

:<samp>LCS(SEQ1,SEQ2) = '''CGTTCGGCTATGCTTCTACTTATTCTA'''</samp>

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

:<samp>SEQ1 = 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}}'''</samp>
:<samp>SEQ2 = '''{{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</samp>

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:
:<samp>SEQ1 = ACGGTGTCGTGCTAT-G--C-TGATGCTGA--CT-T-ATATG-CTA-</samp>
:<samp>        | || ||| ||||| |  | |  | || |  || | || |  ||| </samp>
:<samp>SEQ2 = -C-GT-TCG-GCTATCGTACGT--T-CT-ATTCTATGAT-T-TCTAA</samp>

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 number]]s has an infinite [[Monotone sequence|monotone]] subsequence. (This is a lemma used in the [[Bolzano–Weierstrass theorem#Proof|proof of the Bolzano–Weierstrass theorem]].)
* Every infinite [[bounded sequence]] in <math>\R^n</math> has a [[Limit of a sequence|convergent]] subsequence. (This is the [[Bolzano–Weierstrass theorem]].)
* For all [[integer]]s <math>r</math> and <math>s,</math> every finite sequence of length at least <math>(r - 1)(s - 1) + 1</math> contains a monotonically increasing subsequence of length <math>r</math> {{em|or}} a monotonically decreasing subsequence of length <math>s</math>. (This is the [[Erdős–Szekeres theorem]].)
* A metric space <math>(X,d)</math> is compact if every sequence in <math>X</math> has a convergent subsequence whose limit is in <math>X</math>.

== See also ==

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

== Notes ==

{{reflist}}
{{reflist|group=note}}

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

[[Category:Elementary mathematics]]
[[Category:Sequences and series]]

Subsequence - Revision history

134.60.67.135: /* Theorems */