一种基于De Bruijn图的多序列比对方法

摘要

本发明提供了一种基于De Bruijn图的多序列比对方法，包括以下步骤：步骤S100，将输入序列分割成序列片段；步骤S200，利用序列片段构造De Bruijn图，每一序列片段为一节点；步骤S300，利用深度优先搜索算法剔除De Bruijn图中的环路；步骤S400，利用Bellman‑Ford算法获取最优权值路径作为中心序列；步骤S500，将中心序列和输入序列两两比对，并更新中心序列；步骤S600，更新后的中心序列再与输入序列两两比对，得到比对结果。