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

A De Bruijn Graph Localization Algorithm Based on Minimal Set of Edges

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

A DBG(de Bruijn graph)model called MiniDBG for gene sequence alignment is proposed.It can store the position list of the minimum edge set,and effectively locate any node,edge and path on the graph through the position list,so as to achieve sequence alignment of genes.The MiniDBG model and the path location algorithm based on the model are introduced,and the algorithm is proved.Meanwhile,the MiniDBG is compared with the path location method based on BWT and location list.Experimental results show that the performance of MiniDBG is better than those of the other two methods in the case of frequent alignment.