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

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

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



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






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


Программные системы: теория и приложения, 2015, том 6, выпуск 1, страницы 189–197 (Mi ps164)  

Эта публикация цитируется в 3 научных статьях (всего в 3 статьях)

Математические основы программирования

A model and algorithm for sequence alignment
[Модель и алгоритм выравнивания последовательностей]

S. V. Znamenskij

Program Systems Institute of RAS
Список литературы:
Аннотация: Задача выравнивания (сопоставления) двух текстов с целью выделения общих и различающихся фрагментов обычно имеет не единственное решение. Вычисление лучшего сопоставления канонически базируется на поиске длиннейшей общей подпоследовательности совпадений (LCS) и широко используется в разных целях. Однако многие из современных систем управления версиями предпочитают альтернативные эвристические алгоритмы, работающие не только быстрее, но обычно с лучшим чем поиск LCS результатом.
В статье показаны принципиальные недостатки известных алгоритмов выравнивания последовательностей:
  • даже когда длиннейшая общая подстрока имеет близкую к LCS длину, LCS может состоять из огромного числа коротких малоинформативных фрагментов;
  • известные альтернативные алгоритмы начинают с выделения наиболее информативного общего фрагмента, что порой исключает произвольно длинную последовательность общих фрагментов близкого качества.

Абстрактная задача выравнивания последовательностей рассмотрена как модель выделения изменений в совместно редактируемом тексте с целью минимизации вероятности конфликта (наложения) при слиянии изменений. Целевая функция вводится как совокупное количество всех подстрок, содержащихся в не изменившихся подстроках. Такая оптимизация свободна от упомянутых недостатков. Предложен алгоритм кубической сложности. (Англ.)
Ключевые слова и фразы: сходство строк, выравнивание последовательностей, расстояние редактирования, diff, LCS, метрика Левенштейна, разработка ПО, непрерывная интеграция.
Поступила в редакцию: 14.12.2014
Подписана в печать : 28.01.2015
Тип публикации: Статья
УДК: 004.416
Язык публикации: английский
Образец цитирования: S. V. Znamenskij, “A model and algorithm for sequence alignment”, Программные системы: теория и приложения, 6:1 (2015), 189–197
Цитирование в формате AMSBIB
\RBibitem{Zna15}
\by S.~V.~Znamenskij
\paper A model and algorithm for sequence alignment
\jour Программные системы: теория и приложения
\yr 2015
\vol 6
\issue 1
\pages 189--197
\mathnet{http://mi.mathnet.ru/ps164}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/ps164
  • https://www.mathnet.ru/rus/ps/v6/i1/p189
  • Эта публикация цитируется в следующих 3 статьяx:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Программные системы: теория и приложения
    Статистика просмотров:
    Страница аннотации:248
    PDF полного текста:80
    Список литературы:36
     
      Обратная связь:
     Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024