|
ИСТИНА |
Войти в систему Регистрация |
ИПМех РАН |
||
Finding Approximate Repetitions under Hamming Distanceстатья
- Авторы: Kolpakov R., Kucherov G.
- Сборник: Proceedings of 9th Annual European Symposium on Algorithms (ESA'01)
- Серия: Lecture Notes in Computer Science
- Том: 2161
- Год издания: 2001
- Место издания: SPRINGER-VERLAG BERLIN
- Первая страница: 170
- Последняя страница: 181
- DOI: 10.1007/3-540-44676-1_14
- Аннотация: The problem of computing tandem repetitions with K possible mismatches is studied. Two main definitions are considered, and for both of them an O(nK log K + S) algorithm is proposed (S the size of the output). This improves, in particular, the bound obtained in G. Landau and J. Schmidt. An algorithm for approximate tandem repeats. In A. Apostolico, M. Crochemore, Z. Galil, and U. Manber, editors, Proceedings of the 4th Annual Symposium on Combinatorial Pattern Matching, number 684 in Lecture Notes in Computer Science, pages 120–133, Padova, Italy, 1993. Springer-Verlag, Berlin.
- Добавил в систему: Колпаков Роман Максимович