DocumentCode :
2167318
Title :
Performance comparison & analysis of DivSufSort-based & SAIS-based FM-Index
Author :
Salahuddin, Sumayyea ; Ashfaq, Muniba ; Sher, Madiha ; Hasan, Laiq ; Ahmad, Nasir
Author_Institution :
Department of Computer Systems Engineering, University of Engineering & Technology, Peshawar Pakistan
fYear :
2015
fDate :
22-24 July 2015
Firstpage :
70
Lastpage :
75
Abstract :
FM-Index and Suffix Array are closely related to each other and are both extremely popular indexes for genomic sequences. They are used in several popular read alignment tools, including Bowtie, Bowtie 2, BWA, and GEM. In literature, there exist several Suffix Array Construction Algorithms (SACA). We have considered two popular SACA techniques: DivSufSort and SAIS. Both techniques construct suffix array in linear time. We have constructed FM-Index using both of these SACA algorithms. In this paper, we comprehensively describe our FM-Index construction approach and compare performance of these two indexes in terms of time for different string types in the Dataset. Our result shows that DivSufSort-based FM-Index performs 3.67% time efficient than SAIS-based FM-Index on 10 out of 11 strings in the Dataset.
Keywords :
Algorithm design and analysis; Arrays; Genomics; Indexes; Least squares approximations; Sorting; Transforms; Burrows-Wheeler Transform; FM-Index; String Matching; Suffix Array; Suffix Sorting; Wavelet Tree;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Computer Science & Education (ICCSE), 2015 10th International Conference on
Conference_Location :
Cambridge, United Kingdom
Print_ISBN :
978-1-4799-6598-4
Type :
conf
DOI :
10.1109/ICCSE.2015.7250220
Filename :
7250220
Link To Document :
بازگشت