Research output: Contribution to journal › Conference paper › peer-review
Lorraine A.K. Ayad, Carl Barton, Panagiotis Charalampopoulos, Costas S. Iliopoulos, Solon P. Pissis
Original language | English |
---|---|
Pages (from-to) | 27-41 |
Number of pages | 15 |
Journal | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
DOIs | |
Published | 1 Jan 2018 |
Additional links | |
Event | 25th International Symposium on String Processing and Information Retrieval, SPIRE 2018 - Lima, Peru Duration: 9 Oct 2018 → 11 Oct 2018 |
Although real-world text datasets, such as DNA sequences, are far from being uniformly random, string searching average-case algorithms perform significantly better than worst-case ones in most applications of interest. In this paper, we study the problem of computing the longest prefix of each suffix of a given string of length n that occurs elsewhere in the string with k-errors. This problem has already been studied under the Hamming distance model. Our first result is an improvement upon the state-of-the-art average-case time complexity for non-constant k and using only linear space under the Hamming distance model. Notably, we show that our technique can be extended to the edit distance model with the same time and space complexities. Specifically, our algorithms run in (Formula presented) time on average, where c>1 is a constant, using O(n) space. Finally, we show that our technique is applicable to several algorithmic problems found in computational biology and elsewhere. The importance of our technique lies on the fact that it is the first one achieving this bound for non-constant k and using O(n) space.
King's College London - Homepage
© 2020 King's College London | Strand | London WC2R 2LS | England | United Kingdom | Tel +44 (0)20 7836 5454