Delsekvens

Delsekvens er, i matematikk og informatikk, en sekvens som kan dannes fra en annen sekvens ved å fjerne noen elementer uten å endre rekkefølgen til de gjenværende elementene. Formalt: Gitt en sekvens S = (s1, s2, ..., sn), er en delsekvens T = (t1, t2, ..., tk) en delsekvens hvis det finnes indekser 1 ≤ i1 < i2 < ... < ik ≤ n slik at tj = s_{ij} for alle j. Den tomme sekvensen er også en delsekvens av enhver sekvens.

Eksempel: Fra S = (a, b, c, d) er (a, c, d) en delsekvens, mens (a, d) er en annen delsekvens. En delsekvens der de valgte elementene er påfølgende i originalrekken kalles ofte en kontinuerlig delsekvens (eller delstreng i visse sammenhenger), for eksempel (b, c) fra S.

Tilknyttede egenskaper og tellingsgrunnlag: Antallet delsekvenser av en lengde-n sekvens er 2^n, siden hvert element enten tas med eller ikke. Antall delsekvenser av lengde k er binomialkoeffisienten C(n, k). En viktig spesialdel er lengste felles delsekvens (longest common subsequence, LCS), som er den lengste delsekvensen som er felles for to eller flere sekvenser, og som brukes i algoritmer og bioinformatikk.

Bruksområder: Delsekvenser brukes i combinatorikk og algoritmer, tekstanalyse, mønstergjenkjenning og biologi (for eksempel DNA- og proteinsekvenser). De hjelper til med å studere struktur, likhet og mønster i data der rekkefølgen av elementer er betydningsfull.