寻找覆盖字符串区域的最小kmer的快速算法

Question

我有一个代表人类基因组的字符串，它是一个四元代码（alphabet = {A, C, T, G}）：

str = 'ACTGGTGCGAGACTGCGGGAACACTGAGCGGGCGAGACT'

问题是，通过将字符串划分为大小为bin_size的子字符串，我希望找到为每个子字符串跨越某个阈值T长度的唯一、不重叠的k-mers

例如，对于k=3、bin_size = 10和T = 0.6，它只需要2个唯一的、不重叠的3-mersACT&GCG要跨越长度为10的每个子字符串的6个字符：

ACTGGTGCGA GACTGCGGGA ACACTGAGCG GGCGAGACT

我想到的一种方法是首先使用Bloom过滤器计算k-mers，然后检查每个子串中最流行的k-mers。但不重叠的标准，以及我想找到最少的唯一k-mers，表明这可能是一个优化问题（不知何故）。是否已有一种算法可以解决类似的问题

**编辑：** 实际上，k=16，bin_size = 1 000 000，以及字符串的总长度len(str) = 3 000 000 000

实际上，k-mers的重叠不应超过某些重叠，即overlap = 3 letters