基于最小边集的De Bruijn图定位算法

针对基因序列比对问题提出了一种DBG(de Bruijn图)模型,称为MiniDBG.它可以存储最小边集的位置列表,并通过位置列表有效地定位图上的任何节点、边和路径,从而实现对基因的序列比对.介绍了MiniDBG模型及基于该模型的路径定位算法,并对算法进行了证明.同时将MiniDBG与基于BWT和基于位置列表的路径定位方法进行了比较,实验结果表明,在频繁比对的情况下,MiniDBG的性能优于其他两种方法.