License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2016.2
URN: urn:nbn:de:0030-drops-68359
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6835/
Go to the corresponding LIPIcs Volume Portal

Park, Kunsoo

Compressed and Searchable Indexes for Highly Similar Strings (Invited Talk)

pdf-format:
LIPIcs-ISAAC-2016-2.pdf (0.2 MB)

Abstract

The collection indexing problem is defined as follows: Given a collection of highly similar strings, build a compressed index for the collection of strings, and when a pattern is given, find all occurrences of the pattern in the given strings. Since the index is compressed, we also need a separate operation which retrieves a specified substring of one of the given strings.

Such a collection of highly similar strings can be found in genome sequences of a species and in documents stored in a version control system. Many indexes for the collection indexing problem have been developed, most of which use classical compression schemes such as run-length encoding and Lempel-Ziv compressions to exploit the similarity of the given strings.

We introduce a new index for highly similar strings, called FM index of alignment. We start by finding common regions and non-common regions of highly similar strings. We need not find a multiple alignment of non-common regions. Finding common and non-common regions is much easier and simpler than finding a multiple alignment. Then we make a transformed alignment of the given strings, where gaps in a non-common region are put together into one gap. We define a suffix array of alignment on the transformed alignment, and the FM index of alignment is an FM index of this suffix array of alignment. The FM index of alignment supports the LF mapping and backward search, the key functionalities of the FM index. The FM index of alignment takes less space than other indexes and its pattern search is also fast.

BibTeX - Entry

@InProceedings{park:LIPIcs:2016:6835,
  author =	{Kunsoo Park},
  title =	{{Compressed and Searchable Indexes for Highly Similar Strings (Invited Talk)}},
  booktitle =	{27th International Symposium on Algorithms and Computation (ISAAC 2016)},
  pages =	{2:1--2:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-026-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{64},
  editor =	{Seok-Hee Hong},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6835},
  URN =		{urn:nbn:de:0030-drops-68359},
  doi =		{10.4230/LIPIcs.ISAAC.2016.2},
  annote =	{Keywords: Index for similar strings, FM index, Suffix array, Alignment}
}

Keywords: Index for similar strings, FM index, Suffix array, Alignment
Collection: 27th International Symposium on Algorithms and Computation (ISAAC 2016)
Issue Date: 2016
Date of publication: 07.12.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI