?
О числе реконструкций по подсловам в бинарном алфавите при наложении на один символ
Рассмотрена задача получения точных оценок числа реконструкций для слов над бинарным
алфавитом. Подслова различной длины из заданного множества соединяются методом нало-
жения концевых символов. Соединять можно только такую пару подслов, у которых последний
символ первого подслова совпадает с первым символом второго. При наложении пары подходя-
щих подслов на один символ из двух одинаковых символов (в конце первого и в начале второго
подслова) в реконструкцию входит только один. Предложен подход, основанный на рассмотре-
нии усеченных подслов, состоящих из префикса и суффикса данного подслова, имеющих длину
один. При построении реконструкции вместо самих подслов из заданного множества соединя-
ются усеченные слова вида «00», «01», «10» и «11». Число реконструкций находится в предпо-
ложении, что каждое из усеченных подслов соответствует уникальному подслову в заданном
множестве подслов. В результате при соединении слов «00» и «00» возможны две реконструк-
ции, соответствующие соединению исходных подслов «0x0» и «0y0» в «0x0y0» и «0y0x0», где x
и y — различные последовательности символов бинарного алфавита, одна из которых может
быть пустой (но не обе одновременно).
Такой подход позволил определить условия существования реконструкции по заданному мно-
жеству подслов различной длины. Показано, при каких условиях, касающихся количества усе-
ченных подслов каждого вида, реконструкция невозможна. Например, невозможна реконструк-
ция по множеству подслов, содержащему только подслова вида «00» и «11». Также невозможно
соединить все подслова заданного множества, если число усеченных подслов вида «01» и «10»
отличается больше, чем на один. Для различных случаев, допускающих полную реконструкцию,
получены формулы точного числа реконструкций. Точное число реконструкций зависит от на-
личия или отсутствия подслов, соответствующих усеченным подсловам каждого вида.
Поскольку возможность реконструкции главным образом зависит от соотношения числа под-
слов вида «01» и «10», то отдельно была рассмотрена модель с возможностью инверсий слов.
Предполагается, что множество подслов для реконструкции содержит только слова вида вида
«00», «01» «00», Часть слов вида «01» записывается в обратном порядке и становится словами
вида «10». Если слов «01» было четное число, то в «01» преобразуется половина слов «01»,
иначе — половина от ближайшего четного числа. В последнем случае из множества подслов
вида «01» получается два варианта наборов подслов вида «01» и «10», в одном больше подслов «01», в другом — «10». Для каждого случая приведены формулы точного числа реконструкций
при условии уникальности подслов в заданном множестве, а также несимметричности подслов,
порождающих усеченные подслова вида «00» и «11».