|
Математика
Подход к улучшению алгоритмов расчета расстояний между цепочками ДНК (на примере алгоритма Нидлмана - Вунша)
Б. Ф. Мельниковa, М. А. Тренинаb, А. С. Кочергинa a Российский государственный социальный университет, Москва
b Тольяттинский государственный университет, Тольятти
Аннотация:
Актуальность и цели. На практике достаточно часто встречается необходимость вычисления расстояния между последовательностями различной природы. Подобные алгоритмы используются в биоинформатике для сравнения секвенированных генетических цепочек. В силу большой размерности таких цепочек приходится использовать эвристические алгоритмы, которые дают приближенные результаты. Поэтому возникает задача оценки качества используемых метрик (расстояний), по результатам которой можно сделать вывод о применимости алгоритма к различным исследованиям. Цель исследования – повышение качества оценки расстояния между длинными строками.Материалы и методы. Для сравнения генетических цепочек, взятых из открытого банка данных NСВI, мы предлагаем эвристический алгоритм, разработанный на основе алгоритма Нидлмана - Вунша. После реализации исходного алгоритма к полученным значениям метрики дополнительно применяется специальная функция с тремя параметрами, определение которых производится методом градиентного спуска. Результаты. Получена качественная оценка работы алгоритмов для расчета расстояния между цепочками ДНК и разработан один из подходов к улучшению таких алгоритмов. Выводы. Было предложено улучшение алгоритма Нидлмана - Вунша сравнения строковых последовательностей, а также сформулирован подход к улучшению других алгоритмов построения метрик на длинных строках.
Ключевые слова:
мера сходства последовательностей ДНК, эвристические алгоритмы, алгоритм Нидлмана - Вунша.
Образец цитирования:
Б. Ф. Мельников, М. А. Тренина, А. С. Кочергин, “Подход к улучшению алгоритмов расчета расстояний между цепочками ДНК (на примере алгоритма Нидлмана - Вунша)”, Известия высших учебных заведений. Поволжский регион. Физико-математические науки, 2018, № 1, 46–59
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/ivpnz166 https://www.mathnet.ru/rus/ivpnz/y2018/i1/p46
|
Статистика просмотров: |
Страница аннотации: | 56 | PDF полного текста: | 28 | Список литературы: | 18 |
|