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
  • Программные системы: теория и приложения
    Просмотров:
    Эта страница:85
    Полный текст:32
    Литература:7

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