下一代测序（Next-generation sequencing，NGS）提供了巨大的机遇以核苷酸分辨率研究全基因组变异。由于巨大的数据量，NGS应用需要非常快速且准确的比对算法。大部分现有read比对算法基本上都采用种子和扩展策略，这本质上是顺序的，并且在更长reads上耗费更多时间。

我们开发了一种分而治之（divide-and-conquer）算法，叫做Kart，它通过将一条read分割成能够独立比对的小片段能够像短reads一样快地处理长reads。我们的实验结果表明更耗时的空位比对需要的平均片段大小为约20bp，而不管原始read长度。此外，它能够容忍更高的错误率。实验显示当错误率高达15%时，Kart比其他比对器在更长reads上花费更少的时间，并且仍然产生可靠的比对。

ABCD为完全匹配的simple pair

下载：https://github.com/hsinnan75/Kart/
语言：C++
时间：20170405
参考：Kart: a divide-and-conquer algorithm for NGS read alignment