| Full text | |
| Author(s): |
Total Authors: 3
|
| Affiliation: | [1] Univ Piemonte Orientale, Alessandria - Italy
[2] Univ Fed Uberlandia, Uberlandia, MG - Brazil
[3] Univ Pisa, Pisa - Italy
Total Affiliations: 3
|
| Document type: | Journal article |
| Source: | ALGORITHMICA; JUL 2021. |
| Web of Science Citations: | 0 |
| Abstract | |
The merging of succinct data structures is a well established technique for the space efficient construction of large succinct indexes. In the first part of the paper we propose a new algorithm for merging succinct representations of de Bruijn graphs. Our algorithm has the same asymptotic cost of the state of the art algorithm for the same problem but it uses less than half of its working space. A novel important feature of our algorithm, not found in any of the existing tools, is that it can compute the Variable Order succinct representation of the union graph within the same asymptotic time/space bounds. In the second part of the paper we consider the more general problem of merging succinct representations of Wheeler graphs, a recently introduced graph family which includes as special cases de Bruijn graphs and many other known succinct indexes based on the BWT or one of its variants. In this paper we provide a space efficient algorithm for Wheeler graph merging; our algorithm works under the assumption that the union of the input Wheeler graphs has an ordering that satisfies the Wheeler conditions and which is compatible with the ordering of the original graphs. (AU) | |
| FAPESP's process: | 17/09105-0 - Suffix sorting and string similarity measures |
| Grantee: | Felipe Alves da Louza |
| Support Opportunities: | Scholarships in Brazil - Post-Doctoral |
| FAPESP's process: | 18/21509-2 - Burrows-Wheeler transform and succinct De Bruijn graphs |
| Grantee: | Felipe Alves da Louza |
| Support Opportunities: | Scholarships abroad - Research Internship - Post-doctor |