Lyndon fountains and the Burrows-Wheeler transform

Ali Alatabbi; Maxime Crochemore; Jacqueline W. Daykin; Laurent Mouchard

doi:10.1145/2381716.2381799

Lyndon fountains and the Burrows-Wheeler transform

Ali Alatabbi, Maxime Crochemore, Jacqueline W. Daykin, Laurent Mouchard

Research output: Chapter in Book/Report/Conference proceeding › Conference Proceeding (ISBN)

Abstract

In this paper we study Lyndon structures related to the Burrows-Wheeler Transform with potential application to bioinformatics. Next-Generation Sequencing techniques require the alignment of a large set of short reads (between dozens to hundreds of letters) on a reference sequence (millions of letters). The Burrows-Wheeler Transform has been used in various alignment programs which generally compute the Lyndon factorization of the reference sequence as a preprocessing step. We compute the quadratic factorization of all rotations of an input string and the Burrows-Wheeler Transform of a Lyndon substring. From the factored rotations we introduce the Lyndon fountain.

Original language	English
Title of host publication	Proceedings of the CUBE International Information Technology Conference
Subtitle of host publication	CUBE 2012: 3-5 September 2012, Pune, Maharashtra, India.
Editors	Vidyasagar Potdar
Publisher	Association for Computing Machinery
Pages	441-446
Number of pages	6
ISBN (Print)	978-1-4503-1185-4
DOIs	https://doi.org/10.1145/2381716.2381799
Publication status	Published - 03 Sept 2012
Externally published	Yes

Access to Document

10.1145/2381716.2381799

Permanent link

Persistent link

Cite this

@inproceedings{339173fe00964abea79b206b597afab8,

title = "Lyndon fountains and the Burrows-Wheeler transform",

abstract = "In this paper we study Lyndon structures related to the Burrows-Wheeler Transform with potential application to bioinformatics. Next-Generation Sequencing techniques require the alignment of a large set of short reads (between dozens to hundreds of letters) on a reference sequence (millions of letters). The Burrows-Wheeler Transform has been used in various alignment programs which generally compute the Lyndon factorization of the reference sequence as a preprocessing step. We compute the quadratic factorization of all rotations of an input string and the Burrows-Wheeler Transform of a Lyndon substring. From the factored rotations we introduce the Lyndon fountain.",

author = "Ali Alatabbi and Maxime Crochemore and Daykin, \{Jacqueline W.\} and Laurent Mouchard",

year = "2012",

month = sep,

day = "3",

doi = "10.1145/2381716.2381799",

language = "English",

isbn = "978-1-4503-1185-4",

pages = "441--446",

editor = "Vidyasagar Potdar",

booktitle = "Proceedings of the CUBE International Information Technology Conference",

publisher = "Association for Computing Machinery",

address = "United States of America",

}

Lyndon fountains and the Burrows-Wheeler transform. / Alatabbi, Ali; Crochemore, Maxime; Daykin, Jacqueline W. et al.
Proceedings of the CUBE International Information Technology Conference: CUBE 2012: 3-5 September 2012, Pune, Maharashtra, India.. ed. / Vidyasagar Potdar. Association for Computing Machinery, 2012. p. 441-446.

Research output: Chapter in Book/Report/Conference proceeding › Conference Proceeding (ISBN)

TY - GEN

T1 - Lyndon fountains and the Burrows-Wheeler transform

AU - Alatabbi, Ali

AU - Crochemore, Maxime

AU - Daykin, Jacqueline W.

AU - Mouchard, Laurent

PY - 2012/9/3

Y1 - 2012/9/3

N2 - In this paper we study Lyndon structures related to the Burrows-Wheeler Transform with potential application to bioinformatics. Next-Generation Sequencing techniques require the alignment of a large set of short reads (between dozens to hundreds of letters) on a reference sequence (millions of letters). The Burrows-Wheeler Transform has been used in various alignment programs which generally compute the Lyndon factorization of the reference sequence as a preprocessing step. We compute the quadratic factorization of all rotations of an input string and the Burrows-Wheeler Transform of a Lyndon substring. From the factored rotations we introduce the Lyndon fountain.

AB - In this paper we study Lyndon structures related to the Burrows-Wheeler Transform with potential application to bioinformatics. Next-Generation Sequencing techniques require the alignment of a large set of short reads (between dozens to hundreds of letters) on a reference sequence (millions of letters). The Burrows-Wheeler Transform has been used in various alignment programs which generally compute the Lyndon factorization of the reference sequence as a preprocessing step. We compute the quadratic factorization of all rotations of an input string and the Burrows-Wheeler Transform of a Lyndon substring. From the factored rotations we introduce the Lyndon fountain.

U2 - 10.1145/2381716.2381799

DO - 10.1145/2381716.2381799

M3 - Conference Proceeding (ISBN)

SN - 978-1-4503-1185-4

SP - 441

EP - 446

BT - Proceedings of the CUBE International Information Technology Conference

A2 - Potdar, Vidyasagar

PB - Association for Computing Machinery

ER -

Lyndon fountains and the Burrows-Wheeler transform

Abstract

Access to Document

Permanent link

Fingerprint

Cite this