Haskell中的慢生物信息学算法--丛集查找算法

Question

我正在研究著名的丛集发现问题来学习Haskell。该问题的一部分涉及到将称为kmers的核苷酸序列分解成以下子序列：

ACTGCA -> [ACT,CTG,GCA]

在上面的例子中，这个滑动窗口生成了长度为k，3的所有可能的kmers。

问题是我的简单算法太慢，无法在大肠杆菌基因组上工作。其他使用较慢语言的算法可以在几秒钟内生成kmer列表。

以下是我所写的：

kmerBreak k genome@(x : xs)
  | k <= length genome = take k genome : kmerBreak k xs
  | otherwise = []

我希望得到一些关于如何提高这个简单算法性能的反馈。以及我一般对Haskell的使用。

Answer 1

简单的错误:列表不包含它的长度，所以length遍历列表来计算长度。这意味着kmerBreak在输入的大小上以时间二次形式运行。一个简单的解决方法是检查take k genome是否确实长度为k，假设k很小。或者，您可以将genome的长度作为递归函数的额外参数进行跟踪。

Answer 2

正如前面的海报所建议的，您可以检查take k是否返回长度k的列表。这样做是可能的：

import Data.List (tails)
kmerBreak k = takeWhile ((==k) . length) . map (take k) . tails