subsekuen

Subsekuen, often called subsequence in English, is a concept in mathematics and computer science describing a sequence derived from another by deleting zero or more elements without changing the order of the remaining elements. More formally, if a1, a2, ..., an is a finite sequence, then any sequence b1, b2, ..., bk with k between 0 and n is a subsekuen if there exist indices i1 < i2 < ... < ik such that bj = a_ij for all j.

A contiguous subsekuen, sometimes called a substring or a subarray depending on data type, requires that the selected elements come from consecutive positions in the original sequence. For example, from 3, 1, 4, 1, 5, the subsekuen 3, 4, 5 (indices 1, 3, 5) is valid, while 3, 4 (indices 1 and 3) is also a subsekuen, but 3, 1, 4 (indices 1–3) is a contiguous subsekuen and thus a substring of the sequence.

The number of subsekuens of an n-element sequence is 2^n, including the empty subsekuen and the original sequence. Common variants include increasing subsekuens and the longest common subsekuen problem, which are central in algorithm design and combinatorics.

Uses include algorithm design, such as dynamic programming for the longest increasing subsekuen and the longest common subsekuen, as well as applications in bioinformatics, data comparison, and version control.

See also subsequence, supersequence, longest common subsequence.