Applications of V-Order: Suffix Arrays, the Burrows-Wheeler Transform & the FM-index

Ali Alatabbi, Jacqueline W. Daykin, Neerja Mhaskar, M. Sohel Rahman, W. F. Smyth

Research output: Chapter in Book/Report/Conference proceedingConference Proceeding (Non-Journal item)

1 Citation (SciVal)

Abstract

V-order is a total order on strings that determines an instance of Unique Maximal Factorization Families (UMFFs), a generalization of Lyndon words. The fundamental V-comparison of strings can be done in linear time and constant space. V-order has been proposed as an alternative to lexicographic order (lexorder) in the computation of suffix arrays and in the suffix-sorting induced by the Burrows-Wheeler transform (BWT). In line with the recent interest in the connection between suffix arrays and the Lyndon factorization, we in this paper make a first attempt to obtain similar results for the V-order factorization. Indeed, we show that the results describing the connection between suffix arrays and the Lyndon factorization are matched by analogous V-order processing. We then apply the V-BWT to implement pattern matching in V-order after suitably modifying the FM-index.
Original languageEnglish
Title of host publicationWALCOM
Subtitle of host publicationAlgorithms and Computation - 13th International Conference, WALCOM 2019, Proceedings
EditorsShin-ichi Nakano, Krishnendu Mukhopadhyaya, Gautam K. Das, Partha S. Mandal
PublisherSpringer Nature
Pages329-338
Number of pages10
ISBN (Electronic)978-3-030-10564-8
ISBN (Print)978-3-030-10563-1
DOIs
Publication statusPublished - 16 Feb 2019

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11355 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Keywords

  • Combinatorics
  • FM-index
  • Lexorder
  • Pattern matching
  • String comparison
  • Suffix sorting
  • V-BWT
  • V-order

Fingerprint

Dive into the research topics of 'Applications of V-Order: Suffix Arrays, the Burrows-Wheeler Transform & the FM-index'. Together they form a unique fingerprint.

Cite this