双向多步De Bruijn图的重复双向边识别与去除方法

摘要

本发明公开一种双向多步De Bruijn图的重复双向边识别与去除方法，包括步骤，S1、读取测序数据源文件，并构造双向多步De Bruijn图；S2、判断出度为3的顶点u是否指向的同一个顶点v的同一方向或者同一端，指向相同的一端为耦合重复双向边，指向不同的一端为错误重复双向边；S3、对被判定含有耦合重复双向边顶点u和被判定含有错误重复双向边顶点u进行判断删除。本发明根据重复双向边形成，将部分重复双向边分类，并采取正确的措施清除De Bruijn图中存在的重复双向边；使contigs可以继续延长，De Bruijn图继续收缩；有效的解耦并去除重复双向边，而且避免对正确的双向边的破坏，从而可以一定程度上提高contigs的长度，提高contig的质量。