Indexing is a fundamental step in read mapping.
To maximize efficiency, ideal indexers must utilize long seeds while remaining robust to sequencing errors and genetic variations.
Existing schemes typically rely on probabilistic error tolerance at fixed sub-locations or approximate edit distances via Euclidean embeddings.
However, because edit-distance space is a metric space but not a normed space, approximations using inner-product spaces (like Euclidean space) are inherently lossy.
Here, we demonstrate that high-precision positioning is attainable in coordinate-less string space through multilateration, provided the discrete space is covered by a meticulously selected set of beacon strings.
We show that for any query, a comprehensive set of high-similarity candidates can be efficiently localized using a small subset of proximal beacons.
Leveraging these insights, we propose NavigaMer, a multi-tiered navigation system for string indexing.
NavigaMer retrieves candidate reference sequences by progressively narrowing the search space within the sequence universe, guided by beacon sets ranging from coarse-to-fine resolutions.
Experiments on simulated and real genomes demonstrate that NavigaMer is fully error-tolerant and highly accurate.
It identifies all reference candidates within a specified edit distance with minimal false positives, providing a high-sensitivity foundation for future read mappers.

Co-authors: Minghao Fang, Yiru He, Cheng Wang, Jinpu Cai, Yuxuan Wang, Zhenwei Huang, Shiyang Yu, Shiyang Ma, Yan Li, Hongyi Xin