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. Mathematics, often abbreviated maths in Commonwealth English and math in American English, is the study of abstraction. ... This is a page about mathematics. ...

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

where (n_r) is a strictly increasing sequence in the index set K.

Example

As an example,

< B,C,D,B >

is a subsequence of

< A,C,B,D,E,G,C,E, D,B,G > ,

with corresponding index sequence <3,7,9,10>.

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. Computer science (academically, CS, CSC or compsci) encompasses a variety of topics that relates to computation, like abstract analysis of algorithms, formal grammars, and subjects such as programming languages, program design, software and computer hardware. ... Bioinformatics or computational biology is the use of techniques from applied mathematics, informatics, statistics, and computer science to solve biological problems. ... Space-filling model of a section of DNA molecule Deoxyribose nucleic acid (DNA) is a nucleic acid that contains the genetic instructions specifying the biological development of all cellular forms of life (and many viruses). ...

Take two strands of DNA, say

ORG₁ = ACGGTGTCGTGCTATGCTGATGCTGACTTATATGCTA
ORG₂ = CGTTCGGCTATCGTACGTTCTATTCTATGATTTCTAA

Subsequences are used to determine how similar the two strands of DNA are, using the DNA bases: adenine, guanine, cytosine and thymine. Structure of Adenine Adenine is one of the two purine nucleobases used in forming nucleotides of the nucleic acids DNA and RNA. In DNA, adenine (A) binds to thymine (T) to assist in stabilizing the nucleic acid structures. ... Guanine (2-amino-6-oxypurine) is one of the four main nucleobases found in nucleic acids (e. ... Cytosine Cytosine is one of the 5 main nucleobases used in storing and transporting genetic information within a cell. ... Thymine Thymine (C5H6N2O2, 2-oxy-4-oxy-5-methylpyrimidine, 2,4-dioxy-5-methylpyrimidine, 5-methyluracil) is one of the bases of the nucleic acid found in DNA. It can base pair with adenine. ...

See also

• subsequential limits
• limsup
• liminf

This article incorporates material from subsequence  (http://planetmath.org/?op=getobj&from=objects&id=3300) on PlanetMath, which is licensed under the GFDL. In mathematics, a subsequential limit is the limit of some subsequence. ... In mathematics, the limit inferior and limit superior of a sequence can be thought of as limiting bounds on the sequence. ... In mathematics, the limit inferior and limit superior of a sequence can be thought of as limiting bounds on the sequence. ... PlanetMath is a free, collaborative, online mathematics encyclopedia. ...