- Subsequence
In

mathematics , a**subsequence**of somesequence 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 ("a_{k}") is a sequence of the form $(a\_\{n\_r\})$ where ("n_{r}") 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 ofBioinformatics , where computers are used to compare, analyze, and storeDNA strands.Take two strands of DNA, say :

ORG

_{1}=`ACGGTGTCGTGCTATGCTGATGCTGACTTATATGCTA`

ORG_{2}=`CGTTCGGCTATCGTACGTTCTATTCTATGATTTCTAA`Subsequences are used to determine how similar the two strands of DNA are, using the DNA bases:

adenine ,guanine ,cytosine andthymine .**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**— 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**subsequence**— noun 1. /ˈsʌbsəkwəns/ (say subsuhkwuhns) the state or fact of being subsequent. 2. /ˈsʌbsəkwəns/ (say subsuhkwuhns) that which is subsequent; sequel. 3. /ˈsʌbˌsikwəns/ (say sub.seekwuhns) Mathematics a sequence whose elements belong to and retain … Australian English dictionary