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

doi:10.1007/978-3-030-10564-8_26

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

Department of Computer Science

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

2 Citations (Scopus)

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 language	English
Title of host publication	WALCOM
Subtitle of host publication	Algorithms and Computation - 13th International Conference, WALCOM 2019, Proceedings
Editors	Shin-ichi Nakano, Krishnendu Mukhopadhyaya, Gautam K. Das, Partha S. Mandal
Publisher	Springer Nature
Pages	329-338
Number of pages	10
ISBN (Electronic)	978-3-030-10564-8
ISBN (Print)	978-3-030-10563-1
DOIs	https://doi.org/10.1007/978-3-030-10564-8_26
Publication status	Published - 16 Feb 2019

Publication series

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

Keywords

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

Access to Document

10.1007/978-3-030-10564-8_26

Permanent link

Persistent link

Cite this

Alatabbi, A., Daykin, J. W., Mhaskar, N., Rahman, M. S., & Smyth, W. F. (2019). Applications of V-Order: Suffix Arrays, the Burrows-Wheeler Transform & the FM-index. In S. Nakano, K. Mukhopadhyaya, G. K. Das, & P. S. Mandal (Eds.), WALCOM: Algorithms and Computation - 13th International Conference, WALCOM 2019, Proceedings (pp. 329-338). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11355 LNCS). Springer Nature. https://doi.org/10.1007/978-3-030-10564-8_26

Alatabbi, Ali ; Daykin, Jacqueline W. ; Mhaskar, Neerja et al. / Applications of V-Order : Suffix Arrays, the Burrows-Wheeler Transform & the FM-index. WALCOM: Algorithms and Computation - 13th International Conference, WALCOM 2019, Proceedings. editor / Shin-ichi Nakano ; Krishnendu Mukhopadhyaya ; Gautam K. Das ; Partha S. Mandal. Springer Nature, 2019. pp. 329-338 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{733d6274827940e48d4eadbe7c2a1eb8,

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

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.",

keywords = "Combinatorics, FM-index, Lexorder, Pattern matching, String comparison, Suffix sorting, V-BWT, V-order",

author = "Ali Alatabbi and Daykin, {Jacqueline W.} and Neerja Mhaskar and Rahman, {M. Sohel} and Smyth, {W. F.}",

note = "Funding Information: Acknowledgements. The third and fifth authors were funded by NSERC Grant Number: 10536797. The fourth author was partially supported by a grant from Pub-ali Bank Ltd., Bangladesh. The second author was part-funded by the European Regional Development Fund through the Welsh Government, Grant Number 80761-AU-137 (West): Publisher Copyright: {\textcopyright} 2019, Springer Nature Switzerland AG.",

year = "2019",

month = feb,

day = "16",

doi = "10.1007/978-3-030-10564-8_26",

language = "English",

isbn = "978-3-030-10563-1",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Nature",

pages = "329--338",

editor = "Shin-ichi Nakano and Krishnendu Mukhopadhyaya and Das, {Gautam K.} and Mandal, {Partha S.}",

booktitle = "WALCOM",

address = "Switzerland",

}

Alatabbi, A, Daykin, JW, Mhaskar, N, Rahman, MS & Smyth, WF 2019, Applications of V-Order: Suffix Arrays, the Burrows-Wheeler Transform & the FM-index. in S Nakano, K Mukhopadhyaya, GK Das & PS Mandal (eds), WALCOM: Algorithms and Computation - 13th International Conference, WALCOM 2019, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 11355 LNCS, Springer Nature, pp. 329-338. https://doi.org/10.1007/978-3-030-10564-8_26

Applications of V-Order: Suffix Arrays, the Burrows-Wheeler Transform & the FM-index. / Alatabbi, Ali; Daykin, Jacqueline W.; Mhaskar, Neerja et al.
WALCOM: Algorithms and Computation - 13th International Conference, WALCOM 2019, Proceedings. ed. / Shin-ichi Nakano; Krishnendu Mukhopadhyaya; Gautam K. Das; Partha S. Mandal. Springer Nature, 2019. p. 329-338 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11355 LNCS).

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

TY - GEN

T1 - Applications of V-Order

T2 - Suffix Arrays, the Burrows-Wheeler Transform & the FM-index

AU - Alatabbi, Ali

AU - Daykin, Jacqueline W.

AU - Mhaskar, Neerja

AU - Rahman, M. Sohel

AU - Smyth, W. F.

N1 - Funding Information: Acknowledgements. The third and fifth authors were funded by NSERC Grant Number: 10536797. The fourth author was partially supported by a grant from Pub-ali Bank Ltd., Bangladesh. The second author was part-funded by the European Regional Development Fund through the Welsh Government, Grant Number 80761-AU-137 (West): Publisher Copyright: © 2019, Springer Nature Switzerland AG.

PY - 2019/2/16

Y1 - 2019/2/16

N2 - 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.

AB - 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.

KW - Combinatorics

KW - FM-index

KW - Lexorder

KW - Pattern matching

KW - String comparison

KW - Suffix sorting

KW - V-BWT

KW - V-order

UR - http://www.scopus.com/inward/record.url?scp=85062650867&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-10564-8_26

DO - 10.1007/978-3-030-10564-8_26

M3 - Conference Proceeding (Non-Journal item)

SN - 978-3-030-10563-1

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 329

EP - 338

BT - WALCOM

A2 - Nakano, Shin-ichi

A2 - Mukhopadhyaya, Krishnendu

A2 - Das, Gautam K.

A2 - Mandal, Partha S.

PB - Springer Nature

ER -

Alatabbi A, Daykin JW, Mhaskar N, Rahman MS, Smyth WF. Applications of V-Order: Suffix Arrays, the Burrows-Wheeler Transform & the FM-index. In Nakano S, Mukhopadhyaya K, Das GK, Mandal PS, editors, WALCOM: Algorithms and Computation - 13th International Conference, WALCOM 2019, Proceedings. Springer Nature. 2019. p. 329-338. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). Epub 2018 Dec 21. doi: 10.1007/978-3-030-10564-8_26

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

Abstract

Publication series

Keywords

Access to Document

Permanent link

Other files and links

Fingerprint

Cite this