ОБ ОДНОМ АЛГОРИТМЕ ПОИСКА НАИБОЛЬШЕЙ ОБЩЕЙ ПОДПОСЛЕДОВАТЕЛЬНОСТИ ДВУХ СТРОК

  • Александр Геннадьевич Панин Тольяттинский государственный университет
Ключевые слова: наибольшая общая подпоследовательность, редакторское расстояние, расстояние Левенштейна, выравнивание строк

Аннотация

В данной работе описан anytime-алгоритм нахождения наибольшей общей подпоследовательности за время O(s∙(1-r2/n2)), где s – количество пар (i,j), таких, что xi = yj, r – длина наибольшей общей подпоследовательности, x и y –заданные строки. Сложность по памяти составляет O(n). Алгоритм так же интересен тем, что работает за один проход по каждой из строк и не требует препроцессинга, хотя такая возможность имеется

Литература

1. Гасфилд Д. “Строки, деревья и последовательности в алгоритмах. Информатика и вычислительная биология”. Невский Диалект, БХВ-Петербург, 2003.
2. Apostolico A., Guerra C. (1987) “The longest common subsequence problem revisited” Algorithmica, Vol. 2, p. 315-36.
3. Bellman R., Dreyfus S. (1962) “Applied Dynamic Programming” Princeton University Press, Princeton NJ.
4. Bergroth L. , Hakonen H., Raita T. (2000) – “A Survey of Longest Common Subsequence Algorithms”.
5. Graham A. Stephen (1992) “String Search”. Technical Report TR-92-gas-01. School of Electronic Engineering Science University College of North Wales.
6. Greenberg R. (2003) – “Bounds on the Number of Longest Common Subsequences”.
7. Hirschberg, D. S. (1975). “A linear space algorithm for computing maximal common subsequences”. Communications of the ACM 18 (6): 341–343. doi:10.1145/360825.360861.
8. Hunt J.W., Szymanski T.G. (1977) “A fast algorithm for computing longest common subsequences” Communications of the ACM, Vol. 20, No. 5, p. 350-3, May 1977.
9. Masek W.J., Paterson M.S. (1980) “A faster algorithm for computing string-edit distances” Journal of Computer and Systems Sciences, Vol. 20, No. 1, p. 18-31.
10. Masek W.J., Paterson M.S. (1983) “How to compute string-edit distances quickly” in Sankofi D., Kruskall J.B. (eds.) Time warps, string edits, and macromolecules: the theory and practice ofsequence comparison, Chapter 14, p. 337-49, Addison-Wesley, Reading MA.
11. Myers E.W. (1991) - “An Overview of Sequence Comparison Algorithms in Molecular Biology”.
12. Myers G. (1999) – “A Fast Bit-Vector Algorithm for Approximate String Matching Based on Dynamic Programming”.
13. Needleman S.B., Wunsch C.D. (1970) “A general method applicable to the search for similarities in the amino-acid sequence of two proteins” Journal of Molecular Biology, Vol. 48, p. 443-53.
14. Wagner R.A., Fischer M.J. (1974) “The string-to-string correction problem” Journal of the ACM, Vol. 21, No. 1, p. 168-73, January 1974.
15. “Наибольшая общая подпоследовательность” -
http://ru.wikipedia.org/wiki/Наибольшая_общая_подпоследовательность.
16. “Longest common subsequence problem” -
http://en.wikipedia.org/wiki/Longest-common_subsequence_problem.
17. “Levenshtein distance” - http://en.wikipedia.org/wiki/Levenshtein_distance.
Выпуск
Раздел
Естественные науки