Delfølge

En delfølge er i matematik en talfølge som kan afledes af en anden talfølge ved at fjerne nogle af elementerne uden at ændre rækkefølgen af de tilbageværende elementer. For eksempel er talfølgen $⟨A,B,D⟩$ en delfølge af $⟨A,B,C,D,E,F⟩$ som er fremkommet ved at fjerne elementerne $C$, $E$ og $F$.

Fælles delfølge

Hvis X og Y er to talfølger, siges talfølgen Z at være en fælles delfølge af X og Y, hvis Z er en delfølge af både X and Y. For eksempel, hvis

$X=⟨A,C,B,D,E,G,C,E,D,B,G⟩$ og

$Y=⟨B,E,G,C,F,E,U,B,K⟩$

så vil en fælles delfølge af X og Y være

$Z=⟨B,E,E⟩.$

Det vil ikke være den længste fælles delfølge, da Z kun 3 elementer, og den fælles delfølge $⟨B,E,E,B⟩$ har længden 4. Den længste fælles delfølge af X og Y er $⟨B,E,G,C,E,B⟩$.

Anvendelser

Delfølger har anvendelser i datalogi, specielt inden for bioinformatik hvor computere bruges til at sammenligne, analysere og gemme strenge af DNA, RNA og proteiner.

Tag for eksempler to følger af DNA med 37 elementer:

SEQ₁ = ACGGTGTCGTGCTATGCTGATGCTGACTTATATGCTA

SEQ₂ = CGTTCGGCTATCGTACGTTCTATTCTATGATTTCTAA

Den længste fælles delfølge (LCS = Longest Common Subsequence) af følgerne SEQ₁ og SEQ₂ er:

LCS_(SEQ1,SEQ2) = CGTTCGGCTATGCTTCTACTTATTCTA

Dette kan illustreres ved at fremhæve de 27 elementer i den længste fælles delfølge:

SEQ₁ = ASkabelon:Font colorGSkabelon:Font colorGSkabelon:Font colorTSkabelon:Font colorGASkabelon:Font colorGSkabelon:Font colorGSkabelon:Font colorASkabelon:Font colorGSkabelon:Font color

SEQ₂ = Skabelon:Font colorCSkabelon:Font colorTASkabelon:Font colorGSkabelon:Font colorTTSkabelon:Font colorASkabelon:Font colorGSkabelon:Font colorTSkabelon:Font colorA

En anden måde at vise dette er at justere de to følger så elementer i den længste fælles delfølge er placeret under hinanden (markeret med en lodret streg) og introducere et særligt tegn (her en vandret streg) i en følge hvor to elementer under hinanden er forskellige:

SEQ₁ = ACGGTGTCGTGCTAT-G--C-TGATGCTGA--CT-T-ATATG-CTA-

        | || ||| ||||| |  | |  | || |  || | || |  |||

SEQ₂ = -C-GT-TCG-GCTATCGTACGT--T-CT-ATTCTATGAT-T-TCTAA

Delfølger bruges til at bestemme hvor ensartede to stykker DNA er ved at bruge rækkefølgen af DNA-baserne: adenin (A), guanin (G), cytosin (C) og thymin (T).

Sætninger

• Enhver uendelig følge af reelle tal har en uendelig monoton delfølge. (Dette bruges i beviset for Bolzano–Weierstrass' sætning).
• Enhver begrænset uendelig reel talfølge har en konvergent delfølge. (Dette er Bolzano–Weierstrass' sætning).
• For alle heltal r og s gælder at enhver talfølge med en længde på mindst (r − 1)(s − 1) + 1 indeholder en monotont voksende delfølge med længden r eller en monotont aftagende delfølge med længden s. (Dette er Erdős–Szekeres' sætning).