¿De dónde viene la base en un recuento de subsecuencia?

Question

Si secuencia X tiene m símbolos, entonces X tiene 2^metro posibles subsecuencias.

¿Dónde está la base (2) ¿viene de?

El origen de esta pregunta está en el siguiente párrafo:

Se nos dan dos secuencias ordenadas de símbolos y deseamos encontrar una subsecuencia común más larga de $X$ y $Y$.

una subsecuencia de $X$ es solo $X$ con algunos (o posiblemente todos o ninguno) de sus elementos eliminados.Por ejemplo, una subsecuencia de A; B; C; D; E; F; G sería B; C; E; G.

La longitud de una subsecuencia común más larga de $X$ y $Y$ Da una medida de cuán similares son estas dos secuencias.Por ejemplo, si las dos secuencias son pares de bases en hebras de ADN, entonces podríamos considerarlas similares si tienen una larga subsecuencia común.

Si $X$ tiene $m$ símbolos y $Y$ tiene $n$ símbolos, entonces $X$ y $Y$ tener $2^millones$ y $2^n$ posibles subsecuencias respectivamente.

Answer 1

Puedes pensar en una subsecuencia. $Y$ de $X$ como vector característico $\chi_Y$ que tiene $m$ elementos, uno por elemento de $X$.El $yo$-ésimo elemento de $\chi_Y$ es $1$ Si el $yo$-ésimo elemento de $X$ también está en $Y$ y $0$ de lo contrario.

Es fácil ver que se trata de una biyección:cada subsecuencia $Y$ tiene un vector característico distinto $\chi_Y$, y cada vector característico $\chi_Y$ está asociado a una secuencia distinta $Y$.

Esto significa que el número de subsecuencias $Y$ es igual al número de vectores $\chi_Y$.Dado que cada vector $\chi_Y$ tiene $m$ elementos, cada uno de los cuales puede tener uno de $2$ valores posibles, este número es $2^millones$.

Un ejemplo concreto de una secuencia. $X$, una subsecuencia $Y$, y su vector característico $\chi_Y$ es el siguiente: