Finimizers: Variable-length bounded-frequency minimizers fork-mer sets

we know 7. Construction. The input was preprocessed into canonical unitigs before index construction, using GGCAT [11]. The time for this preprocessing in not included in the construction times. We then employed a heuristic method to reduce dummy nodes in the SBWT on all datasets. The method 8 is described in the supplementary materials, and may be of independent interest. From here, for k = 31 and m = 20 SSH ASH ,with otherwise default parameters, took 11, 3, and 2 minutes to construct, respectively, for the Metagenome, Nanopore, and E.Coli datasets, with peak memory of 11GB, 4GB, and 2GB. For the same k, construction of the double-stranded F INITO index was longer, resp.: 299, 58, and 13 minutes (peak memory, resp.: 140GB, 42GB, and 12GB), more than half 7As described in [33], SSH ASH only claims to solve the problem of k-mer lookup, but the implementation requires only trival modifications to report k-mer localization. 8See https://github.com/jnalanko/unitig_flipper .CC-BY 4.0 International licenseavailable under a (which was not certified by peer review) is the author/funder, who has granted bioRxiv a license to display the preprint in perpetuity. It is made The copyright holder for this preprintthis version posted February 21, 2024. ; https://doi.org/10.1101/2024.02.19.580943doi: bioRxiv preprint 10 0 2 4 6 8 10 t 0 1 2 3# distinct finimizers ×107 # Distinct finimizers 0 2 4 6 8 10 t 0 10 20 30Average length Average finimizer length 0 2 4 6 8 10 t 0.0 0.1 0.2 0.3 0.4 0.5 Sampling density DBG sampling density 0 2 4 6 8 10 t 0 1 2 3 4 5Average frequency Average finimizer frequency k = 21 k = 31 k = 63 k = 127 Fig. 5. Statistics on shortest t-bounded finimizers on the 3682 E. coli genomes dataset. The DBG sampling density at bottom left is defined as the number of DBG occurrences of all distinct finimizers, divided by the number of distinct nodes in the DBG. The frequency plotted at the bottom right is the average number of DBG occurrences of finimizers. TABLE I Statistics on the raw genomic datasets.k-mer counts considers canonicalk-mers. We derived unitigs for each dataset and built a SBWT. $ original is the number of dummy nodes in the original unitig ordering, and $ flipped is the number after applying the unitig orientation heuristic described in Section V. Sequences Total length Unique 31-mers Unitigs Unitig length $ original $ flipped E. coli 745,409 18,957,578,183 170,648,610 8,939,732 438,840,570 52,528,157 4,838,079 Metagenome 17,336,887 8,703,117,274 2,761,523,935 76,958,596 4,182,332,581 517,193,809 191,843,337 Nanopore 501,216 2,888,677,990 483,259,051 29,581,392 1,370,700,811 119,248,987 10,994,322 of which was spent on SBWT construction9. We remark that although F INITO construction time is higher than SSH ASH, it still acceptably fast in real terms. Moreover, the construction of FINITO currently runs on a single thread, whereas SSH ASH uses 8. The bottleneck in our construction process—SBWT computation—could be significantly sped up with paralleliza- tion, a task we leave for future work. Queries. We generated two types of query sets: random sequences of length 200 (negative queries ), the k-mers of which are highly unlikely to have any matches in the datasets; and positive queries were generated by randomly sampling 200-mers from each dataset. We measured the time F INITO and SSH ASH took to look up every k-mer in 500,000 positive and negative length-200 sequences, for various values ofk (see Figure 6). To match Sshash queries, we consider ak-mer found if it is found in either forward or reverse complement orienta- tion. As mentioned before, we achieved this either by using an index that contains both the forward and reverse complement strains of all unitigs, and storing the permutation mapping reverse and forward counterparts to report the localizations 9Construction time for the single-stranded index were faster, resp. 131, 26, 8 minutes (using resp. 4.6, 2, 2.5GB of RAM), with a corresponding slow down in query time. on the original DNA strand, or by using an index containing only one direction, but running all queries in both directions. The former approach being roughly twice as fast but taking twice the space as the latter. The index size of F INITO was typically larger than Sshash, but the query times of both tools were similar, within a small constant factor from each other, depending on the configuration and the dataset, with negative queries favoring F INITO . Alanko et al. [4] provide several data structures to support ExtendRight queries on the SBWT. We use their so-called Plain Matrix representation. Other data structures could reduce the size of our index at the expense of an increased query time, at least with current SBWT incarnations. In this respect, it is worth noting that SBWT data structures are still very new, and that further engineering may yet lead to significant performance gains. VII. C ONCLUSIONS AND FUTURE WORK In the 20 years since minimizers emerged, researchers have invented various heuristics to avoid very frequent minimizers. In this paper we have demonstrated an alternative solution to the problem that works by letting the minimizer length vary. This way, when indexing DSPSS representations, we can get a guarantee for the maximum frequency and thus .CC-BY 4.0 International licenseavailable under a (which was not certified by peer review) is the author/funder, who has granted bioRxiv a license to display the preprint in perpetuity. It is made The copyright holder for this preprintthis version posted February 21, 2024. ; https://doi.org/10.1101/2024.02.19.580943doi: bioRxiv preprint 11 0 20 40 60 0.0 0.5 1.0 1.5 2.0 2.5 3.0 3.5 4.0 Time (µs/kmer) 12 16 20 12 1620 E. coli 0 20 40 60 0.0 0.5 1.0 1.5 2.0 2.5 3.0 3.5 4.0 12 16 20 12 16 20 Nanopore 0 20 40 60 0.0 0.5 1.0 1.5 2.0 2.5 3.0 3.5 4.0 12 16 12 16 20 Metagenome Sshash Finito Finito+rev k=21 k=31 0 20 40 60 Index size (bits/kmer) 0.0 0.5 1.0 1.5 2.0 2.5 3.0 3.5 4.0 Time (µs/kmer) 12 16 20 1620 0 20 40 60 Index size (bits/kmer) 0.0 0.5 1.0 1.5 2.0 2.5 3.0 3.5 4.0 16 20 1620 0 20 40 60 Index size (bits/kmer) 0.0 0.5 1.0 1.5 2.0 2.5 3.0 3.5 4.0 16 12 16 20 Fig. 6. Query performance of SSH ASH and F INITO . Top: Time and index size for positive queries for varying k and m on each dataset. Bottom: Time and index size for negative queries.SShash results for Metagenome with k = 21, m = 20 are not plotted because construction failed due to collisions of 64-bit hash values. maximum localization query time. A distinct advantage the Shortest Unique Finimizers, we have introduced, have over minimizers is that they are parameter free. While our current prototype is already competitive with state-of-the-art minimizer-based localization methods, we be- lieve it can be optimized further, e.g., by adding word- level parallelism to our ContractLeft implementation, and by reducing the time and space for ExtendRight by engineering the structures from [4] to use faster recent predecessor [13] and rank [3], [8] structures. The SBWT offers a convenient way to index finimizers for lookup, however more direct methods based on, for example, multiple pattern matching data structures (e.g., [39]), may lead to smaller and faster indexes. The principle challenge (compared to minimizers) is to deal with variable-length keys. In this respect, exploring trie-based solutions may be fruitful. Finally, interesting applications for finimizers beyond k- mer localization include: skipping heuristics in pseudoalign- ment [6]; approximate k-mer matching; and replacing hashing with finimizers in spectrum-preserving tilings [16]. A C OMPETING INTERESTS No competing interest is declared. B A UTHOR CONTRIBUTIONS STATEMENT All authors contributed equally. C A CKNOWLEDGMENTS This work was supported in part by the Academy of Finland via grants 339070 and 351150.

[1] P. Abedin, M. O. Külekci, and S. V . Thankachan. A survey on shortest unique substring queries. Algorithms, 13(9):224, 2020. [2] J. N. Alanko, E. Biagi, and S. J. Puglisi. Longest common prefix arrays for succinct k-spectra. In Proc. SPIRE, LNCS 14240, pages 1–13. Springer, 2023. [3] J. N. Alanko, E. Biagi, S. J. Puglisi, and J. Vuohtoniemi. Subset wavelet trees. In Proc. SEA, LIPIcs 265, pages 4:1–4:14. Schloss Dagstuhl, 2023. [4] J. N. Alanko, S. J. Puglisi, and J. Vuohtoniemi. Small searchable k-spectra via subset rank queries on the spectral Burrows-Wheeler transform. In Proc. ACDA, pages 225–236. SIAM, 2023. [5] D. Belazzougui and F. Cunial. Indexed matching statistics and shortest unique substrings. In Proc. SPIRE 2014, pages 179–190. Springer, 2014. [6] N. L. Bray, H. Pimentel, P. Melsted, and L. Pachter. Near-optimal probabilistic RNA-seq quantification. Nature Biotechnology, 34(5):525– 527, 2016. [7] R. Cánovas and G. Navarro. Practical compressed suffix trees. In P. Festa, editor, Proc. 9th International Symposium Experimental Al- gorithms (SEA), volume 6049 of Lecture Notes in Computer Science, pages 94–105. Springer, 2010. [8] M. Ceregini, F. Kurpicz, and R. Venturini. Faster wavelet trees with quad vectors. CoRR, abs/2302.09239, 2023. [9] R. Chikhi, A. Limasset, S. Jackman, J. T. Simpson, and P. Medvedev. On the representation of de Bruijn graphs. In Proc. RECOMB, LNCS 8394, pages 35–55. Springer, 2014. [10] R. Chikhi, A. Limasset, and P. Medvedev. Compacting de Bruijn graphs from sequencing data quickly and in low memory. Bioinformatics, 32(12):i201–i208, 06 2016. [11] A. Cracco and A. Tomescu. Extremely fast construction and querying of compacted and colored de Bruijn graphs with GGCAT. Genome res., 05 2023. [12] S. Deorowicz, M. Kokot, S. Grabowski, and A. Debudaj-Grabysz. KMC 2: fast and resource-frugal k-mer counting. Bioinformatics, 31(10):1569– 1576, 2015. [13] D. Díaz-Domínguez, S. Dönges, S. J. Puglisi, and L. Salmela. Simple runs-bounded FM-index designs are fast. In Proc. SEA, LIPIcs 265, pages 7:1–7:16. Schloss Dagstuhl, 2023. [14] B. Ekim, B. Berger, and R. Chikhi. Minimizer-space de bruijn graphs: Whole-genome assembly of long reads in minutes on a personal com- puter. Cell Systems, 12(10):958–968.e6, 2021. .CC-BY 4.0 International licenseavailable under a (which was not certified by peer review) is the author/funder, who has granted bioRxiv a license to display the preprint in perpetuity. It is made The copyright holder for this preprintthis version posted February 21, 2024. ; https://doi.org/10.1101/2024.02.19.580943doi: bioRxiv preprint 12 [15] M. Erbert, S. Rechner, and M. Müller-Hannemann. Gerbil: a fast and memory-efficient k-mer counter with GPU-support. Algorithms for Molecular Biology, 12(9), 2017. [16] J. Fan, J. Khan, G. E. Pibiri, and R. Patro. Spectrum preserving tilings enable sparse and modular reference indexing. In Proc. RECOMB, LNCS 13976, pages 21–40. Springer, 2023. [17] U. Ferraro-Petrillo, M. Sorella, G. Cattaneo, R. Giancarlo, and S. E. Rombo. Analyzing big datasets of genomic sequences: fast and scalable collection of k-mer statistics. BMC Bioinformatics, 20(Suppl 4):138, 2019. [18] J. Fischer. Combined data structure for previous-and next-smaller-values. Theoretical Computer Science, 412(22):2451–2456, 2011. [19] G. Holley and P. Melsted. Bifrost: highly parallel construction and indexing of colored and compacted de Bruijn graphs. Genome biology, 21(1):1–20, 2020. [20] C. Jain et al. Weighted minimizer sampling improves long read mapping. Bioinf., 36(Suppl 1):i111–i118, 07 2020. [21] I. B. Jeffery et al. Differences in fecal microbiomes and metabolomes of people with vs without irritable bowel syndrome and bile acid malabsorption. Gastroenterology, 158(4):1016–1028, 2020. [22] M. Karasikov, H. Mustafa, D. Danciu, M. Zimmermann, C. Barber, G. Rätsch, and A. Kahles. Metagraph: Indexing and analysing nucleotide archives at petabase-scale. BioRxiv, 2020. [23] J. Khan, M. Kokot, S. Deorowicz, and R. Patro. Scalable, ultra-fast, and low-memory construction of compacted de Bruijn graphs with Cuttlefish 2. Genome Biology, 23, 09 2022. [24] H. Li. Aligning sequence reads, clone sequences and assembly contigs with bwa-mem. arXiv preprint arXiv:1303.3997, 2013. [25] H. Li. Minimap2: pairwise alignment for nucleotide sequences. Bioin- formatics, 34(18):3094–3100, 05 2018. [26] C. Marchet, C. Boucher, S. J. Puglisi, P. Medvedev, M. Salson, and R. Chikhi. Data structures based on k-mers for querying large collections of sequencing data sets. Genome Res., 31(1):1–12, 2021. [27] C. Marchet, Z. Iqbal, D. Gautheret, M. Salson, and R. Chikhi. Reindeer: efficient indexing of k-mer presence and abundance in sequencing datasets. Bioinf., 36:i177–i185, 07 2020. [28] C. Marchet, M. Kerbiriou, and A. Limasset. BLight: efficient exact associative structure for k-mers. Bioinformatics, 37(18):2858–2865, 2021. [29] G. Navarro. Compact Data Structures – A practical approach. Cam- bridge University Press, 2016. [30] J. Nyström-Persson, G. Keeble-Gagnère, and N. Zawad. Compact and evenly distributed k-mer binning for genomic sequences. Bioinformatics, 37(17):2563–2569, 2021. [31] E. Ohlebusch, S. Gog, and A. Kügel. Computing matching statistics and maximal exact matches on compressed full-text indexes. In Proc. SPIRE 2010, pages 347–358. Springer, 2010. [32] Y . Orenstein et al. Designing small universal k-mer hitting sets for improved analysis of high-throughput sequencing. PLoS Computational Biology, 13(10):e1005777, 2017. [33] G. E. Pibiri. Sparse and skew hashing of K-mers. Bioinformatics, 38(Suppl 1):i185–i194, 06 2022. [34] A. Rahman and P. Medevedev. Representation of k-mer sets using spectrum-preserving string sets. J. Computational Biology, 28(4):381– 394, 2021. [35] M. Roberts et al. A preprocessor for shotgun assembly of large genomes. J. Computational Biology, 11(4):734–752, 2004. [36] M. Roberts, W. Hayes, B. R. Hunt, S. M. Mount, and J. A. Yorke. Reducing storage requirements for biological sequence comparison. Bioinformatics, 20(18):3363–3369, 07 2004. [37] S. Schleimer, D. S. Wilkerson, and A. Aiken. Winnowing: local algorithms for document fingerprinting. In Proceedings of the 2003 ACM SIGMOD international conference on Management of data, pages 76–85, 2003. [38] S. Schmidt, S. Khan, J. N. Alanko, G. E. Pibiri, and A. I. Tomescu. Matchtigs: minimum plain text representation of k-mer sets. Genome Biology, 24(1):1–32, 2023. [39] S. Wu and U. Manber. A fast algorithm for multi-pattern searching. Technical Report TR94-17, University of Arizona. Department of Com- puter Science Tucson, AZ, 1994. [40] H. Zheng, G. Marçais, and C. Kingsford. Creating and using minimizer sketches in computational genomics. J. Computational Biology, 30(0):1– 26, 2023. .CC-BY 4.0 International licenseavailable under a (which was not certified by peer review) is the author/funder, who has granted bioRxiv a license to display the preprint in perpetuity. It is made The copyright holder for this preprintthis version posted February 21, 2024. ; https://doi.org/10.1101/2024.02.19.580943doi: bioRxiv preprint Supplementary material for Finimizers: Variable-length bounded-frequency minimizers for k-mer sets Jarno N. Alanko, Elena Biagi, Simon J. Puglisi 1 k-bounded Matching Statistics Algorithm 1 k-bounded matching statistics. Input: A query string Q and a data structure supporting ExtendRight and ContractLeft on the padded k-mer spectrum. Output: MSk[1..|Q|] 1: [ℓ, r] ← [1, n] ▷ The current colexicographic interval 2: d ← 0 ▷ The length of the current match, up to k 3: MSk[1..|Q|] ← Array of length |Q|. 4: for i = 1..|Q| do 5: while d > 0 and ExtendRight([ℓ, r], Q[i]) = ∅ do 6: [ℓ, r] ← ContractLeft([ℓ, r]) 7: d ← d − 1 8: if ExtendRight([ℓ, r], Q[i]) ̸= ∅ then 9: [ℓ, r] ← ExtendRight([ℓ, r], Q[i]) 10: d ← min(k, d + 1) 11: MSk[i] ← (d, r − ℓ + 1, ℓ) ▷ Len, Freq, Colex start Definition 1. (k-bounded matching statistics) The k-bounded matching statistics of a query sequence Q[1..m], versus a padded k-spectrum R+, is the array MS k[1..m] such that MS k[i] = (di, pi, ℓi), where di is the largest non-negative integer such that Q(i − di..i] is a suffix of at least one k-mer in R+, pi is the DBG frequency of Q(i − di..i] and ℓi is the start of the colexicographic interval of Q(i − di..i]. Theorem 1. Given constant-time ContractLeft and ExtendRight queries on the padded k-spectrum R+, Algorithm 1 computes M Sk for query Q in time O(|Q|). Proof. The algorithm maintains the invariant that at the end of iteration i, the interval [ℓ, r] is the interval of the longest suffix of Q[1..i] that occurs as suffix of at least one k-mer. If [ ℓ, r] is the longest match at the end of iteration i − 1, then at iteration i after lines 5 – 7, we have the interval of the longest match ending at i − 1 that can be extended with Q[i], or the interval of the empty string if Q[i] does not exist in any k-mer. If the longest match ending at i is nonempty, it is a right extension of such a string, so the invariant is maintained. The algorithm works in O(|Q|) time because d is always non-negative, and the while-loop can run only d times because d is incremented at most |Q| times, and every run of the while-loop decrements d. 1 .CC-BY 4.0 International licenseavailable under a (which was not certified by peer review) is the author/funder, who has granted bioRxiv a license to display the preprint in perpetuity. It is made The copyright holder for this preprintthis version posted February 21, 2024. ; https://doi.org/10.1101/2024.02.19.580943doi: bioRxiv preprint 2 Shortest Frequency-bounded Suffixes Algorithm 2 Shortest frequency-bounded suffix statistics. Input: A query string Q, frequency upper bound t, and a data structure supporting ExtendRight and ContractLeft on the padded k-mer spectrum. Output: SFSk,t[1..|Q|] Assumes all characters of the query Q exist in the index at least once. 1: [ℓ, r] ← [1, n] ▷ The current colexicographic interval 2: d ← 0 ▷ The length of the current match, up to k 3: SFSk,t[1..|Q|] ← Array of length |Q| initialized to values ⊥ 4: for i = 1..|Q| do 5: while ExtendRight([ℓ, r], Q[i]) = ∅ do 6: [ℓ, r] ← ContractLeft([ℓ, r]) 7: d ← d − 1 8: [ℓ, r] ← ExtendRight([ℓ, r], Q[i]) 9: d ← min(k, d + 1) 10: while |ContractLeft([ℓ, r], 1)| ≤ t do 11: [ℓ, r] ← ContractLeft([ℓ, r]) 12: d ← d − 1 13: if r − ℓ + 1 ≤ t then 14: SFSk,t[i] ← (d, r − ℓ + 1, ℓ) Definition 2. (Shortest frequency-bounded suffixes) The shortest suffix statistics of a query sequenceQ[1..m], versus a padded k-spectrum R+, is the array SF Sk,t[1..m] such that SF Sk,t[i] = (di, pi, ℓi), where di is the smallest positive integer such that Q(i − di..i] is a suffix of pi (pi ≤ t) k-mers in R+, and ℓi is the start of the colexicographic interval of Q(i − di..i]. If no such di exists, SF Sk,t[i] = ⊥. Theorem 2. Given constant-time ContractLeft and ExtendRight queries on the padded k-spectrum R+, Algorithm 2 computes SF Sk for query Q in time O(|Q|). Proof. The algorithm maintains the invariant that at the end of iteration i, the interval [ℓ, r] is the interval of the shortest suffix of Q[1..i] that occurs as suffix of at most t k -mers, if exists, or otherwise [ℓ, r ] is the longest suffix of Q[1..i] that occurs in the k-mers. To see this, we consider two cases. • (i) If [ ℓ, r] is the interval of the longest match at the end of iteration i − 1, then in iteration i, the lines 5 – 9 update it to the longest match up to position i. If the interval becomes of size ≤ t after lines 5 – 9, then lines 10 – 12 contract it to the shortest match with frequency at most t and the invariant continues to hold. Otherwise if the interval size did not shrink to at most t after lines 5 – 9, then lines 10 – 12 are not run and the interval remains the longest match. The invariant continues to hold. • (ii) If [ ℓ, r] is the shortest match with frequency at most t at the end of iteration i − 1, then – (iia) if the loop on lines 5 – 7 is run at least once, it becomes the longest match after the right extension at line 8 (a left contraction was needed for a right extension, so the positions that were contracted can not be a part of the longest match). If the loop on lines 10 – 12 is run at least once, it is contracted to the shortest match of frequency at most t, otherwise the interval is not changed and it remains the longest match, maintaining the invariant. – (iib) if the loop on lines 5 – 7 is not run at least once, then the interval remains unchanged up to line 8, and the right extension on line 8 can only make the frequency smaller, so the frequency remains at most t. Lines 10 – 12 contract it to the shortest match with frequency at most t, maintaining the invariant. If the assignment on line 14 happens, it is correct since then [ l, r] is of size at most t and by lines 10 – 12 the length d is minimal. If the assignment does not happen, then SF Sk[i] is correctly left as ⊥ since now the interval [ ℓ, r] represents the longest available match ending at i, and thus a match with frequency t or less can not exist, as it would have to be longer than the longest match. The algorithm works in O(|Q|) time because the while-loop conditions are false at most |Q| times each, and every time they evaluate to true, the left contraction inside can be charged to a distinct right extension on line 8, which is executed |Q| times. 2 .CC-BY 4.0 International licenseavailable under a (which was not certified by peer review) is the author/funder, who has granted bioRxiv a license to display the preprint in perpetuity. It is made The copyright holder for this preprintthis version posted February 21, 2024. ; https://doi.org/10.1101/2024.02.19.580943doi: bioRxiv preprint 3 Localization Proof of Correctness Suppose we have query a Q such that k-mer α = Q(i − k..i] is known to exist in the DBG according to the matching statistics information. We now prove that our algorithm localizes α to the correct unitig. • Case 1: Localization via the branch dictionary . Suppose there exists a substring β = Q[p..q] with i − k + 1 ≤ p ≤ q ≤ i such that the DBG frequency of β is 1, and β is the suffix of a k-mer that is at the start of a unitig X. Further, suppose that q is the largest possible (up to i) with this property. Then, our algorithm localizes α to X. Let δ = Q[q + 1..i]. First, we claim that βδ is a substring of X. – Proof. For a contradiction, suppose this is not the case. Then, since β is unique in the DBG and α is known to exist in the DBG, it must be the case that X ends before the end of δ, that is, |X| < k + |δ|, which means that the path labeled with βδ contains an edge (u, v) such that u has outdegree larger than 1. Let βδ[1..r] be the path label up to and including v. This path label is still unique in DBG, and it is a suffix of the first k-mer of its unitig. But then q was not the largest possible since position q + r also fulfills the conditions imposed on q, contradiction. Let α = γβδ . We claim that γβ is a substring of X. – Proof. Since α exists in the DBG and β is unique in the DBG, the occurrence of β in the graph has an incoming path with label γ. Since β = X[k − |β| + 1..k], we have that k − |β| − |γ| + 1 ≥ 1 and so X[k − |β| − |γ | + 1..k] = γβ. Since β is DBG-unique, and both γβ and βδ are in X, we conclude that α = γβδ must also be in X. • Case 2: Localization via the finimizer dictionary. Suppose there does not exist β in the case above. Let ρ be the shortest unique finimizer of α, so α = τ ρτ′. Then our algorithm localizes α to the unitig which contains an occurrence of ρ the furthest from the start of the unitig. First, we claim that the path of α is non-branching DBG. – Proof. Let v1, . . . , vk+1 be the path labeled with α. We consider incoming branches and outgoing branches as separate cases: ∗ Suppose there exists j > 1 such that the indegree of vj is at least 2. Then, ρ is the suffix of two distinct k-mers, so it is not unique in the DBG, a contradiction. ∗ Suppose there exists j < k + 1 such that the outdegree of vj is at least 2. Then, vj must be after the ending point of ρ on the path, since otherwise ρ is not DBG-unique. But then the label of the subpath from the start of ρ to the node vj+1 satisfies the conditions for β, which is a contradiction since such β was assumed to not exist. The global offset stored for ρ is the one furthest from the unitig start. We claim that the global offset of ρ that we have stored is in the unitig that contains α: – Proof. The string ρτ ′ is fully contained in the same unitig as ρ, because otherwise the path of ρτ ′ would be branching, but that cannot be that case since α = τ ρτ′ in non-branching. Since we are at the unitig X that contains ρ the furthest to the right as possible, the whole string α = τ ρτ′ must be found fully in X. 3 .CC-BY 4.0 International licenseavailable under a (which was not certified by peer review) is the author/funder, who has granted bioRxiv a license to display the preprint in perpetuity. It is made The copyright holder for this preprintthis version posted February 21, 2024. ; https://doi.org/10.1101/2024.02.19.580943doi: bioRxiv preprint