Subsequence

Subsequence

In mathematics, a subsequence of some sequence is a new sequence which is formed from the original sequence by deleting some of the elements without disturbing the relative positions of the remaining elements.

Formally, suppose that "X" is a set and that ("a""k")"k" ∈ "K" is a sequence in "X", where "K" = {1,2,3,...,"n"} if ("a""k") is a finite sequence and "K" = N if ("a""k") is an infinite sequence. Then, a subsequence of ("ak") is a sequence of the form (a_{n_r}) where ("nr") is a strictly increasing sequence in the index set "K".

Example

As an example,: < B,C,D,G > is a subsequence of: < A,C,B,D,E,G,C,E,D,B,G > ,with corresponding index sequence <3,7,9,11>.

Given two sequences "X" and "Y", a sequence "G" is said to be a "common subsequence" of "X" and "Y", if "G" is a subsequence of both "X" and "Y". For example, if: X = < A,C,B,D,E,G,C,E,D,B,G > and: Y = < B,E,G,C,F,E,U,B,K > then common subsequence of "X" and "Y" could be: G = < B,E,E >

This would "not" be the "longest common subsequence", since "G" only has length 3, and the common subsequence < B,E,E,B > has length 4. The longest common subsequence of "X" and "Y" is < B,E,G,C,E,B >.

Applications

Subsequences have applications to computer science, especially in the discipline of Bioinformatics, where computers are used to compare, analyze, and store DNA strands.

Take two strands of DNA, say :

ORG1 = ACGGTGTCGTGCTATGCTGATGCTGACTTATATGCTA
ORG2 = CGTTCGGCTATCGTACGTTCTATTCTATGATTTCTAA

Subsequences are used to determine how similar the two strands of DNA are, using the DNA bases: adenine, guanine, cytosine and thymine.

ubstring vs. subsequence

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 the subsequence of a string is not always a substring of the string. [cite book | last = Gusfield | first = Dan | origyear = 1997 | year = 1999 | title = Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology | publisher = Cambridge University Press | location = USA | id = ISBN 0-521-58519-8 | pages = 4]

ee also

*subsequential limit
*limit superior and limit inferior
*longest common subsequence problem
*longest increasing subsequence problem
*Erdős–Szekeres theorem

References


Wikimedia Foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Look at other dictionaries:

  • Subsequence — Sub se*quence, Subsequency Sub se*quen*cy, n. The act or state of following; opposed to precedence. [1913 Webster] …   The Collaborative International Dictionary of English

  • subséquence — [sybsekɑ̃s] n. f. ÉTYM. 1834; de subséquent. ❖ ♦ Didact. Caractère de ce qui se produit après quelque chose, de ce qui est subséquent …   Encyclopédie Universelle

  • subsequence — (n.) c.1500; see SUBSEQUENT (Cf. subsequent) + ENCE (Cf. ence) …   Etymology dictionary

  • subsequence — [sub′si kwəns, sub′sikwens΄; ] for 3 [ sub′sē΄kwəns] n. [ML subsequentia] 1. the fact or condition of being subsequent 2. a subsequent happening 3. Math. a sequence within a sequence …   English World dictionary

  • subsequence counter — mikrokomandų skaitiklis statusas T sritis automatika atitikmenys: angl. microinstruction counter; microprogram counter; subsequence counter vok. Mikrobefehlszähler, m rus. счетчик микрокоманд, m pranc. compteur de micro temps, m; compteur de sous …   Automatikos terminų žodynas

  • subsequence — I. noun Date: circa 1500 the quality or state of being subsequent; also a subsequent event II. noun Date: 1908 a mathematical sequence that is part of another sequence …   New Collegiate Dictionary

  • subsequence — subsequence1 /sub si kweuhns/, n. 1. the state or fact of being subsequent. 2. a subsequent occurrence, event, etc.; sequel. [1490 1500; SUBSEQU(ENT) + ENCE] subsequence2 /sub see kweuhns/, n. Math. a sequence obtained from a given sequence by… …   Universalium

  • subsequence — noun a) A subsequent act or thing; a sequel b) A sequence that is contained within a larger one …   Wiktionary

  • subsequence — subsequence1 [ sʌbsɪkw(ə)ns] noun formal the state of following or being a consequence of something. subsequence2 [ sʌbˌsi:kw(ə)ns] noun a sequence contained in or derived from another sequence …   English new terms dictionary

  • subsequence — sub•se•quence [[t]ˈsʌb sɪ kwəns[/t]] n. 1) the state or fact of being subsequent 2) a subsequent occurrence, event, etc.; sequel • Etymology: 1490–1500 …   From formal English to slang

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”