Откуда берется база при подсчете подпоследовательности?

Question

Если последовательность X имеет m символы, затем X имеет 2^m возможные подпоследовательности.

Где находится база (2) откуда взялся?

Источником этого вопроса является следующий абзац:

Нам даны две упорядоченные последовательности символов, и мы хотим найти самую длинную общую подпоследовательность из $X$ и $У$.

Подпоследовательность из $X$ это просто $X$ с удалением некоторых (или, возможно, всех или ни одного) его элементов.Например, одна подпоследовательность из A; B; C; D; E; F; G было бы B; C; E; G.

Длина самой длинной общей подпоследовательности из $X$ и $У$ дает один показатель того, насколько похожи эти две последовательности.Например, если две последовательности являются парами оснований в цепях ДНК , то мы могли бы считать их похожими, если они имеют длинную общую подпоследовательность.

Если $X$ имеет $м$ символы и $У$ имеет $n$ символы, затем $X$ и $У$ иметь $2^млн$ и $2^n$ возможные подпоследовательности соответственно.

Answer 1

Вы можете придумать подпоследовательность $У$ от $X$ как характеристический вектор $\chi_Y$ который имеет $м$ элементы, по одному на элемент $X$.То $я$-й элемент $\chi_Y$ является $1$ если $я$-й элемент $X$ также находится в $У$ и $0$ иначе.

Легко видеть, что это биекция:каждая подпоследовательность $У$ имеет отчетливый характерный вектор $\chi_Y$, и каждый характеристический вектор $\chi_Y$ связан с определенной последовательностью $У$.

Это означает, что число подпоследовательностей $У$ равно числу векторов $\chi_Y$.Поскольку каждый вектор $\chi_Y$ имеет $м$ элементы, каждый из которых может иметь один из $2$ возможные значения, это число равно $2^млн$.

Конкретный пример последовательности $X$, подпоследовательность $У$, и его характерный вектор $\chi_Y$ заключается в следующем: