Suffix tree of alignment: an efficient index for similar data

DOI10.1007/978-3-642-45278-9_29MaRDI QIDQ2870039zbMATH OpenOpenAlexFDO

Authors Joong Chae Na, Heejin Park, Maxime Crochemore, Jan Holub, Costas S. Iliopoulos, L. Mouchard, Kunsoo Park

Publication date 17 January 2014

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1305.1744

zbMATH Keywords

alignmentsindexes for similar datasuffix trees

Mathematics Subject Classification ID

Data structures (68P05) Algorithms on strings (68W32)

Abstract: We consider an index data structure for similar strings. The generalized suffix tree can be a solution for this. The generalized suffix tree of two strings $A$ and $B$ is a compacted trie representing all suffixes in $A$ and $B$. It has $|A|+|B|$ leaves and can be constructed in $O(|A|+|B|)$ time. However, if the two strings are similar, the generalized suffix tree is not efficient because it does not exploit the similarity which is usually represented as an alignment of $A$ and $B$. In this paper we propose a space/time-efficient suffix tree of alignment which wisely exploits the similarity in an alignment. Our suffix tree for an alignment of $A$ and $B$ has $|A|+l_d+l_1$ leaves where $l_d$ is the sum of the lengths of all parts of $B$ different from $A$ and $l_1$ is the sum of the lengths of some common parts of $A$ and $B$. We did not compromise the pattern search to reduce the space. Our suffix tree can be searched for a pattern $P$ in $O(|P|+occ)$ time where $occ$ is the number of occurrences of $P$ in $A$ and $B$. We also present an efficient algorithm to construct the suffix tree of alignment. When the suffix tree is constructed from scratch, the algorithm requires $O(|A|+l_d+l_1+l_2)$ time where $l_2$ is the sum of the lengths of other common substrings of $A$ and $B$. When the suffix tree of $A$ is already given, it requires $O(l_d+l_1+l_2)$ time.

Recommendations

• FM-index of alignment: a compressed index for similar strings
• Space efficient suffix trees
• Suffix Arrays: A New Method for On-Line String Searches
• Suffix trees on words
• Contracted Suffix Trees: A Simple and Dynamic Text Indexing Data Structure

Cited in

(11)

• FM-index of alignment with gaps
• On-line string matching in highly similar DNA sequences
• Document listing on repetitive collections with guaranteed performance
• Grammar-compressed indexes with logarithmic search time
• FM-index of alignment: a compressed index for similar strings
• Algorithms for indexing highly similar DNA sequences
• scientific article; zbMATH DE number 2079422 (Why is no real title available?)
• Faster compressed suffix trees for repetitive collections
• Geometric Suffix Tree: A New Index Structure for Protein 3-D Structures
• Algorithms and complexity on indexing founder graphs
• The Burrows-Wheeler transform of an elastic-degenerate string and its application to pattern matching

This page was built for publication: Suffix tree of alignment: an efficient index for similar data

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2870039)