Projects per year
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 Lyndon factorization, in this paper we obtain similar results for the V-order factorization. Indeed, we show that the results describing the connection between suffix arrays and Lyndon factorization are matched by analogous V-order processing. We also describe a methodology for efficiently computing the FM-Index in V-order, as well as V-order substring pattern matching using backward search.
Original language | English |
---|---|
Pages (from-to) | 82-96 |
Number of pages | 15 |
Journal | Theoretical Computer Science |
Volume | 880 |
Early online date | 21 Jul 2021 |
DOIs | |
Publication status | Published - 03 Aug 2021 |
Keywords
- Burrows-Wheeler transform
- Combinatorics
- FM-index
- Lexorder
- String comparison
- Substring pattern matching
- Suffix sorting
- V-BWT
- V-order
Fingerprint
Dive into the research topics of 'Computation of the suffix array, burrows-wheeler transform and FM-index in V-order'. Together they form a unique fingerprint.Projects
- 1 Finished
-
SeqInfo : Big Data Stringology Algorithms for 2nd and 3rd Generation Sequencing - Dr Jacqueline Daykin - EU/WG
15 Jan 2018 → 07 Jan 2021
Project: Externally funded research