Où en est la base, dans une sous-suite qui comptent?

Question

Si la séquence X a m symboles, puis X a 2^m possible de sous-séquences.

Où est la base de l'2) vient-il?

L'origine de cette question est le paragraphe suivant:

Nous nous sommes donné deux séquences ordonnées de symboles, et nous souhaitons trouver une plus longue sous-suite commune de $X$ et $Y$.

Une sous-suite de $X$ est juste $X$ avec certains (ou éventuellement de tous les ou aucun) de ses éléments supprimés.Par exemple, une sous-suite de A; B; C; D; E; F; G serait B; C; E; G.

La longueur d'un plus long commune de la sous-suite d' $X$ et $Y$ donne la mesure de similarité de ces deux séquences sont.Par exemple, si les deux séquences de paires de base dans la Les brins d'ADN, alors on peut considérer qu'elles sont similaires s'ils ont une longue commune de la sous-suite.

Si $X$ a $m$ les symboles et les $Y$ a $n$ symboles, puis $X$ et $Y$ ont $2^m$ et $2^n$ possible de sous-séquences respectivement.

Answer 1

Vous pouvez penser à une sous-suite $Y$ de $X$ comme un vecteur caractéristique $\chi_Y$ qui a $m$ les éléments, un par élément de $X$.L' $i$-ème élément de $\chi_Y$ est $1$ si l' $i$-ème élément de $X$ est également en $Y$ et $0$ sinon.

Il est facile de voir que c'est une bijection:chaque sous-suite $Y$ a une caractéristique distincte de vecteur $\chi_Y$, et chaque vecteur caractéristique $\chi_Y$ est associée à une séquence distincte $Y$.

Cela signifie que le nombre de sous-séquences $Y$ est égal au nombre de vecteurs $\chi_Y$.Depuis chaque vecteur $\chi_Y$ a $m$ éléments, dont chacun peut avoir l'une des $2$ valeurs possibles, ce nombre est $2^m$.

Un exemple concret d'une séquence $X$, une sous-suite $Y$, et son vecteur caractéristique $\chi_Y$ est la suivante: