Journal Article

S-conLSH: alignment-free gapped mapping of noisy long reads

Chakraborty, Angana, Bandyopadhyay, Sanghamitra, Morgenstern, Burkhard

2021

Overview

Background The advancement of SMRT technology has unfolded new opportunities of genome analysis with its longer read length and low GC bias. Alignment of the reads to their appropriate positions in the respective reference genome is the first but costliest step of any analysis pipeline based on SMRT sequencing. However, the state-of-the-art aligners often fail to identify distant homologies due to lack of conserved regions, caused by frequent genetic duplication and recombination. Therefore, we developed a novel alignment-free method of sequence mapping that is fast and accurate. Results We present a new mapper called S-conLSH that uses S paced con text based L ocality S ensitive H ashing. With multiple spaced patterns, S-conLSH facilitates a gapped mapping of noisy long reads to the corresponding target locations of a reference genome. We have examined the performance of the proposed method on 5 different real and simulated datasets. S-conLSH is at least 2 times faster than the recently developed method lordFAST. It achieves a sensitivity of 99%, without using any traditional base-to-base alignment, on human simulated sequence data. By default, S-conLSH provides an alignment-free mapping in PAF format. However, it has an option of generating aligned output as SAM-file, if it is required for any downstream processing. Conclusions S-conLSH is one of the first alignment-free reference genome mapping tools achieving a high level of sensitivity. The spaced -context is especially suitable for extracting distant similarities. The variable-length spaced-seeds or patterns add flexibility to the proposed algorithm by introducing gapped mapping of the noisy long reads. Therefore, S-conLSH may be considered as a prominent direction towards alignment-free sequence analysis.

• Publisher: BioMed Central,BioMed Central Ltd,Springer Nature B.V,BMC
• Subject: Algorithms / Alignment / Alignment-free sequence comparison / Background noise / Bioinformatics / Biomedical and Life Sciences / Computational Biology/Bioinformatics / Computer Appl. in Life Sciences / Context / Cost analysis / Datasets / Deoxyribonucleic acid / DNA / DNA methylation / DNA sequencing / Experiments / Gene mapping / Genomes / Genomics / Hashing (Computers) / High-Throughput Nucleotide Sequencing / Homology / Humans / Life Sciences / Locality sensitive hashing / Mapping / Methodology / Methodology Article / Methods / Microarrays / Noisy long SMRT reads / Novel computational methods for the analysis of biological systems / Nucleotide sequencing / Optimization techniques / Recombination / Seeds / Sensitivity / Sequence Alignment / Sequence analysis / Sequence Analysis, DNA / Software