Метод быстрого множественного попарного выравнивания на основе префиксных деревьев

Обложка

Цитировать

Полный текст

Аннотация

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

Об авторах

П. А. Яковлев

ЗАО “Биокад”

Автор, ответственный за переписку.
Email: yakovlev@biocad.ru
Россия, Санкт-Петербург

Список литературы

  1. Левенштейн В.И. // ДАН. 1965. Т. 163. № 4. С. 845–848.
  2. Needleman S.B., Wunsch C.D. // J. Mol. Biol. 1970. V. 48. № 3. P. 443–453.
  3. Damerau F.J. // Commun. ACM. 1964. V. 7. № 3. P. 171–176.
  4. Smith T.F., Waterman M.S. // J. Mol. Biol. 1981. V. 147. № 1. P. 195–197.
  5. Brudno M., et al. // Bioinformatics. 2003. V. 19. P. 54–62.
  6. Wagner R.A., Fischer M.J. // J. ACM. 1974. V. 21. № 1. P. 168–173.
  7. Aho A.V., Corasick M.J. // Commun. ACM. 1975. V. 18. № 6. P. 333–340.
  8. Cohen J.D. // ACM Trans. Inf. Sys. 1997. V. 15. № 3. P. 291–320.
  9. Market E., Papavasiliou F.N. // PLoS Biol. 2003. V. 1. № 1. P. 24–27.

Дополнительные файлы

Доп. файлы
Действие
1. JATS XML
Скачать

© Российская академия наук, 2019