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

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

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



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






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


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

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

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

A model and algorithm for sequence alignment

[Модель и алгоритм выравнивания последовательностей]

S. V. Znamenskij

Program Systems Institute of RAS

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

Абстрактная задача выравнивания последовательностей рассмотрена как модель выделения изменений в совместно редактируемом тексте с целью минимизации вероятности конфликта (наложения) при слиянии изменений. Целевая функция вводится как совокупное количество всех подстрок, содержащихся в не изменившихся подстроках. Такая оптимизация свободна от упомянутых недостатков. Предложен алгоритм кубической сложности. (Англ.)

Ключевые слова и фразы: сходство строк, выравнивание последовательностей, расстояние редактирования, diff, LCS, метрика Левенштейна, разработка ПО, непрерывная интеграция.

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

Тип публикации: Статья
УДК: 004.416
Поступила в редакцию: 14.12.2014
Подписана в печать : 28.01.2015
Язык публикации: английский

Образец цитирования: 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}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/ps164
  • http://mi.mathnet.ru/rus/ps/v6/i1/p189

    ОТПРАВИТЬ: 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

    Эта публикация цитируется в следующих статьяx:
    1. Sergej V. Znamenskij, “Simple essential improvements to the ROUGE-W algorithm”, Журн. СФУ. Сер. Матем. и физ., 8:4 (2015), 497–501  mathnet  crossref
  • Программные системы: теория и приложения
    Просмотров:
    Эта страница:99
    Полный текст:39
    Литература:7

     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2019