Article: Compressed indexes for approximate string matching
| Title | Compressed indexes for approximate string matching | ||||
|---|---|---|---|---|---|
| Authors | Chan, HL1 Lam, TW1 Sung, WK2 Tam, SL1 Wong, SS2 | ||||
| Keywords | Approximate String Matching Compressed Index | ||||
| Issue Date | 2010 | ||||
| Publisher | Springer New York LLC. The Journal's web site is located at http://link.springer.de/link/service/journals/00453/index.htm | ||||
| Citation | Algorithmica (New York), 2010, v. 58 n. 2, p. 263-281 [How to Cite?] DOI: http://dx.doi.org/10.1007/s00453-008-9263-2 | ||||
| Abstract | We revisit the problem of indexing a string S[1..n] to support finding all substrings in S that match a given pattern P[1..m] with at most k errors. Previous solutions either require an index of size exponential in k or need Ω(m k ) time for searching. Motivated by the indexing of DNA, we investigate space efficient indexes that occupy only O(n) space. For k=1, we give an index to support matching in O(m+occ+log∈nlog∈log∈n) time. The previously best solution achieving this time complexity requires an index of O(nlog∈n) space. This new index can also be used to improve existing indexes for k≥2 errors. Among others, it can support 2-error matching in O(mlog∈nlog∈log∈n+occ) time, and k-error matching, for any k>2, in O(m k-1log∈nlog∈log∈n+occ) time. © 2008 Springer Science+Business Media, LLC. | ||||
| ISSN | 0178-4617 2011 Impact Factor: 0.604 2011 SCImago Journal Rankings: 0.042 | ||||
| DOI | http://dx.doi.org/10.1007/s00453-008-9263-2 | ||||
| ISI Accession Number ID | WOS:000279681700003
Funding Information: The research T.-W. Lam was supported by the Hong Kong RGC Grant HKU 7140/06E. | ||||
| References | References in Scopus | ||||
| Grants | Compressed indexes for approximate string matching, with applications to biological sequences |
| dc.contributor.author | Chan, HL | ||||
|---|---|---|---|---|---|
| dc.contributor.author | Lam, TW | ||||
| dc.contributor.author | Sung, WK | ||||
| dc.contributor.author | Tam, SL | ||||
| dc.contributor.author | Wong, SS | ||||
| dc.date.accessioned | 2012-06-26T06:39:05Z | ||||
| dc.date.available | 2012-06-26T06:39:05Z | ||||
| dc.date.issued | 2010 | ||||
| dc.description.abstract | We revisit the problem of indexing a string S[1..n] to support finding all substrings in S that match a given pattern P[1..m] with at most k errors. Previous solutions either require an index of size exponential in k or need Ω(m k ) time for searching. Motivated by the indexing of DNA, we investigate space efficient indexes that occupy only O(n) space. For k=1, we give an index to support matching in O(m+occ+log∈nlog∈log∈n) time. The previously best solution achieving this time complexity requires an index of O(nlog∈n) space. This new index can also be used to improve existing indexes for k≥2 errors. Among others, it can support 2-error matching in O(mlog∈nlog∈log∈n+occ) time, and k-error matching, for any k>2, in O(m k-1log∈nlog∈log∈n+occ) time. © 2008 Springer Science+Business Media, LLC. | ||||
| dc.description.grant | Compressed indexes for approximate string matching, with applications to biological sequences | ||||
| dc.description.grantcode | 82195 | ||||
| dc.description.nature | Link_to_subscribed_fulltext | ||||
| dc.identifier.citation | Algorithmica (New York), 2010, v. 58 n. 2, p. 263-281 [How to Cite?] DOI: http://dx.doi.org/10.1007/s00453-008-9263-2 | ||||
| dc.identifier.citeulike | 3811405 | ||||
| dc.identifier.doi | http://dx.doi.org/10.1007/s00453-008-9263-2 | ||||
| dc.identifier.epage | 281 | ||||
| dc.identifier.hkuros | 177358 | ||||
| dc.identifier.isi | WOS:000279681700003
Funding Information: The research T.-W. Lam was supported by the Hong Kong RGC Grant HKU 7140/06E. | ||||
| dc.identifier.issn | 0178-4617 2011 Impact Factor: 0.604 2011 SCImago Journal Rankings: 0.042 | ||||
| dc.identifier.issue | 2 | ||||
| dc.identifier.scopus | eid_2-s2.0-77955655806 | ||||
| dc.identifier.spage | 263 | ||||
| dc.identifier.uri | http://hdl.handle.net/10722/152439 | ||||
| dc.identifier.volume | 58 | ||||
| dc.language | eng | ||||
| dc.publisher | Springer New York LLC. The Journal's web site is located at http://link.springer.de/link/service/journals/00453/index.htm | ||||
| dc.publisher.place | United States | ||||
| dc.relation.ispartof | Algorithmica (New York) | ||||
| dc.relation.references | References in Scopus | ||||
| dc.rights | The original publication is available at www.springerlink.com | ||||
| dc.subject | Approximate String Matching | ||||
| dc.subject | Compressed Index | ||||
| dc.title | Compressed indexes for approximate string matching | ||||
| dc.type | Article |
Author Affiliations
- The University of Hong Kong
- National University of Singapore