Alignment of Single-Molecule Sequencing Reads by Enhancing the Accuracy and Efficiency of Locality-Sensitive Hashing

Aligning single-molecule sequencing (SMS) reads to a reference genome has been computationally challenging due to the high sequencing error rates in this technology. Short distances between consecutive errors in SMS reads confront finding seeds, subsequences of the reads with exact matches to the reference, that specifically target a unique genomic position. To overcome this issue, one can look for similarities, rather than exact matches. MinHash, a locality-sensitive hashing (LSH) scheme, measures the similarity of two sequences by listing all k-mers of each one and approximating the fraction of common k-mers between them using a family of hash functions, which usually includes hundreds to thousands of different hash functions in order to increase the measurement accuracy. MinHash is used to address various bioinformatics problems, including the assembly of SMS reads. Here, we enhance both the efficiency and accuracy of the MinHash scheme by algorithmic techniques. We use a single hash function, rather than hundreds or thousands of different hash functions as used in the other MinHash-based algorithms, without losing the accuracy. We also double the size of the seed sequences by allowing one sequencing error of any form inside a pair of k-mers, which has a significant impact on the accuracy. We show algorithm, called Aryana-LoR, outperforms the accuracy of the other existing SMS aligners in both E-coli and Human genomes. AvailabilityAryana-LoR is freely available at https://gitlab.com/hnikaein/aryana-LoR