1

我有数据需要保持在输入的确切序列（基因组测序）中，我想搜索大约 10 亿个节点，每个节点约有 18 个成员来定位模式。

显然，对于这么大的数据集，速度是一个问题，实际上我目前没有任何数据可以用作离散键，因为搜索的基础是定位和隔离（但不是删除）重复项。

我正在寻找一种可以在相对较短的时间内遍历数据以定位这些模式和相似性的算法，并且我可以计算出正则表达式进行比较，但我不确定如何获得更快的搜索比 O(n)。

任何帮助，将不胜感激。

谢谢

4

1 回答 1

0
  • 可能您想要的称为“从头组装”
  • 一种方法是计算 N-mers，并在索引中使用它们
  • 如果您需要部分匹配/不匹配，nmers 将变得更加重要
  • 如果十亿 := 1E9，python 可能太弱了
  • 还要注意 18 个碱基* 2 位 := 36 位信息来枚举它们。这暂时接近 32 位，可以放入 64 位。散列/比特摆弄可能是一种选择
于 2012-09-18T09:58:32.720 回答