Lyndon fountains and the Burrows-Wheeler transform

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

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


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 languageEnglish
Title of host publicationProceedings of the CUBE International Information Technology Conference
Subtitle of host publicationCUBE 2012: 3-5 September 2012, Pune, Maharashtra, India.
EditorsVidyasagar Potdar
PublisherAssociation for Computing Machinery
Number of pages6
ISBN (Print)978-1-4503-1185-4
Publication statusPublished - 03 Sept 2012
Externally publishedYes


Dive into the research topics of 'Lyndon fountains and the Burrows-Wheeler transform'. Together they form a unique fingerprint.

Cite this