Hamming-shifting graph of genomic short reads: Efficient construction and its application for compression.

ABSTRACT: Graphs such as de Bruijn graphs and OLC (overlap-layout-consensus) graphs have been widely adopted for the de novo assembly of genomic short reads. This work studies another important problem in the field: how graphs can be used for high-performance compression of the large-scale sequencing data. We present a novel graph definition named Hamming-Shifting graph to address this problem. The definition originates from the technological characteristics of next-generation sequencing machines, aiming to link all pairs of distinct reads that have a small Hamming distance or a small shifting offset or both. We compute multiple lexicographically minimal k-mers to index the reads for an efficient search of the weight-lightest edges, and we prove a very high probability of successfully detecting thes

SUBMITTER: Liu Y 

PROVIDER: S-EPMC8321399 | biostudies-literature | 2021 Jul

REPOSITORIES: biostudies-literature