In der Mathematik ist eine Subfolge eine Folge, die aus einer anderen Folge durch das Löschen einiger Elemente abgeleitet werden kann, ohne die Ordnung der restlichen Elemente zu ändern. Zum Beispiel ist die Folge eine Subfolge dessen.

In Anbetracht zwei Folgen X und Y, wie man sagt, ist eine Folge G eine allgemeine Subfolge X und Y, wenn G eine Subfolge sowohl X als auch Y ist. Zum Beispiel, wenn

: und

dann konnte eine allgemeine Subfolge X und Y sein

Das würde nicht die längste allgemeine Subfolge sein, da G nur Länge 3 hat, und die allgemeine Subfolge Länge 4 hat. Die längste allgemeine Subfolge X und Y ist.

Anwendungen

Subfolgen haben Anwendungen auf die Informatik besonders in der Disziplin von Bioinformatics, wo Computer verwendet werden, um DNA-Ufer zu vergleichen, zu analysieren, und zu versorgen.

Nehmen Sie zwei Ufer der DNA, sagen Sie:

:ORG =

:ORG =.

Subfolgen werden verwendet, um zu bestimmen, wie ähnlich die zwei Ufer der DNA mit den DNA-Basen sind: Adenin, guanine, cytosine und thymine.

Teilkette gegen die Subfolge

In der Informatik wird Schnur häufig als ein Synonym für die Folge verwendet, aber es ist wichtig zu bemerken, dass Teilkette und Subfolge nicht Synonyme sind. Teilketten sind Konsekutivteile einer Schnur, während Subfolgen nicht zu sein brauchen. Das bedeutet, dass eine Teilkette einer Schnur immer eine Subfolge der Schnur ist, aber eine Subfolge einer Schnur ist nicht immer eine Teilkette der Schnur.

Siehe auch

• Subfolgende Grenze
• Beschränken Sie höher und beschränken Sie untergeordneten
• Längstes zunehmendes Subfolge-Problem
• Erdős-Szekeres Lehrsatz