Ну давайте сделаем так.
Значит, во-первых, давайте считать, что ни в
каком выравнивании,
ни в каком выравнивании
[ПИШЕТ НА ДОСКЕ] не бывает ситуации,
когда гэп стоит над гэпом, не бывает вот такого столбика.
Это очень естественное предположение,
потому что на черта сравнивать несуществующие символы.
Мы их сами зачем-то добавили, понятно зачем, — для того чтобы подогнать две
последовательности друг к другу так, чтобы где-то какие-то участки совпали,
но их-то между собой сравнивать нет никакого смысла, абсолютно никакого.
Ну и давайте считать еще дополнительно вот это важное ограничение, которое
нам позволит применить весь арсенал наших замечательных комбинаторных тождеств,
которые мы с вами доказали, — не зря доказывали, что называется,
то есть тождества сработают.
Значит, давайте в качестве второго пункта сделаем следующую оговорку.
Вот представим себе, представим
себе, что есть 2 выравнивания,
которые выглядят следующим образом.
Два выравнивания, одно из которых там что-то что-то,
потом идет какой-то символ «а», идет гэп,
здесь гэп и какой-то символ «б», потом что-то что-то — это одно выравнивание.
Ну скобочки я нарисовал для красоты, просто чтобы их было легко отделить.
Вот какое-то такое выравнивание, и в нем участочек, в котором друг к дружке
примыкают 2 вот таких столбца: один: а—пусто, другой: пусто—б.
Вот представим себе, что есть одно такое, а другое вот такое,
сейчас скажу: пусто, «а», «б», пусто, многоточие, многоточие.
И при этом, внимание, товарищи, подразумевается,
что вот это многоточие в точности совпадает вот с этим, то есть те символы,
которые написаны слева от буквы «а» в первом выравнивании, и те символы,
которые написаны слева от гэпа во втором выравнивании,
— это в точности одни и те же символы.
То же самое касается вот этого кусочка, — давайте я как-нибудь по-другому заштрихую,
— и вот этого кусочка, они тождественно совпадают.
То же самое касается вот этого и вот этого.
Ну и то же самое вот здесь и вот здесь.
То есть все в целом абсолютно одинаковое,
и только вот где-то посерединке, там, или сбоку, неважно,
находится такой вот блок 2х2, в котором в одном случае стоит «а», пусто, пусто,
«б», а в другом — «а» неважно, что такое «а», это просто какой-то символ,
и «б» тоже неважно, просто какой-то символ из нашего алфавита,
— а в другом выравнивании то же самое, те же самые 2 столбца, но в другом порядке.
Вот представим себе, что у нас есть 2 таких выравнивания.
Ну кажется абсолютно естественным считать,
что они просто выражают одну и ту же информацию.
Ну какая разница: сравнить сначала «а» с пустым множеством,
а потом пустое множество с «б», или, наоборот,
сначала пустое множество с «б» сравнить, а потом «а» с пустым множеством?
Никакой новой информации вот это второе выравнивание нам, конечно, не дает.
Если мы уже знаем все информацию, заложенную в первом,
то никакой новой информации за счет второго мы не получим.
Поэтому если такое случилось,
то давайте эти 2 выравнивания просто будем отождествлять.
Значит, есть 2 выравнивания вот таких, — будем их отождествлять, будем считать,
что они вообще на самом деле ничем не отличаются, будем их отождествлять.
Ну давайте рассмотрим пример, чтобы было совершенно понятно.
Вот есть, скажем, выравнивание: «а»,
пусто, пусто «б», пусто «б», «а», пусто.
Вот такое вот выравнивание, то есть, есть одна последовательность,
которая состоит из двух одинаковых символов «а», «а»,
и есть другая последовательность, которая состоит из двух одинаковых символов «б»,
«б», и вот мы именно так выровняли эти 2 последовательности.
Смотрите, первое условие соблюдено, то есть нигде пустое под пустым не стоит.
Второе условие, ну второе условие просто говорит о том,
что помимо вот этого выравнивания есть еще какие-то, которые несут ту же самую
информацию что и оно и, соответственно, с ним отождествляются.
Ну вот давайте подумаем, какие, например, отождествляются.
Давайте переставим вот эти 2 столбца, у нас получится: пусто,
«б», «а», пусто, пусто,
«а», «б», пусто — отождествляются.
Но в свою очередь вот эта вот штуковина может быть дальше переставлена.
Например, мы можем переставить между собой вот эти два столбца,
а можем вот эти — у нас возможностей много.
Ну давайте переставим, например, вот эти 2.
Что у нас получится?
Пусто, «б», пусто, «а», «б»,
пусто, «а», пусто.
Переставили.
И теперь оказывается, что в результате вот таких последовательных перестановок
столбцов, у нас исходное выравнивание не только отождествляется вот с этим,
но и вот с этим тоже.
Они все попарно тождественны, они все дают одну и ту же информацию.
Никакой новизны ни вот в этом по отношению к этому,
ни вот в этом по отношению к этому или к этому нет.
Но для чего я это говорю?
Ну, во-первых, для того чтобы понять, что все-таки выравниваний не совсем столько,
как если бы мы делали полный перебор, их немножко меньше,
а, с другой стороны, я пытаюсь сказать, что, вообще говоря, вот
это вот выравнивание из вот этого — одной такой операции просто сделать было нельзя,
нужно было действительно рисовать такую цепочку из двух
последовательных преобразований столбцов вот по вот этому принципу.
Ну неважно, можно продолжить эту цепочку дальше,
посмотреть что какие-то дальше там отождествляются.
Ну и, соответственно, возникает вопрос: а сколько их действительно все-таки таких?
Сколько существует таких выравниваний,
которые удовлетворяют одновременно вот этому ограничению и вот этому?
Дмитрий Ильинскийпреподаватель
Андрей Райгородскийпрофессор, доктор физико-математических наук
