FM-index of alignment: A compressed index for similar strings
- Title
- FM-index of alignment: A compressed index for similar strings
- Author
- 박희진
- Keywords
- Indexes for similar strings; FM-indexes; Suffix arrays; Alignments; Backward search
- Issue Date
- 2016-07
- Publisher
- ELSEVIER SCIENCE BV
- Citation
- THEORETICAL COMPUTER SCIENCE, v. 638, Page. 159-170
- 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 Makinen et al. (C) 2015 Elsevier B.V. All rights reserved.
- URI
- https://www.sciencedirect.com/science/article/pii/S0304397515007288?via%3Dihubhttps://repository.hanyang.ac.kr/handle/20.500.11754/74319
- ISSN
- 0304-3975; 1879-2294
- DOI
- 10.1016/j.tcs.2015.08.008
- Appears in Collections:
- COLLEGE OF ENGINEERING[S](공과대학) > COMPUTER SCIENCE(컴퓨터소프트웨어학부) > Articles
- Files in This Item:
There are no files associated with this item.
- Export
- RIS (EndNote)
- XLS (Excel)
- XML