Col-BWT: Pangenomic Seed Chaining with Maximal Matches Improves Read Classification

Given a set of exact matches, chaining consists of finding those which are colinear with respect to the reference. However, this requires superlinear time in the number of matches and is not suitable for approaches such as read classification using a pangenome due to the increased multiplicity of matches. While compressed full-text indexes enable efficient read classification against a pangenome or tree-of-life index, past work on compressed index classification captures only fine-grained colinearity of exact matches. This fails to capture whether seeds appear colinearly in the reference, which we denote as "coarse-grained colinearity," as traditionally described by chaining. We present a novel data structure, col-BWT (for colinear Burrows-Wheeler Transform [BWT]), that additionally obtains coarse-grained colinearity ("chain") statistics. We start with a collection of strings, avoiding the multiple-alignment step required by graph approaches. We rapidly compute multi-maximal unique matches (multi-MUMs) and identify BWT sub-runs that correspond to these multi-MUMs. From these, we select those that can be "tunneled," in that they satisfy the concept of a tunnel in BWT compression, and mark them with their corresponding multi-MUM identifier. We call this approach the col-BWT due to its ability to recognize colinearity with respect to the reference. This yields an O(r + n/d)-space index for a collection of d sequences having a length-n BWT consisting of r maximal equal-character runs. Using col-BWT, we simultaneously compute both fine-grained statistics and coarse-grained chain statistics in linear time with respect to query length, faster than traditional superlinear chaining approaches. We found that this substantially improves classification accuracy compared with past compressed-indexing approaches and reaches the same level of accuracy as less efficient alignment-based methods.