Back to Search
Start Over
String correction using the Damerau-Levenshtein distance
- Source :
- BMC Bioinformatics, BMC Bioinformatics, Vol 20, Iss S11, Pp 1-28 (2019)
- Publication Year :
- 2019
-
Abstract
- Background In the string correction problem, we are to transform one string into another using a set of prescribed edit operations. In string correction using the Damerau-Levenshtein (DL) distance, the permissible edit operations are: substitution, insertion, deletion and transposition. Several algorithms for string correction using the DL distance have been proposed. The fastest and most space efficient of these algorithms is due to Lowrance and Wagner. It computes the DL distance between strings of length m and n, respectively, in O(m n) time and O(m n) space. In this paper, we focus on the development of algorithms whose asymptotic space complexity is less and whose actual runtime and energy consumption are less than those of the algorithm of Lowrance and Wagner. Results We develop space- and cache-efficient algorithms to compute the Damerau-Levenshtein (DL) distance between two strings as well as to find a sequence of edit operations of length equal to the DL distance. Our algorithms require O(s min{m,n}+m+n) space, where s is the size of the alphabet and m and n are, respectively, the lengths of the two strings. Previously known algorithms require O(m n) space. The space- and cache-efficient algorithms of this paper are demonstrated, experimentally, to be superior to earlier algorithms for the DL distance problem on time, space, and enery metrics using three different computational platforms. Conclusion Our benchmarking shows that, our algorithms are able to handle much larger sequences than earlier algorithms due to the reduction in space requirements. On a single core, we are able to compute the DL distance and an optimal edit sequence faster than known algorithms by as much as 73.1% and 63.5%, respectively. Further, we reduce energy consumption by as much as 68.5%. Multicore versions of our algorithms achieve a speedup of 23.2 on 24 cores.
- Subjects :
- Speedup
Time Factors
String correction
Edit distance
Space (mathematics)
lcsh:Computer applications to medicine. Medical informatics
Biochemistry
Reduction (complexity)
Cache efficient
03 medical and health sciences
0302 clinical medicine
Structural Biology
Damerau–Levenshtein distance
Damerau-Levenshtein distance
Molecular Biology
lcsh:QH301-705.5
030304 developmental biology
Mathematics
Discrete mathematics
0303 health sciences
Sequence
Base Sequence
Applied Mathematics
Research
String (computer science)
Computational Biology
Computer Science Applications
lcsh:Biology (General)
030220 oncology & carcinogenesis
lcsh:R858-859.7
Single-core
Algorithms
Subjects
Details
- ISSN :
- 14712105
- Volume :
- 20
- Issue :
- Suppl 11
- Database :
- OpenAIRE
- Journal :
- BMC bioinformatics
- Accession number :
- edsair.doi.dedup.....8004035c6eb3743d419cbf7ae3333ed6