Finding approximate repetitions under Hamming distance

被引：38

作者：

Kolpakov, R ^{[1
]}

Kucherov, G

机构：

[1] Moscow MV Lomonosov State Univ, French Russian Inst Informat & Appl Math, Moscow 119899, Russia

[2] INRIA Lorraine, Loria, F-54602 Villers Les Nancy, France

来源：

THEORETICAL COMPUTER SCIENCE | 2003年 / 303卷 / 01期

关键词：

D O I：

10.1016/S0304-3975(02)00448-6

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

The problem of computing periodicities 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 (n the word length and S the size of the output). This improves, in particular, the bound obtained by G. Landan and J. Schmidt in 1993 (Proceedings of the Fourth Annual Symposium on Combinatorial Pattern Matching, Lecture Notes in Computer Science, Vol. 684, Springer, Berlin, Padova, Italy, pp. 120-133). Finally, other possible definitions are briefly analyzed. (C) 2002 Elsevier Science B.V. All rights reserved.

引用

页码：135 / 156

页数：22

共 27 条

[1] Tandem repeats finder: a program to analyze DNA sequences [J].

Benson, G .

NUCLEIC ACIDS RESEARCH, 1999, 27 (02) :573-580

[2] A METHOD FOR FAST DATABASE SEARCH FOR ALL K-NUCLEOTIDE REPEATS [J].

BENSON, G ;

WATERMAN, MS .

NUCLEIC ACIDS RESEARCH, 1994, 22 (22) :4828-4836

[3] SQUARES, CUBES, AND TIME-SPACE EFFICIENT STRING SEARCHING [J].

CROCHEMORE, M ;

RYTTER, W .

ALGORITHMICA, 1995, 13 (05) :405-425

[4]

CROCHEMORE M, 1983, CR ACAD SCI I-MATH, V296, P781

[5] AN OPTIMAL ALGORITHM FOR COMPUTING THE REPETITIONS IN A WORD [J].

CROCHEMORE, M .

INFORMATION PROCESSING LETTERS, 1981, 12 (05) :244-250

[6] TIME-SPACE-OPTIMAL STRING MATCHING [J].

GALIL, Z ;

SEIFERAS, J .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1983, 26 (03) :280-294

[7]

Gusfield D, 1997, ALGORITHMS STRINGS T

[8] A characterization of the squares in a Fibonacci string [J].

Iliopoulos, CS ;

Moore, D ;

Smyth, WF .

THEORETICAL COMPUTER SCIENCE, 1997, 172 (1-2) :281-291

[9]

KOLPAKOV R., 1999, P 40 ANN S FDN COMP, P596, DOI DOI 10.1109/SFFCS.1999.814634

[10]

Kosaraju S. R., 1994, Combinatorial Pattern Matching. 5th Annual Symposium, CPM 94. Proceedings, P146

← 1 2 3 →