Подход к улучшению алгоритмов расчета расстояний между цепочками ДНК (на примере алгоритма Нидлмана - Вунша)

Актуальность и цели. На практике достаточно часто встречается необходимость вычисления расстояния между последовательностями различной природы. Подобные алгоритмы используются в биоинформатике для сравнения секвенированных генетических цепочек. В силу большой размерности таких цепочек приходится использовать эвристические алгоритмы, которые дают приближенные результаты. Поэтому возникает задача оценки качества используемых метрик (расстояний), по результатам которой можно сделать вывод о применимости алгоритма к различным исследованиям. Цель исследования – повышение качества оценки расстояния между длинными строками.Материалы и методы. Для сравнения генетических цепочек, взятых из открытого банка данных NСВI, мы предлагаем эвристический алгоритм, разработанный на основе алгоритма Нидлмана - Вунша. После реализации исходного алгоритма к полученным значениям метрики дополнительно применяется специальная функция с тремя параметрами, определение которых производится методом градиентного спуска. Результаты. Получена качественная оценка работы алгоритмов для расчета расстояния между цепочками ДНК и разработан один из подходов к улучшению таких алгоритмов. Выводы. Было предложено улучшение алгоритма Нидлмана - Вунша сравнения строковых последовательностей, а также сформулирован подход к улучшению других алгоритмов построения метрик на длинных строках.