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