实现机制：
1.算法
Smith-Waterman (SW) algorithm 算法是经典的局部比对算法，复杂度O(L r *L q )和序列的长度相关， Lr、Lq是要比对的两条序列。对于全基因组比对就无法满足性能要求，whole genome alignment algorithm (LASTZ) 基于BLAST的启发式seed-filter-extend算法，专门针对全基因组的比对进行的改进。
LASTZ的算法分为下面三个阶段：
88112bce-b3b2-4d3c-8188-e5299aa41f1d-image.png
(1)Seeding
使用尽可能完全匹配的片段(K-Mer)作为种子, 并把所有的种子保存为一张查询表。这些种子通常也就10几个碱基，因此假阳性很高，需要在下一步进行过滤。
(2)Filter
过滤步骤性能消耗占整个过程的98%以上。该算法对种子在两个方向进行延长，并计算比对的评分，评分低于某个阈值H x时终止延长。通过这些阈值的就是高分序列对high-scoring segment pair (HSP)，传递到下一步继续进行分析。HSP 大约100个碱基左右。
(3)采用动态规划(Dynamic programming)算法将HSP延长到1000个碱基左右。
2.GPU 单节点加速
Streaming Multiproces-sors (SMs)
3.Spark 多节点加速