基于FPGA的基因序列组装算法计算加速方法

摘要

本发明公开了一种基于FPGA的基因序列组装算法计算加速方法，包括CPU和FPGA的异构计算平台，该方法包括以下步骤：1)过滤阶段，在CPU主机上将查询序列Kmer化得到一系列种子，然后依次寻找所有种子在参考序列区间上的匹配位置，即命中；然后对各个命中区间中种子重叠的碱基数目进行计数，挑选数量大于阈值的位置作为候选位置；2)扩展阶段，通过优化后的Smith‑Waterman算法，以候选位置作为起点开始扩展，通过CPU对矩阵的分块加以控制；FPGA对每个分块矩阵进行运算得到部分回溯路径；3)CPU将这些回溯路径依次进行拼接从而获取完整的回溯路径。本发明采用一种优化后的Smith‑Waterman算法，能大幅提高序列比对的运行速度。