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 ${\displaystyle \langle A,B,D\rangle }$ en delfølge af ${\displaystyle \langle A,B,C,D,E,F\rangle }$ som er fremkommet ved at fjerne elementerne ${\displaystyle C}$, ${\displaystyle E}$ og ${\displaystyle 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

${\displaystyle X=\langle A,C,B,D,E,G,C,E,D,B,G\rangle }$ og

${\displaystyle Y=\langle B,E,G,C,F,E,U,B,K\rangle }$

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

${\displaystyle Z=\langle B,E,E\rangle .}$

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

Anvendelser

Delfølger har anvendelser i datalogi,^[1] 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₁ = ACGGTGTCGTGCTATGCTGATGCTGACTTATATGCTA

SEQ₂ = CGTTCGGCTATCGTACGTTCTATTCTATGATTTCTAA

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).

Noter

1. ^ I datalogi er streng ofte brugt som et synonym for talfølge, men man skal være opmærksom på at delstreng og delfølge ikke er synonymer. Delstrenge er sammenhængende dele af en streng, hvilket delfølger ikke nødvendigvis er. Det betyder at delstreng af en streng altid er en delfølge af strengen, mens delfølge af en streng ikke altid er en delstreng af strengen, se:Gusfield, Dan (1999) [1997]. Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology. USA: Cambridge University Press. pp. 4. ISBN 0-521-58519-8.