RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB
Общая информация
Последний выпуск
Архив
Импакт-фактор

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Матем. биология и биоинформ.:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Матем. биология и биоинформ., 2017, том 12, выпуск 1, страницы 137–150 (Mi mbb285)  

Биоинформатика

Параллельный алгоритм глобального выравнивания протяжённых аминокислотных и нуклеотидных последовательностей

Р. К. Тетуев, М. И. Пятков, А. Н. Панкратов

Институт математических проблем биологии РАН – филиал ИПМ им. М.В.Келдыша РАН, Пущино, Московская область, Россия

Аннотация: Разработан параллельный алгоритм для глобального выравнивания протяженных последовательностей. Алгоритм использует произвольную матрицу замен. Аффинная система штрафов за внутренние и концевые разрывы в выравнивании может быть задана раздельно для каждой последовательности. Реализована возможность управления выбором оптимального выравнивания из множества альтернативных. Параметрами параллельного алгоритма являются шаги сетки, которая разбивает матрицу глобального выравнивания на блоки. Проведены исследования и выработаны критерии выбора этих параметров как для оптимизации использования памяти, так и по сокращению времени работы алгоритма. Показано, что при выборе размеров блоков, обеспечивающих оптимизацию сложности по памяти, алгоритм позволяет выравнивать протяженные последовательности длины $L$, используя объем памяти $\mathrm{O}(L^{4/3})$. Дополнительно показано, что алгоритм идеально масштабируется на многоядерных системах, демонстрируя суперлинейное ускорение. Алгоритм реализован в виде высокопроизводительного параллельного веб-приложения на языке JavaScript, доступного по адресу http://sbars.impb.ru/aligner.html.

Ключевые слова: глобальное выравнивание, аффинная система штрафов, концевые вставки, параллельные вычисления, суперлинейное ускорение.

Финансовая поддержка Номер гранта
Российский фонд фундаментальных исследований 15-29-07063_офи_м
16-01-00692_а
Работа выполнена при поддержке РФФИ, проекты №15-29-07063 и №16-01-00692.


DOI: https://doi.org/10.17537/2017.12.137

Полный текст: PDF файл (322 kB)
Список литературы: PDF файл   HTML файл

Тип публикации: Статья
УДК: 575.112:004
Материал поступил в редакцию 14.03.2017, опубликован 13.04.2017

Образец цитирования: Р. К. Тетуев, М. И. Пятков, А. Н. Панкратов, “Параллельный алгоритм глобального выравнивания протяжённых аминокислотных и нуклеотидных последовательностей”, Матем. биология и биоинформ., 12:1 (2017), 137–150

Цитирование в формате AMSBIB
\RBibitem{TetPyaPan17}
\by Р.~К.~Тетуев, М.~И.~Пятков, А.~Н.~Панкратов
\paper Параллельный алгоритм глобального выравнивания протяжённых аминокислотных и нуклеотидных последовательностей
\jour Матем. биология и биоинформ.
\yr 2017
\vol 12
\issue 1
\pages 137--150
\mathnet{http://mi.mathnet.ru/mbb285}
\crossref{https://doi.org/10.17537/2017.12.137}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/mbb285
  • http://mi.mathnet.ru/rus/mbb/v12/i1/p137

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Просмотров:
    Эта страница:75
    Полный текст:21
    Литература:8
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020