Sous-séquence

En mathématiques , une sous-suite d'une suite donnée est une suite que l'on peut obtenir de cette suite en supprimant certains éléments, voire aucun, sans modifier l'ordre des éléments restants. Par exemple, la suite est une sous-suite de obtenue après suppression de certains éléments . La relation entre deux suites est une relation d' ordre partiel .

Les sous-séquences peuvent contenir des éléments consécutifs qui ne l'étaient pas dans la séquence originale. Une sous-séquence constituée d'une suite d'éléments consécutifs de la séquence originale, comme « from » , est une sous-chaîne . La sous-chaîne est un raffinement de la sous-séquence.

La liste de toutes les sous-séquences du mot « apple » serait « a », « ap », « al », « ae », « app », « apl », « ape », « ale », « appl », « appe », « aple », « apple », « p », « pp », « pl », « pe », « ppl », « ppe », « ple », « pple », « l », « le » , « e », « » ( chaîne vide ).

Étant donné deux suites A et B, une suite A est dite sous-suite commune à A et B si A est une sous-suite des deux suites . Par exemple, si A = B, alors A est dite sous-suite commune à A et B.

Ce ne serait pas la plus longue sous-séquence commune , car elle n'a qu'une longueur de 3, alors que la sous-séquence commune a une longueur de 4. La plus longue sous-séquence commune de et est

Les sous-séquences ont des applications en informatique , notamment dans la discipline de la bioinformatique , où les ordinateurs sont utilisés pour comparer, analyser et stocker des séquences d'ADN , d'ARN et de protéines .

Prenons deux séquences d'ADN contenant 37 éléments, par exemple :

SEQ ₁ = ACGGTGTCGTGCTAGCTGATGCTGACTTATATGCTA

SEQ ₂ = CGTTCGGCTATCGTACGTTCTATTCTATGATTTCTAA

La plus longue sous-séquence commune aux séquences 1 et 2 est :

LCS _{(SEQ 1 ,SEQ 2 )} = CGTTCGGCTATGCTTCTACTTATTCTA

Ceci peut être illustré en mettant en évidence les 27 éléments de la plus longue sous-séquence commune dans les séquences initiales :

SEQ ₁ = A CG G T G TCG T GCTATGCT GA T G CT G ACTTAT A T G CTA

SEQ ₂ = CGTTCGGCTAT C G TA C G TTCTA TT CT A T G ATT T CTA A

Une autre façon de le montrer consiste à aligner les deux séquences, c'est-à-dire à positionner les éléments de la plus longue sous-séquence commune dans une même colonne (indiquée par la barre verticale) et à introduire un caractère spécial (ici, un tiret) pour le remplissage des sous-séquences vides apparues :

SÉQUENCE ₁ = ACGGTGTCGTGCTAT-G--C-TGATGCTGA--CT-T-ATATG-CTA-

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

SÉQUENCE ₂ = -C-GT-TCG-GCTATCGTACGT--T-CT-ATTCTATGAT-T-TCTAA

Des sous-séquences sont utilisées pour déterminer le degré de similarité entre les deux brins d'ADN, en utilisant les bases de l'ADN : adénine , guanine , cytosine et thymine .

• Toute suite infinie de nombres réels possède une sous-suite monotone infinie . (Il s'agit d'un lemme utilisé dans la démonstration du théorème de Bolzano-Weierstrass .)
• Toute suite bornée infinie possède une sous-suite convergente . (C'est le théorème de Bolzano-Weierstrass .)
• Pour tout entier n et toute suite finie de longueur au moins n, il existe une sous-suite croissante de longueur n ou une sous-suite décroissante de longueur n . (C'est le théorème d'Erdős-Szekeres .)
• Un espace métrique est compact si toute suite dans possède une sous-suite convergente dont la limite est dans .