基于多步双向De Bruijn图的变长kmer查询的顶点扩展方法

摘要

本发明涉及基因测序技术领域，提供了一种基于多步双向De Bruijn图的变长kmer查询的顶点扩展方法，包括：步骤A：读取测序数据源文件，构造多步双向De Bruijn图；步骤B：在所述多步双向De Bruijn图中对分叉顶点的变长kmer进行构造和统计；步骤C：在所述多步双向De Bruijn图中基于变长kmer查询的顶点扩展。本发明只选取一些分叉的顶点构建非常少的一些变长kmer，然后对这些分叉顶点进行定向解耦，无需对每种kmer长度都去构建一个De Bruijn图，可以方便快速地解决所有长度小于序列长度的repeat，最大化contig的长度和质量。

主权项

一种基于多步双向De Bruijn图的变长kmer查询的顶点扩展方法，其特征在于，包括：步骤A：读取测序数据源文件，构造多步双向De Bruijn图；步骤B：在所述多步双向De Bruijn图中对分叉顶点的变长kmer进行构造和统计；步骤C：在所述多步双向De Bruijn图中基于变长kmer查询的顶点扩展；所述步骤B中，对所述多步双向De Bruijn图中的顶点所有可能的分叉合并路径上的k+2长的变长kmer构造权重表，选择权重最高的一组分叉路径组合进行分叉路径上的双向边合并；所述步骤C中，对于一个给定的分叉顶点u，在查询顶点u所有的k+2长的变长kmer权重值之后，选择权重最高的一组分叉路径组合进行分叉路径上的双向边合并，同时删除合并前的被选择的分叉双向边。