Домашнее задание по Лекции 10 — Алгоритмы выравнивания последовательностей
Выполненное задание можно будет показать на зачете.
- Выберите два произвольных не очень длинных слова (из русского языка, или любого на выбор); чтобы получилось осмысленно, выберите какие-то отличающиеся, но "родственные" слова. Например, однокоренные, но с чередованием гласной в корне, или с разными суффиксами/приставками.
Нарисуйте матрицу алгоритма динамического программирования для глобального выравнивания двух получившихся слов. Используйте следующие параметры: штраф за открытие гэпа = -2, цена совпадения = 1, цена несовпадения букв = -1. Если хотите усложнить себе жизнь, можете выбрать меньший штраф за продолжение гэпа.
- Можно нарисовать матрицу от руки (на листочке) или в Excel и.т.п - как удобно.
- Отметьте на матрице оптимальный путь.
- Напишите выравнивание, соответствующее найденному пути.