一种针对大规模Read Mapping的高效DBG索引方法

作者：于长永; 李俊杰; 马海涛; 赵宇海

来源：东北大学学报(自然科学版), 2023, 44(06): 770-776.

• de Bruijn graph
• 索引
• read mapping(序列映射)
• FM-index
• 参考序列

为了能够回答生物信息学中关于de Bruijn graph(DBG)的两个问题——(1)对于任意的k-mer,回答其是否为DBG的顶点，(2)对于DBG的任意顶点，回答其邻接信息(入边和出边),提出了一种针对大规模read mapping的高效DBG索引方法.本文将以上两个问题转化为非重复多路径上的k-mer和(k+1)-mer的确切查找问题，并利用FM-index进行解决.首先，对给定的参考序列进行压缩，即非重复多路径的发现，从而压缩了序列中大量存在的重复(k+1)-mer.其次，基于非重复多路径FM-index对DBG进行索引.查找k-mer是否出现在DBG上，若找到，给出该k-mer的直接前驱和直接后继结点，从而提高时空效率.最后，在62种大肠杆菌菌株的基因组上进行实验.实验结果表明，所提出的方法可以高效地对多参考序列的DBG进行索引.

• 单位
  东北大学