Khanh at 04:37, 22 November 2021

2021-11-22T04:37:47Z

Khanh: Created page with " 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 o..."

2021-11-22T04:32:37Z

Created page with " 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 o..."

New page

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

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 ''not'' be the ''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, 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:

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

The longest common subsequence of sequences 1 and 2 is:

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

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

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

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

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 <math>\R^n</math> has a convergent subsequence (This is the Bolzano–Weierstrass theorem).
* For all integers <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> ''or'' a monotonically decreasing subsequence of length <math>s</math> (This is the Erdős–Szekeres theorem).

← Older revision		Revision as of 04:37, 22 November 2021
Line 46:		Line 46:
	* Every infinite bounded sequence in <math>\R^n</math> has a convergent subsequence (This is the Bolzano–Weierstrass theorem).		* Every infinite bounded sequence in <math>\R^n</math> has a convergent subsequence (This is the Bolzano–Weierstrass theorem).
	* For all integers <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> ''or'' a monotonically decreasing subsequence of length <math>s</math> (This is the Erdős–Szekeres theorem).		* For all integers <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> ''or'' a monotonically decreasing subsequence of length <math>s</math> (This is the Erdős–Szekeres theorem).
		+
		+	== Licensing ==
		+	Content obtained and/or adapted from:
		+	* [https://en.wikipedia.org/wiki/Subsequence Subsequence, Wikipedia] under a CC BY-SA license

Subsequences - Revision history

Khanh at 04:37, 22 November 2021

Khanh: Created page with " 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 o..."