Алгоритмы в биоинформатике 2013 (практика)

Курс: Алгоритмы в биоинформатике.

Преподаватель: Алексей Кладов.

Даты: Feb 2013 — May 2013.


# Лекции и файлы Дата и время
1 Марковские модели

Алгоритм Витерби на примере задачи нахождения 5'-сайтов сплайсинга.

PDF icon nbt1004-1315.pdf
2 Mar 2013 - 10:00 to 12:00
2 Алгоритм Баума-Велша

PDF icon rabiner.pdf, PDF icon lecture5version3.pdf, Microsoft Office document icon lecture7.doc, Office presentation icon cs262_2006_lecture6.ppt
9 Mar 2013 - 10:00 to 12:00
3 Поиск подстрок

Наивный алгоритм поиска подстроки в строке за O(n^2). Использование хеш-функций в задачах на строки. Построение суффиксного массива за O(n(log n)^2). Алгоритм Рабина-Карпа. Z-функция, префикс-функция и её применение в алгоритме Кнута-Морриса-Пратта
16 Mar 2013 - 10:00 to 12:00
4 Алгоритм Бойера-Мура

Эвристика плохого символа, эвристика хорошего суффикса, эвристика Zvi Galil для количества сравнений.
23 Mar 2013 - 10:00 to 12:00
5 Алгоритм Ахо-Корасик

Задача поиска множества паттернов в тексте. Бор. Суффиксные ссылки. Функция go. Словарные ссылки.

PDF icon Некоторые картинки. Подробное описание алгоритма на http://e-maxx.ru/algo/aho_corasick
6 Apr 2013 - 10:00 to 12:00
6 Выравнивание последовательностей I

Расстояния Хэмминга и Левенштейна. Нахождение edit distance методом динамического программирования. Матрицы замен. Алгоритм Нидлмана — Вунша

PDF icon bioalgo-2013-06-alignment-1.pdf
13 Apr 2013 - 10:00 to 12:00
7 Выравнивание последовательностей II

Локальное выравнивание. Алгоритм Смита-Вотермана. Fitting alignment. Affine gap penalty. Выравнивание для произвольной функции штрафа за O(n^3).

PDF icon bioalgo-2013-07-alignment-2.pdf
20 Apr 2013 - 10:00 to 12:00
8 Выравнивание последовательностей III

Affine gap penalty. Неправильная модификация алгоритма Нидлмана — Вунша. Нидлман — Вунш с тремя матрицами. Задача множественного выравнивания.

PDF icon bioalgo-2013-08-alignment-3.pdf
27 Apr 2013 - 10:00 to 12:00
9 Филогения

Представление эволюции с помощью деревьев. Укоренённые и не укоренённые деревья. Алгоритм Фитча. Сравнение деревьев при помощи split distance. Использование хэширования для сравнения деревьев.

PDF icon bioalgo-2013-09-phylogenetics.pdf
18 May 2013 - 10:00 to 12:00
10 Экзамен 10 Jun 2013 - 10:00 to 12:00