Fig. 1

A toy example showing how an x-mer-based algorithm (c) can more effectively handle low-complexity repetitive regions and high-complexity variant-dense regions than a k-mer-based algorithm (b), and an algorithm using gapped x-mers (d) can further improve variant-dense regions. a The optimal alignment result and some candidate suboptimal alignment results of the example query mapping to the example reference. The reference is labeled as variant-dense regions and duplicated regions. b–d Matches of k-mers/x-mers/gapped x-mers highlighted in blue represent matches that agree with the optimal alignment. Matches of k-mers/x-mers/gapped x-mers highlighted in gray represent matches that do not agree with the optimal alignment but support suboptimal ones. The algorithm will then identify all unique offsets (positions of the query in the reference) to which any k-mer/x-mer/gapped x-mer maps. For each such offset, the algorithm may attempt to extend the k-mer/x-mer/gapped x-mer matches into neighboring base pairs to produce an alignment for the query at that position. Each dotted line connecting k-mers/x-mers/gapped x-mers represents a unique query offset where such an extension may occur. b K-mers 4 and 5 match each multiple offsets in the reference, while k-mers 1–3 have no matches. c X-mers 1–3 each match 1–2 offsets in the reference. d Gapped x-mers 1–2 match a single offset in the reference. Each “_” in a gapped x-mer represents a 1 bp gap