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.
|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.|
|Publisher||Association for Computing Machinery|
|Number of pages||6|
|Publication status||Published - 03 Sept 2012|