Please use this identifier to cite or link to this item:
https://scholarbank.nus.edu.sg/handle/10635/41733
DC Field | Value | |
---|---|---|
dc.title | A linear size index for approximate pattern matching | |
dc.contributor.author | Chan, H.-L. | |
dc.contributor.author | Lam, T.-W. | |
dc.contributor.author | Sung, W.-K. | |
dc.contributor.author | Tam, S.-L. | |
dc.contributor.author | Wong, S.-S. | |
dc.date.accessioned | 2013-07-04T08:34:27Z | |
dc.date.available | 2013-07-04T08:34:27Z | |
dc.date.issued | 2006 | |
dc.identifier.citation | Chan, H.-L.,Lam, T.-W.,Sung, W.-K.,Tam, S.-L.,Wong, S.-S. (2006). A linear size index for approximate pattern matching. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 4009 LNCS : 49-59. ScholarBank@NUS Repository. | |
dc.identifier.isbn | 3540354557 | |
dc.identifier.issn | 03029743 | |
dc.identifier.uri | http://scholarbank.nus.edu.sg/handle/10635/41733 | |
dc.description.abstract | This paper revisits the problem of indexing a text S[1.,n] to support searching substrings in S that match a given pattern P[1..m] with at most k errors. A naive solution either has a worst-case matching time complexity of Ω(m k) or requires Ω(n k) space. Devising a solution with better performance has been a challenge until Cole et al. [5] showed an O(nlog k n)-space index that can support k-error matching in O(m+occ+log k n log log n) time, where occ is the number of occurrences. Motivated by the indexing of DNA, we investigate in this paper the feasibility of devising a linear-size index that still has a time complexity linear in m. In particular, we give an O(n)-apace index that supports k-error matching in O(m + occ+ (log n) k(k+1) log log n) worst-case time. Furthermore, the index can be compressed from O(n) words into O(n) bits with a slight increase in the time complexity. © Springer-Verlag Berlin Heidelberg 2006. | |
dc.source | Scopus | |
dc.type | Conference Paper | |
dc.contributor.department | COMPUTER SCIENCE | |
dc.description.sourcetitle | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) | |
dc.description.volume | 4009 LNCS | |
dc.description.page | 49-59 | |
dc.identifier.isiut | NOT_IN_WOS | |
Appears in Collections: | Staff Publications |
Show simple item record
Files in This Item:
There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.