Комбинаторика для начинающих - это базовый курс, закладывающий самые основы комбинаторного знания. На этом курсе слушатели, которые почти не знают комбинаторику или прочно ее забыли, откроют ее для себя впервые или заново. Курс очень полезен всем, кому трудно с ходу включиться в продвинутый курс современной комбинаторики. Однако фактические бонусы те же: в итоге человек, прослушавший курс, получит путевку в увлекательный мир комбинаторных задач и их далеко идущих приложений. Более того, даже в нем самом мы уже расскажем об инструментах, позволяющих решать некоторые задачи такой важной прикладной области знаний, как биоинформатика. Курс состоит из 7 учебных недель и экзамена. Каждую неделю слушателю предлагается выполнить тест, составляющий 10% от общей оценки. Экзамен состоит из задач по всему курсу и составляет 30% от общей оценки. Для получения сертификата необходимо набрать не менее 50% от общей суммы баллов. Данный курс является упрощённой версией курса "Современная комбинаторика" и рекомендуется к прохождению перед курсом "Теория вероятностей для начинающих".
Задача о выравнивании последовательностей
Loading...
来自 Moscow Institute of Physics and Technology 的课程
Комбинаторика для начинающих
762 个评分
从本节课中
Выравнивания
Насколько похожими являются "кролик" и "икра"? А "хорёк" и "суслик"? Ответы на эти вопросы мы получим в течение этой недели, обсуждая практическое применение комбинаторики в биологии.
与讲师见面
Дмитрий Ильинскийпреподаватель
кафедра дискретной математики МФТИ
Андрей Райгородскийпрофессор, доктор физико-математических наук
кафедра дискретной математики МФТИ
Ну вот давайте поставим эту задачу в математическом ключе.
Называется она, в биологии она называется выравнивание последовательностей.
Выравнивание последовательностей.
Мы ее сейчас, повторяю, поставим в совершенно абстрактном математическом
ключе, но я буду по ходу дела каждый раз напоминать, что это, действительно,
вполне конкретная биологическая задача, которая реально работает,
которая реально нужна для практических нужд.
Значит, смотрите, давайте для простоты считать, что последовательности у нас две.
Есть одна последовательность, которая состоит из каких-то символов a1, ..., an.
Можно ее интерпретировать просто как некое слово.
Но если вам приятнее биологическая интерпретация, то представляйте себе,
что здесь стоят какие-то элементы последовательности ДНК, например.
Вот, а есть другая последовательность, длина которой, вообще говоря,
отличается от длины первой.
То есть видите, здесь мы обозначили длину последовательности n,
а в этом случае длина последовательности уже обозначена m.
Это две последовательности разной, вообще говоря, длины.
Это вполне отвечает практической ситуации, когда мы имеем дело с двумя разными
организмами, и у них, естественно, разные и длины последовательности ДНК.
Чем организм сложнее, тем длина выше.
И в хороших таких, содержательных случаях речь идет, конечно,
о миллиардах в этом месте, ну а в совсем таких тривиальных – о тысячах, о сотнях.
Вот и нам хочется, имея вот эти вот две абстрактные последовательности, понять,
а есть ли в этих последовательностях какие-то похожие участки?
Много ли этих похожих участков?
Но если там есть похожие участки, у нас уже возникает подозрение на то,
что соответствующие организмы достаточно родственны между собой.
Можно производить содержательную классификацию,
искать какие-то общие способы лечения заболеваний и так далее.
То есть тут есть огромная перспектива,
лишь бы научиться сравнивать вот эти две последовательности между собой.
Так, вот что значит — сравнить эти две последовательности?
Что значит — их сравнить?
Ну давайте рассмотрим какой-нибудь конкретный шуточный пример, конечно.
Вот есть кролик, и это — последовательность букв.
То есть будем считать, что наша первая последовательность, которая a1, ...,
an — это последовательность букв слова «кролик», она, конечно, очень коротенькая.
Повторяю, на практике речь идет в лучшем, так сказать, случае о тысячах, а в худшем,
то есть наиболее содержательном случае, речь идет о миллиардах.
Поэтому кролик — это такой совершенно модельный пример.
Ну с жабой его сравнивать, ну вы же понимаете, что нелепо,
потому что если я напишу слово «жаба», вы видите сразу просто, ну человеческий мозг
хорошо устроен, вы видите сразу, что слово «жаба», а равно и слово «лягушка»,
ну в общем как-то на слово «кролик» совершенно не похоже,
никакого родства здесь не видно.
Поэтому я напишу здесь другое слово,
которое в моем сознании ассоциируется с лягушкой, это будет слово «икра».
Нет, ну вы можете себе представлять,
конечно, красную икру, кому что больше нравится.
Но лягушка красную икру, как известно, не мечет.
Вот, значит есть два слова: «кролик» и «икра», и глядя на эти два слова,
вы мгновенно соображаете, что у них, действительно, есть общие участки.
Вот здесь вот есть «кр», которое общее с этим «кр», и вот здесь вот есть участочек
«ик», который является общим с вот этим участочком «ик», то есть есть целых два
похожих участка в последовательности «кролик» и в последовательности «икра».
Повторяю, здесь n = 6, m = 4.
И мы сразу на глазок видим, что есть участки такой похожести.
А теперь представьте себе, что это не вы глядите на эти слова, а компьютер.
Вот как компьютер научить отыскать эти участки?
Он же не соображает так, как вы.
Он должен какой-то перебор осуществить.
Кроме того, даже если и вы соображаете, и у вас тут написано 10 миллиардов символов,
а здесь 100 миллионнов, то извините, вы, конечно,
за мгновение не найдете все участки похожести.
Может и одного не найдете, это такая длинная вереница букв, знаете,
как матрица такая на вас сыпется, и пойдите найдите участки схожести.
Ничего у вас не получится, конечно.
Вот поэтому надо придумать какой-то подход, который компьютер мог
бы реализовать, перебрав какие-то варианты, найти участки схожести.
Вот эти самые «ик» и «кр».
И что придумали люди в первый момент, вот что им пришло сразу в голову?
Им сразу в голову пришло выровнять эти две последовательности друг
относительно друга.
Выровнять в том смысле, чтобы сделать их одинаковой длины, добавив к каждой из этих
последовательностей некоторые символы, которые заведомо не
используются в том языке, на котором эти последовательности написаны.
Ну скажем, символы, которых заведомо нет ни в русском языке, ни в языке,
на котором написана последовательность ДНК, биологическом языке.
Вот символы эти обычно обозначаются вот такой вот штучкой.
И в математике, конечно, они называются пустыми множествами, и мы такое, в общем,
с вами встречали неоднократно.
А в биологии такая штучка называется гэпом.
Ну английское слово gap, то есть пробел, пропуск, дырка.
Вот мы такие вот пустые множества, пробелы, дырки будем расставлять между
буквами каждого из вот этих вот исходных слов, стараясь при этом расположить друг
над другом эти слова, так чтобы длины их совпадали.
При этом, естественно,
последовательность букв исходных слов мы никак менять не будем, мы просто будем
между некоторыми из этих букв добавлять вот такие вот гэпы в каком-то количестве.
То есть ну давайте я приведу пример естественного выравнивания.
Вот написано: «кролик», и вот написано: «икра»,
а здесь добавлено два гэпа, два пустых множества.
Ну вполне себе выравнивание, видите, добавили два несуществующих символа,
получилось две последовательности длины 6, но когда мы глядим на эти две
последовательности никаких участков схожести мы не наблюдаем автоматически.
То есть мы по-прежнему лишь угадываем, что есть какой-то общий «ик»,
но при этом это вот «и» расположено под «к», а вот это «к» расположено под «р»,
то есть машина, компьютер, когда глядит на такое выравнивание,
она сходу не может понять, действительно, есть такой участок похожести или нету.
Но можно написать другое выравнивание, например вот такое: «кролик»,
здесь «ик», «пусто», «пусто»,
«ра», а здесь насажать кучу пустых множеств.
Это тоже выравнивание, как видите, оно имеет другую длину, здесь, видите,
пришлось 6 увеличить на 2, для того чтобы длины сравнялись,
и при этом вот этот вот участочек схожести возник.
Ну или можно также отловить схожесть между «кр».
То есть вот так написать «кролик», а здесь написать «икра»,
сюда добавить гэп и сюда 3 раза добавить гэп.
Вот еще одно выравнивание, которое показывает, свидетельствует о том,
что два наших слова похожи каким-то образом друг на друга, «кр» совпадают,
вот сразу видно, что здесь одинаковые участки.
То есть есть подозрение на то,
что эти слова отражают какую-то одну и ту же сущность биологическую.
Все-таки жаба в каком-то смысле близка к кролику.
Вот, такая вот замечательная штука,
ну и возникает вопрос, товарищи, а сколько существует всего различных выравниваний?
То есть ведь что теперь надо сделать компьютеру?
Компьютеру надо просто тупо перебрать все возможные способы,
выровнять слово «кролик» и «икра».
Среди этих способов будут вот такие дурацкие, которые ни о чем не
свидетельствуют, но будут и содержательные — вот такое, вот такое, вот такое.
И когда они появятся, компьютер загорится красной лампочкой, скажет: о,
смотрите, похожесть появилась.
Значит, но сколько ему придется сделать различных операций,
сколько ему придется перебрать различных выравниваний до тех пор, пока он не
изловит какие-то подходящие, вот это вот интересный комбинаторный вопрос,
которым много занимались математики, но который, в общем, довольно быстро показал,
что полный перебор — это издевательство над компьютером,
издевательство над человечеством, и надо придумывать какие-то дополнительные идеи.
Эти идеи потом появились, но они немножко выходят за рамки нашего курса.
А сейчас мы обсудим, действительно, почему все плохо,
если производить полный перебор.
То есть насколько много различных выравниваний здесь получается,
коль скоро длины исходных последовательностей достаточно велики.
