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 is the body of Knowledge and Academic discipline that studies such concepts as Quantity, Structure, Space and In Mathematics, a sequence is an ordered list of objects (or events

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.

Contents 1 Example 2 Applications 3 Substring vs. subsequence 4 See also 5 References

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 problem (LCS is finding the longest Subsequence common to all sequences in a set of sequences (often just two 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 (or computing science) is the study and the Science of the theoretical foundations of Information and Computation and their Bioinformatics is the application of information technology to the field of molecular biology Deoxyribonucleic acid ( DNA) is a Nucleic acid that contains the genetic instructions used in the development and functioning of all known

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. Adenine is a Purine with a variety of roles in Biochemistry including Cellular respiration, in the form of both the energy-rich Adenosine Guanine is one of the five main Nucleobases found in the Nucleic acids DNA and RNA, the others being Adenine, Cytosine, Cytosine is one of the five main bases found in DNA and RNA. It is a Pyrimidine derivative with a Heterocyclic Aromatic ring Thymine is one of the four bases in the Nucleic acid of DNA that make up the letters ATGC

Substring 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. In Computer programming and some branches of Mathematics, a string is an ordered Sequence of Symbols. A subsequence, substring, prefix or suffix of a string is a subset of the symbols in a string where the order of the elements is preserved 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 opposite is not true. ^[1]

See also

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

References

1. ^ Gusfield, Dan [1997] (1999). In Mathematics, a subsequential limit of a Sequence is the limit of some Subsequence. In Mathematics, the limit inferior and limit superior (also called infimum limit and supremum limit, or liminf and limsup The longest common subsequence problem (LCS is finding the longest Subsequence common to all sequences in a set of sequences (often just two The longest increasing subsequence problem is to find the Longest increasing subsequence of a given sequence In Mathematics, the Erdős–Szekeres theorem is a finitary result which makes precise one of the corollaries of Ramsey's theorem. Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology. USA: Cambridge University Press, 4. ISBN 0-521-58519-8.  

This article incorporates material from subsequence on PlanetMath, which is licensed under the GFDL. PlanetMath is a free, collaborative online Mathematics Encyclopedia.

---

© 2009 citizendia.org; parts available under the terms of GNU Free Documentation License, from http://en.wikipedia.org
Dapyx Software network: MP3 Explorer | Ebook Manager | Zenithic