FM-index of alignment with gaps

J.C. Na; H. Kim; S. Min; H. Park; T. Lecroq; M. Léonard; L. Mouchard; K. Park

doi:10.1016/j.tcs.2017.02.020

Back

Journal article

Open access

Peer reviewed

FM-index of alignment with gaps

J.C. Na, H. Kim, S. Min, H. Park, T. Lecroq, M. Léonard, L. Mouchard and K. Park

Theoretical Computer Science, Vol.710, pp.148-157

2017

DOI: https://doi.org/10.1016/j.tcs.2017.02.020

Files and links (2)

pdf

FMindex.pdfDownload View

Author’s Version Open Access

url

Link to Published Version *Subscription may be requiredView

Abstract

Recently a compressed index for similar strings, called the FM-index of alignment (FMA), has been proposed with the functionalities of pattern search and random access. The FMA is quite efficient in space requirement and pattern search time, but it is applicable only for an alignment of strings without gaps. In this paper we propose the FM-index of alignment with gaps, a realistic index for similar strings, which allows gaps in their alignment. For this, we design a new version of the suffix array of alignment by using an alignment transformation and a new definition of the alignment-suffix. The new suffix array of alignment enables us to support the LF-mapping and backward search, the key functionalities of the FM-index, regardless of gap existence in the alignment. We experimentally compared our index with RLCSA due to Mäkinen et al. and related indexes GCSA due to Sirén et al. and GCSA2 due to Sirén on genome sequences from the 1000 Genomes Project. The index size of our index is smaller than those of other indexes.

Details

Title: FM-index of alignment with gaps
Authors/Creators: J.C. Na (Author/Creator) - Sejong University
H. Kim (Author/Creator) - Seoul National University
S. Min (Author/Creator) - Seoul National University
H. Park (Author/Creator) - Hanyang University
T. Lecroq (Author/Creator) - Murdoch University
M. Léonard (Author/Creator) - Intelligence and National Security Alliance
L. Mouchard (Author/Creator) - Laboratoire d'Informatique de l'École Polytechnique
K. Park (Author/Creator) - Seoul National University
Publication Details: Theoretical Computer Science, Vol.710, pp.148-157
Publisher: Elsevier BV
Identifiers: 991005544995907891
Murdoch Affiliation: School of Engineering and Information Technology
Language: English
Resource Type: Journal article

Metrics

20 File views/ downloads

68 Record Views

14 Times Cited - Web of Science

InCites Highlights

These are selected metrics from InCites Benchmarking & Analytics tool, related to this output

Collaboration types: Domestic collaboration; International collaboration
Citation topics: 4 Electrical Engineering, Electronics & Computer Science; 4.182 Data Structures, Algorithms & Complexity; 4.182.1103 Efficient Algorithms
Web Of Science research areas: Computer Science, Theory & Methods
ESI research areas: Computer Science