一种用于大规模序列匹配的高效空间优化动态规划算法

本发明提供了一种用于大规模序列匹配的高效空间优化动态规划算法，包括以下步骤：输入与预处理；序列分块；初始化全局得分矩阵；初始化一维动态规划数组，块内动态规划计算，计算匹配得分，剪枝判断，更新一维动态规划数组，更新全局得分矩阵；按照块的顺序，合并得分，处理块间的匹配依赖，计算全局最优得分；结果输出。本发明能够实现将空间复杂度从O(mn)降低至O(n)，显著提高计算效率，在保证匹配精度的前提下，大幅降低计算资源的需求，适用于DNA序列比对、文本相似度计算等需要处理超长序列的场景。