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

Area of Science:

• Bioinformatics
• Computational Biology
• Data Structures

Background:

• Existing graph indexing methods, often FM-Index based, have limitations in handling complex biological graphs like pangenomes and transcriptomes.
• These methods may struggle with non-hierarchical structures, explicit storage of all walks, or efficient querying across numerous potential paths.

Purpose of the Study:

• To introduce GIN-TONIC (Graph Indexing Through Optimal Near Interval Compaction), a new data structure for indexing arbitrary string-labelled directed graphs.
• To provide capabilities beyond current FM-Index based methods, including non-hierarchical indexing and efficient querying of all graph walks.

Main Methods:

• GIN-TONIC treats graphs as monolithic objects, indexing all nucleotide-level walks without explicit storage.
• It supports exact substring queries in polynomial time and space, even for exponentially many walks.
• Ad-hoc optimizations like precomputed caches enhance performance across various graph topologies and sizes.

Main Results:

• GIN-TONIC demonstrates robust scalability and querying performance comparable to linear FM-Index.
• The method achieves excellent performance on real-world applications, including human pangenomes and transcriptomes.
• Benchmarks confirm its efficiency for diverse graph structures and scales.

Conclusions:

• GIN-TONIC offers a powerful and efficient solution for indexing complex biological graphs.
• Its capabilities significantly advance graph indexing for applications in genomics and transcriptomics.
• The availability of source code and benchmarks facilitates further research and application.