World Library  
Flag as Inappropriate
Email this Article

Subsequence

Article Id: WHEBN0000236098
Reproduction Date:

Title: Subsequence  
Author: World Heritage Encyclopedia
Language: English
Subject: Substring, Bolzano–Weierstrass theorem, Compact space, Infobox integer sequence, Fermat number
Collection:
Publisher: World Heritage Encyclopedia
Publication
Date:
 

Subsequence

In mathematics, a subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements. For example, the sequence \langle A,B,D \rangle is a subsequence of \langle A,B,C,D,E,F \rangle . They should not be confused with substring which is \langle A,B,C,D \rangle for above string and which is a refinement of subsequence.

Contents

  • Common subsequence 1
  • Applications 2
  • Theorems 3
  • See also 4
  • Notes 5

Common subsequence

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 = \langle A,C,B,D,E,G,C,E,D,B,G \rangle and
Y = \langle B,E,G,C,F,E,U,B,K \rangle

then a common subsequence of X and Y could be

G = \langle B,E,E \rangle.

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

Applications

Subsequences have applications to computer science,[1] 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
and
ORG2 = CGTTCGGCTATCGTACGTTCTATTCTATGATTTCTAA.

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

Theorems

See also

Notes

  1. ^ In computer science,  

This article incorporates material from subsequence on PlanetMath, which is licensed under the Creative Commons Attribution/Share-Alike License.

This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
 
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
 
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.
 


Copyright © World Library Foundation. All rights reserved. eBooks from Project Gutenberg are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.