Abstract | ||
---|---|---|
In this paper we propose the FM-index of alignment, a compressed index for similar strings with the functionalities of pattern search and random access. For this, we first design a new and improved version of the suffix array of alignment. 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, but the LF-mapping and backward search of our index is significantly more involved than the original FM-index. We implemented the FM-index of alignment and did experiments on 100 genome sequences from the 1000 Genomes Project. The index size of the FM-index of alignment is about a half of that of RLCSA due to Mäkinen et al. |
Year | DOI | Venue |
---|---|---|
2016 | 10.1016/j.tcs.2015.08.008 | Theoretical Computer Science |
Keywords | DocType | Volume |
Indexes for similar strings,FM-indexes,Suffix arrays,Alignments,Backward search | Journal | 638 |
ISSN | Citations | PageRank |
0304-3975 | 3 | 0.42 |
References | Authors | |
17 | 7 |
Name | Order | Citations | PageRank |
---|---|---|---|
Joong Chae Na | 1 | 162 | 18.21 |
Hyun-joon Kim | 2 | 93 | 10.19 |
Heejin Park | 3 | 235 | 21.63 |
Thierry Lecroq | 4 | 662 | 58.52 |
Martine Léonard | 5 | 37 | 5.66 |
Laurent Mouchard | 6 | 251 | 25.07 |
Kunsoo Park | 7 | 1396 | 171.00 |