GIN-TONIC: non-hierarchical full-text indexing for graph genomes.

ABSTRACT: This paper presents a new data structure, GIN-TONIC (Graph INdexing Through Optimal Near Interval Compaction), designed to index arbitrary string-labelled directed graphs representing, for instance, pangenomes or transcriptomes. GIN-TONIC provides several capabilities not offered by other graph-indexing methods based on the FM-Index. It is non-hierarchical, handling a graph as a monolithic object; it indexes at nucleotide resolution all possible walks in the graph without the need to explicitly store them; it supports exact substring queries in polynomial time and space for all possible walk roots in the graph, even if there are exponentially many walks corresponding to such roots. Specific ad-hoc optimizations, such as precomputed caches, a

SUBMITTER: Ozturk U 

PROVIDER: S-EPMC11632618 | biostudies-literature | 2024 Dec

REPOSITORIES: biostudies-literature