Методические указания к курсу «Элементы дискретной математики и биоинформатики» (стр. 4 из 8)
В силу выбора нами дочерних бактерий следует, что
.Последовательность натуральных чисел П1, П2, П3, … монотонно убывает. Первый член этой последовательности равен 1000, последний – 2. Значит, найдется такой номер k, когда число Пk в первый раз станет меньше 200, т.е. когда
и 
. Учитывая, что 
, получим 
, т.е. число потомков бактерии Бk не меньше 100 и не больше 199. Лекции 16-17.
Цель данного раздела – дать общее представление о теории алгоритмов, обсудить вопросы сложности и эффективности, рассмотреть классические примеры алгоритмов на графах, а также примеры биологических задач, использующих алгоритмические методы решения. Тем самым, этот раздел с одной стороны позволяет студентам более успешно осваивать дисциплины, связанные с информатикой, с другой стороны дает предварительные сведения из теории алгоритмов, необходимые при изучении второй части курса, посвященной основам биоинформатики.
В качестве примера, приведем две типичные задачи биоинформатики. Первая задача – задача сравнения последовательностей. Дана аминокислотная последовательность, похожая на некоторую другую последовательность, хранящуюся в банке данных, т.е. по которой имеются экспериментальные данные, и известны ее функции. Тогда можно предположить, что эти последовательности выполняют сходные функции. Таким образом, после секвенирования новой последовательности ее сравнивают с уже существующими в базах данных последовательностями, чтобы судить о том, какие функции несет эта последовательность. Следовательно, возникает задача поиска сходства последовательностей, а именно: одна последовательность записывается под другой, и требуется найти наилучший вариант так выровнять эту пару последовательностей, чтобы количество совпадений было максимальным. Качество выравнивания оценивают, назначая штрафы за несовпадение букв и за наличие пробелов (когда приходится раздвигать одну последовательность для того, чтобы получить наибольшее число совпадающих позиций). Ясно, что можно найти оптимальное выравнивание перебором всех возможных вариантов, но на практике этот способ неприменим – число возможных выравниваний экспоненциально зависит от длины последовательности. Тем не менее, для решения этой задачи существует эффективный алгоритм: она сводится к задаче поиска кратчайшего пути во взвешенном графе.
Другая задача – предсказание вторичной структуры РНК. Вторичная структура РНК – структура, образуемая спаренными основаниями на однонитевой молекуле РНК. Вся РНК состоит из петель и спиралей. Петли бывают следующих типов: шпилька, внутренняя, выпячивание, множественная, псевдоузел. Таким образом, задача определения вторичной структуры состоит в правильном определении спаренных нуклеотидов. Эту задачу можно интерпретировать в терминах теории графов: «правильной» вторичной структуре будет соответствовать максимальный подграф (клика) в графе потенциальных спиралей. Однако известно, что задача поиска клики в графе является труднорешаемой – для нее, скорее всего, не существует более эффективного алгоритма решения, чем полный перебор всех вариантов. Тем не менее, на практике эта задача решается приближенно, используя алгоритм динамического программирования.
Краткое содержание раздела:
Понятие алгоритма. Алгоритмы и их сложность. Полиномиальные и экспоненциальные алгоритмы. Эффективные и неэффективные алгоритмы. Примеры задач: задача о кратчайшем пути во взвешенном графе, задача о минимальном остове. Алгоритм Краскала. Труднорешаемые задачи: задача коммивояжера, задача о максимальном полном подграфе. Поиск в графе: поиск в глубину, поиск в ширину. Поиск кратчайшего по числу ребер пути. Алгоритм отыскания эйлеровой цепи в эйлеровом графе. Некоторые типичные задачи биоинформатики, сводящиеся к задачам на графах: задача сравнения последовательностей, задача предсказания вторичной структуры РНК, задача поиска кратчайшей надстроки, расшифровка гибридизацией.
Литература: [1], гл. 7 стр. 207-213, гл. 8 стр. 226-232, 247-262.
Задачи: [12] №№ 59, 61.
6. Основные алгебраические структуры.
Лекции 18-20.
Алгебраические методы описания моделей находят самое широкое применение при формализации различных предметных областей. Можно сказать, что при построении модели предметной области, все начинается с введения подходящих множеств, операций и отношений над их элементами с последующим исследованием их свойств. Таким образом, владение алгебраической терминологией входит в арсенал средств, необходимых для абстрактного моделирования. Приведем пример применения полугрупп в биологии для описания некоторых аспектов скрещивания организмов. При выведении породы крупного рогатого скота рассматривают цвет, черный или бурый, и признаки одноцветности или пятнистости. Известно, что черный цвет доминантен, а бурый рецессивен и что одноцветность доминирует над пятнистостью. Таким образом, в данном стаде различают четыре типа скота:
a – «черный одноцветный», b – «черный пятнистый»,
c – «бурый одноцветный», d – «бурый пятнистый».
Учитывая отношения доминирования, при скрещивании черной пятнистой особи с бурой одноцветной особью следует ожидать черное одноцветное потомство. Это можно записать в виде
. «Операция скрещивания» 
, рассмотренная для всех всевозможных пар, описывается следующей таблицей: | | a b c d |
| a b c d | a a a a a b a b a a c c a b c d |
Это – таблица Кэли для группоида
. По данной таблице можно проверить, что операция является ассоциативной, т.е. S является полугруппой. Кроме того, таблица является симметричной относительно главной диагонали, следовательно, операция коммутативна, элемент d является нейтральным элементом полугруппы, а – нулем.В процессе изучения данного раздела студенты должны составить представление о классических алгебраических структурах: полугруппах, группах, кольцах, полях и их основных свойствах. Особое внимание при изучении данного раздела уделяется свободным полугруппам, поскольку они играют важную роль, как в общей теории полугрупп, так и в приложениях. Их прикладная роль объясняется, в частности, тем, что во многих процессах передачи информации, передаваемые сообщения представляют собой цепочки символов ("реальных" букв или слов, других кодовых знаков, электрических сигналов, последовательностей нуклеотидов в цепочке ДНК и т.д.), и соединение двух таких цепочек есть не что иное, как конкатенация слов в подходящей свободной полугруппе. Свободные полугруппы (главным образом над конечными алфавитами) являются исходным объектом в теории формальных языков и теории кодов, существенна их роль в теории автоматов.
Краткое содержание раздела:
Операции на множествах. Свойства операций: ассоциативность, коммутативность. Понятие полугруппы. Примеры. Полугруппы в биологии. Нейтральный элемент и его свойства. Обратный элемент и его единственность в полугруппе. Понятие группы. Примеры. Абелевы группы. Подполугруппы, подгруппы. Порождающие множества. Циклические полугруппы и группы, их свойства. Гомоморфизмы и изоморфизмы полугрупп и групп. Свободные полугруппы и группы, их свойства. Свободные полугруппы и цепочки ДНК.
Кольца. Поля. Основные свойства, примеры. Область целостности, тело. Примеры. Кольцо многочленов.
Литература: [2], [10], [11].
Задачи: [3] №№ 1.1.1 (а, в, д, ж, и), 1.1.3 (а), 1.1.9, 1.2.10 (а), 1.2.12 (б), 2.2.33 (б), 2.3.6 (а, в), 3.1.1 (а, б, в), 4.1.15 (а), 4.2.4.
7. Элементы теории формальных языков и автоматов.
Лекции 21-24.
Теория формальных языков и автоматов представляет удобный и естественный аппарат для формального математического описания операций над молекулами ДНК, самих молекул и вычислительных процессов с использованием ДНК. Живые организмы выполняют сложные операции, руководствуясь, по сути, цифровой информацией. Биомолекулярные реакции, да и деятельность организма в целом, управляются инструкциями, записанными в геноме последовательностью нуклеиновых кислот. Если внутриклеточную биомолекулярную машину, обрабатывающую нуклеотидные последовательности ДНК и РНК, сравнить с машиной Тьюринга, то можно заметить поразительное сходство. Обе системы оперируют информацией, которая хранится в цепочке символов, построенной на основании алфавита, и шаг за шагом выполняют инструкции, переходя от одного элемента к другому и по определенным правилам изменяя их или добавляя новые. Поэтому естественно предположить, что из биологических молекул можно создать ЭВМ. При этом, естественным аппаратом для математического моделирования и исследования молекулярных вычислений является теория формальных языков и автоматов. Например, молекула ДНК состоит из двух нитей, которые, соединяясь друг с другом, образуют двойную спираль. Каждая нить, будучи полимером, построена из нуклеотидов, различающихся своими основаниями. Таких оснований четыре: А (аденин), Г (гуанин), Ц (цитозин) и Т (тимин). Поэтому отдельную нить ДНК естественно представлять в виде слова над четырехбуквенным алфавитом. При помощи специальных веществ – ферментов – с ДНК можно производить различные операции: удлинять ДНК, обрезать или разрезать ДНК, соединять последовательно две молекулы ДНК. Эти и другие ферментные операции с молекулами ДНК естественно представляются как операции над строками (например, сшивка двух молекул ДНК соответствует операции конкатенации двух строк, т.е. приписывания второй строки в конец первой).