NIQKI

NIQKI implements generalized Hyperminhash ((h,m)-HMH) fingerprints and inverted-index search to index large genomic collections and enable rapid, scalable pairwise distance estimation for comparative genomics and phylogenetic analysis.

Key Features:

• Fingerprints - (h,m)-HMH: Generalizes Hyperminhash into (h,m)-HMH fingerprints that can be tuned for expected sub-sampling levels to minimize false positive rate in genomic comparisons.
• Optimized Indexing Structure: Employs inverted indexes that accept any fingerprint type to achieve optimal query performance with time complexity linear in the size of the output.
• Scalability and Speed: Demonstrated processing of over one million bacterial genomes from GenBank in a few days on a small cluster, yielding order-of-magnitude speed improvements over current state-of-the-art while maintaining precision.

Scientific Applications:

• Comparative Genomics: Rapidly computes pairwise distances across large genome collections for large-scale comparative analyses.
• Phylogenetic Analysis: Provides fast distance estimates suitable for large-scale phylogenetic inference and tree construction.
• Microbial Diversity Studies: Enables scalable analysis of microbial diversity across extensive bacterial genome datasets such as GenBank.
• Large-Scale Genomic Queries: Facilitates fast, scalable querying and exploration of vast genomic databases.

Methodology:

Generalization of Hyperminhash into (h,m)-HMH fingerprints for tunable false-positive rates; an inverted-index structure using inverted indexes that supports arbitrary fingerprint types and yields query time linear in output size.