Advanced search
Start date
Betweenand

Burrows-Wheeler transform and succinct De Bruijn graphs

Grant number: 18/21509-2
Support type:Scholarships abroad - Research Internship - Post-doctor
Effective date (Start): December 15, 2018
Effective date (End): March 14, 2019
Field of knowledge:Physical Sciences and Mathematics - Computer Science - Computing Methodologies and Techniques
Principal researcher:Zhao Liang
Grantee:Felipe Alves da Louza
Supervisor abroad: Giovanni Manzini
Home Institution: Faculdade de Filosofia, Ciências e Letras de Ribeirão Preto (FFCLRP). Universidade de São Paulo (USP). Ribeirão Preto , SP, Brazil
Research place: Consiglio Nazionale delle Ricerche (CNR), Italy  
Associated to the scholarship:17/09105-0 - Suffix sorting and string similarity measures, BP.PD

Abstract

The post-doctoral project conducted by the candidate deals with algorithms to compute the Burrows-Wheeler transform (BWT), and investigate string similarity measures based on the BWT. Recently, Egidi, Louza, Manzini and Telles [7] introduced an external memory algorithm to compute the BWT together with the LCP array for a string collection, and showed how to output the document array (DA). The authors also suggested a simple, scan based, external memory algorithm based on the BWT and DA to construct de Bruijn graphs in a succinct representation. The objective of this internship project is to implement the computation of DA together with the BWT, and present a practical external memory algorithm to compute succinct de Bruijn graphs for large string collections.

Scientific publications
(References retrieved automatically from Web of Science and SciELO through information on FAPESP grants and their corresponding numbers as mentioned in the publications by the authors)
LOUZA, FELIPE A.; TELLES, GUILHERME P.; GOG, SIMON; ZHAO, LIANG. Algorithms to compute the Burrows-Wheeler Similarity Distribution. THEORETICAL COMPUTER SCIENCE, v. 782, p. 145-156, AUG 23 2019. Web of Science Citations: 1.
EGIDI, LAVINIA; LOUZA, FELIPE A.; MANZINI, GIOVANNI; TELLES, GUILHERME P. External memory BWT and LCP computation for sequence collections with applications. Algorithms for Molecular Biology, v. 14, MAR 8 2019. Web of Science Citations: 1.

Please report errors in scientific publications list by writing to: cdi@fapesp.br.