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 | |
Publication status | Published - 03 Sept 2012 |
Externally published | Yes |