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, allow GIN-TONIC to achieve excellent performance for input graphs of various topologies and sizes. Robust scalability capabilities and a querying performance close to that of a linear FM-Index are demonstrated for two real-world applications on the scale of human pangenomes and transcriptomes. Source code and associated benchmarks are available on GitHub.

Figure 1.

Example segment of a complex region of a string graph. Vertices are denoted with rectangles, and edges with arrows, and vertex labels as text inside rectangles representing vertices. Walk roots corresponding to the string CATACA—equivalent to vertex index and offsets—are marked with vertical arrows pointing to vertex labels. The walks inducing CATACA starting from the marked walk roots are underlined. Note that one root may induce multiple walks of the example string, that walks stemming from different roots may partially overlap, and that the same path can contain more than one match. Locate queries output all walk roots (vertical arrows), and Walk queries output all paths (segments underlining vertex labels).

Figure 2.

Illustrated examples of how to build and query a GIN-TONIC. (I) A string graph of five vertices and eight edges. (II) Arbitrarily sampled constraint sets for three string label prefixes A, AT, AG generated according to the procedure in the section ‘The vertex permutation’. (III) Codeword assignment to enforce a permutation preserving a consecutive order of the constraint sets in (II). (IV) The single-vertex range translator over σ₀. contains the ranges of in the permutation given in (III). (V) LF-Mapping constructed on the graph encoding with the permutation obtained in (III) with and . The LF-Mapping is partitioned into chunks of 10 characters for visual and algorithm tracing convenience. (VI) IMT based on the single range mapper . (VII) Matching Q = AAT using the data structures in V and VI. The query is successively extended one character at a time starting from its end to the beginning as in the linear FM-Index.

Figure 3.

Benchmarking GIN-TONIC (fast) on adversarial queries. Left panels are for the pangenome, right panels for the transcriptome. Panels (A) and (B) show baseline performance using neither cache nor permutation, only permutation, only cache; and performance of different GIN-TONIC implementations (fast, native and sdsl-based) using both cache and permutation as characters matched per second. Panels (C) and (D) show average Δ(Q) as a function of cache depth. Caches of depth 0 and 1 have very similar performances close to the baseline since they cannot traverse more than one vertex, and hence they appear superimposed in the plots. Panels (E) and (F) show Δ(Q) versus characters matched per second, grouped by cache depth (dashed lines) and average effective query length (solid lines).