Search

Given two strings X ( | X | = m ) and Y ( | Y | = n ) over an alphabet Σ, the edit distance between X and Y can be computed in O ( m n / t ) time with the help of the Four-Russians' lookup table whose block size is t . The Four-Russians' lookup table can be constructed in O ( ( 3 | Σ | ) 2 t t 2 ) time using O ( ( 3 | Σ | ) 2 t t ) space. However, the construction time and space requirement of the lookup table grow very fast as the alphabet size increases and thus it has been used only when | Σ | is very small. For example, when a string is a protein sequence, | Σ | = 20 and thus it is almost impossible to use the Four-Russians' lookup table on typical workstations. In this paper, we present an efficient alphabet-independent Four-Russians' lookup table. It requires O ( 3 2 t ( 2 t ) ! t ) space and can be constructed in O ( 3 2 t ( 2 t ) ! t 2 ) time. Thus, the Four-Russians' lookup table can be constructed and used irrespective of the alphabet size. The time and space complexity were achieved by compacting the lookup table using a clever encoding of the preprocessed strings. Experimental results show that the space requirement of the lookup table is reduced to about 1/5,172,030 of its original size when | Σ | = 26 and t = 4 . Furthermore, we present efficient multithreaded parallel algorithms for edit distance computation using the Four-Russians' lookup table. The parallel algorithm for lookup table construction runs in O ( t ) time and the parallel algorithm for edit distance computation between X and Y runs in O ( m + n ) time. Experiments performed on CUDA-supported GPU show that our algorithm runs about 942 times faster than the sequential version of the original Four-Russians' algorithm for 100 pairs of random strings of length approximately 1,000 when | Σ | = 4 and t = 4 . [ABSTRACT FROM AUTHOR]

Abstract: In this paper, we study approximate regularities of strings, that is, approximate periods, approximate covers, and approximate seeds. We explore their similarities and differences and we implement algorithms for solving the smallest distance approximate period/cover/seed problem and the restricted smallest approximate period/cover/seed/ problem in polynomial time, under a variety of distance rules (the Hamming distance, the edit distance, and the weighted edit distance). Then, we analyse our experimental results to find out the time complexity of the algorithms in practice. [Copyright &y& Elsevier]