基于波前算法的DNA序列向量化并行比对方法和装置

1.一种基于波前算法的DNA序列向量化并行比对方法，其特征在于，所述方法包括：获取待比对序列和参考序列；设置初始罚分为0、初始波前坐标为（0,0）、当前待比对位置为初始波前所在的位置；查询当前待比对位置所涉及到的所有对角线，将前 w 条对角线作为当前组 w 条对角线； w 为预设向量宽度；在当前组 w 条对角线上设置标记向量，根据所述标记向量对所述当前待比对位置进行向量化并行的序列拓展计算，得到当前组 w 条对角线对应的罚分的波前；在当前组 w 条对角线上，通过向量化并行，计算下一波前的初始坐标；对下一组 w 条对角线，继续进行下一波前的初始坐标计算，直到遍历完所有对角线为止；根据下一个波前的罚分，继续对下一个罚分进行计算，直到遍历完两条序列的所有碱基为止；根据罚分情况，从罚分值大到小的顺序获取对应的波前坐标，确定最终的比对结果；其中，在当前组 w 条对角线上设置标记向量，根据所述标记向量对所述当前待比对位置进行向量化并行的序列拓展计算，得到当前组 w 条对角线对应的罚分的波前，包括：将当前组 w 条对角线对应的罚分的波前坐标初始化为当前初始位置的坐标；设置标记向量，并将所述标记向量各个元素的初值均设置为1；判断当前组 w 条对角线上的元素能否序列拓展，如果能，则将对应位标记为1；如果不能，则将对应位标记为0；将判断结果保存在向量 中；将所述标记向量和向量 进行向量按位与操作，将得到的结果保存到所述标记向量中；将当前波前的横纵坐标与所述标记向量进行向量加操作，将得到的结果作为计算后的波前坐标；判断所述标记向量的所有元素是否全为0，如果不全为0，则继续进行向量化并行的序列拓展计算；如果全为0，则得到当前组 w 条对角线对应的罚分的波前。 2.根据权利要求1所述的方法，其特征在于，在当前组 w 条对角线上，通过向量化并行，计算下一波前的初始坐标，包括：设置掩码向量；所述掩码向量的宽度为 w ；进行向量逻辑计算，依次判断当前 w 条对角线是否在上一个罚分的波前范围内；若在上一个罚分的波前范围内，则将所述掩码向量中对应位标记为1，否则将所述掩码向量中对应位标记为0；使用向量指令，确定所述掩码向量中标记为1和标记为0所对应元素的计算结果；所述计算结果包括三个向量，分别为插入、删除以及不匹配的比对结果向量；将所述掩码向量中标记为1和标记为0所对应元素的计算结果的相同类型比对结果向量进行向量加运算，得到插入、删除以及不匹配的最终比对结果向量；计算不匹配的最终比对结果向量和插入的最终比对结果向量的最大值，并对得到的结果进行向量加1运算，得到当前波前碱基插入分量的结果；计算不匹配的最终比对结果向量和删除的最终比对结果向量的最大值，将得到的结果作为当前波前碱基缺失分量的结果；选择当前波前碱基缺失分量的结果、当前波前碱基插入分量的结果以及对不匹配的最终比对结果向量进行向量加1运算的结果中的最大值，并将所述最大值作为当前波前的不匹配分量的结果，将当前波前的不匹配分量的结果作为下一波前的初始坐标。 3.根据权利要求2所述的方法，其特征在于，掩码向量中标记为1所对应元素的计算结果的计算步骤包括：将前一个波前插入、删除、不匹配的比对结果分别保存到三个中间向量中；分别将三个中间向量和掩码向量进行向量按位与操作，将得到的结果分别保存到向量 中，得到掩码向量中标记为1所对应元素的计算结果。 4.根据权利要求2所述的方法，其特征在于，掩码向量中标记为0所对应元素的计算结果的计算步骤包括：将三个第一中间向量赋值为负无穷；对掩码向量进行向量按位取反操作，将得到的结果保存到向量 中；分别将三个第一中间向量和向量 进行向量按位与操作，将得到的结果分别保存到向量 中，得到掩码向量中标记为0所对应元素的计算结果。 5.一种基于波前算法的DNA序列向量化并行比对装置，其特征在于，所述装置包括：序列获取模块，用于获取待比对序列和参考序列；并行比对初始化模块，用于设置初始罚分为0、初始波前坐标为（0,0）、当前待比对位置为初始波前所在的位置；向量化并行比对模块，用于查询当前待比对位置所涉及到的所有对角线，将前 w 条对角线作为当前组 w 条对角线； w 为预设向量宽度；在当前组 w 条对角线上设置标记向量，根据所述标记向量对所述当前待比对位置进行向量化并行的序列拓展计算，得到当前组 w 条对角线对应的罚分的波前；在当前组 w 条对角线上，通过向量化并行，计算下一波前的初始坐标；对下一组 w 条对角线，继续进行下一波前的初始坐标计算，直到遍历完所有对角线为止；根据下一个波前的罚分，继续对下一个罚分进行计算，直到遍历完两条序列的所有碱基为止；比对结果确定模块，用于根据罚分情况，从罚分值大到小的顺序获取对应的波前坐标，确定最终的比对结果；向量化并行比对模块，还用于将当前组 w 条对角线对应的罚分的波前坐标初始化为当前初始位置的坐标；设置标记向量，并将所述标记向量各个元素的初值均设置为1；判断当前组 w 条对角线上的元素能否序列拓展，如果能，则将对应位标记为1；如果不能，则将对应位标记为0；将判断结果保存在向量 中；将所述标记向量和向量 进行向量按位与操作，将得到的结果保存到所述标记向量中；将当前波前的横纵坐标与所述标记向量进行向量加操作，将得到的结果作为计算后的波前坐标；判断所述标记向量的所有元素是否全为0，如果不全为0，则继续进行向量化并行的序列拓展计算；如果全为0，则得到当前组 w 条对角线对应的罚分的波前。 6.根据权利要求5所述的装置，其特征在于，向量化并行比对模块，还用于设置掩码向量；所述掩码向量的宽度为 w ；进行向量逻辑计算，依次判断当前 w 条对角线是否在上一个罚分的波前范围内；若在上一个罚分的波前范围内，则将所述掩码向量中对应位标记为1，否则将所述掩码向量中对应位标记为0；使用向量指令，确定所述掩码向量中标记为1和标记为0所对应元素的计算结果；所述计算结果包括三个向量，分别为插入、删除以及不匹配的比对结果向量；将所述掩码向量中标记为1和标记为0所对应元素的计算结果的相同类型比对结果向量进行向量加运算，得到插入、删除以及不匹配的最终比对结果向量；计算不匹配的最终比对结果向量和插入的最终比对结果向量的最大值，并对得到的结果进行向量加1运算，得到当前波前碱基插入分量的结果；计算不匹配的最终比对结果向量和删除的最终比对结果向量的最大值，将得到的结果作为当前波前碱基缺失分量的结果；选择当前波前碱基缺失分量的结果、当前波前碱基插入分量的结果以及对不匹配的最终比对结果向量进行向量加1运算的结果中的最大值，并将所述最大值作为当前波前的不匹配分量的结果，将当前波前的不匹配分量的结果作为下一波前的初始坐标。 7.根据权利要求6所述的装置，其特征在于，向量化并行比对模块中掩码向量中标记为1所对应元素的计算结果的计算步骤包括：将前一个波前插入、删除、不匹配的比对结果分别保存到三个中间向量中；分别将三个中间向量和掩码向量进行向量按位与操作，将得到的结果分别保存到向量 中，得到掩码向量中标记为1所对应元素的计算结果。 8.根据权利要求6所述的装置，其特征在于，向量化并行比对模块中掩码向量中标记为0所对应元素的计算结果的计算步骤包括：将三个第一中间向量赋值为负无穷；对掩码向量进行向量按位取反操作，将得到的结果保存到向量 中；分别将三个第一中间向量和向量 进行向量按位与操作，将得到的结果分别保存到向量 中，得到掩码向量中标记为0所对应元素的计算结果。