Woher kommt die Basis in einer Teilsequenzzählung?

Question

Wenn Reihenfolge X hat m Symbole also X hat 2^M mögliche Folgefolgen.

Woher kommt die Basis (2) komme aus?

Der Ursprung dieser Frage ist der folgende Absatz:

Wir erhalten zwei geordnete Folgen von Symbolen und möchten eine längste gemeinsame Teilfolge von finden $X$ Und $Y$.

Eine Folge von $X$ ist nur $X$ mit einigen (oder möglicherweise allen oder nicht) seiner Elemente entfernt.Zum Beispiel eine Teilfolge von A; B; C; D; E; F; G wäre B; C; E; G.

Die Länge einer längsten häufigen Untersequenz von $X$ Und $Y$ gibt ein Maß dafür an, wie ähnlich diese beiden Sequenzen sind.Wenn beispielsweise die beiden Sequenzen Basispaare in DNA -Strängen sind, können wir sie als ähnlich betrachten, wenn sie eine lange gemeinsame Subsequenz haben.

Wenn $X$ hat $m$ Symbole und $Y$ hat $n$ Symbole also $X$ Und $Y$ haben 2^m$ Und $2^n$ mögliche Untersequenzen.

Answer 1

Sie können sich eine Teilsequenz vorstellen $Y$ von $X$ als charakteristischer Vektor $\chi_Y$ das hat $m$ Elemente, eines pro Element von $X$.Der $i$-tes Element von $\chi_Y$ Ist $1$ wenn die $i$-tes Element von $X$ ist auch dabei $Y$ Und $0$ ansonsten.

Es ist leicht zu erkennen, dass es sich hierbei um eine Bijektion handelt:jede Teilfolge $Y$ hat einen ausgeprägten charakteristischen Vektor $\chi_Y$, und jeder charakteristische Vektor $\chi_Y$ ist einer bestimmten Sequenz zugeordnet $Y$.

Dies bedeutet, dass die Anzahl der Teilsequenzen $Y$ ist gleich der Anzahl der Vektoren $\chi_Y$.Da jeder Vektor $\chi_Y$ hat $m$ Elemente, von denen jedes eines haben kann $2$ Mögliche Werte ist diese Zahl 2^m$.

Ein konkretes Beispiel einer Sequenz $X$, eine Teilfolge $Y$, und sein charakteristischer Vektor $\chi_Y$ ist das Folgende: