Subsequence

In mathematics, a subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements. For example, the sequence ⟨ A , B , D ⟩ {displaystyle langle A,B,D angle } is a subsequence of ⟨ A , B , C , D , E , F ⟩ {displaystyle langle A,B,C,D,E,F angle } obtained after removal of elements C {displaystyle C} , E {displaystyle E} , and F {displaystyle F} . The relation of one sequence being the subsequence of another is a preorder. In mathematics, a subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements. For example, the sequence ⟨ A , B , D ⟩ {displaystyle langle A,B,D angle } is a subsequence of ⟨ A , B , C , D , E , F ⟩ {displaystyle langle A,B,C,D,E,F angle } obtained after removal of elements C {displaystyle C} , E {displaystyle E} , and F {displaystyle F} . The relation of one sequence being the subsequence of another is a preorder. The subsequence should not be confused with substring ⟨ A , B , C , D ⟩ {displaystyle langle A,B,C,D angle } which can be derived from the above string ⟨ A , B , C , D , E , F ⟩ {displaystyle langle A,B,C,D,E,F angle } by deleting substring ⟨ E , F ⟩ {displaystyle langle E,F angle } . The substring is a refinement of the subsequence. The list of all subsequences for the word 'apple' would be 'a', 'ap', 'al', 'ae', 'app', 'apl', 'ape', 'ale', 'appl', 'appe', 'aple', 'apple', 'p', 'pp', 'pl', 'pe', 'ppl', 'ppe', 'ple', 'pple', 'l', 'le', 'e', ''. Given two sequences X and Y, a sequence Z is said to be a common subsequence of X and Y, if Z is a subsequence of both X and Y. For example, if then Z {displaystyle Z} is said to be a common subsequence of X and Y. This would not be the longest common subsequence, since Z only has length 3, and the common subsequence ⟨ B , E , E , B ⟩ {displaystyle langle B,E,E,B angle } has length 4. The longest common subsequence of X and Y is ⟨ B , E , G , C , E , B ⟩ {displaystyle langle B,E,G,C,E,B angle } . Subsequences have applications to computer science, especially in the discipline of bioinformatics, where computers are used to compare, analyze, and store DNA, RNA, and protein sequences.