Adaptive Learning of Rank-One Models for Efficient Pairwise Sequence Alignment

arXiv2011.04832MaRDI QIDQ6353375

Author name not available (Why is that?)

Publication date: 9 November 2020

Abstract: Pairwise alignment of DNA sequencing data is a ubiquitous task in bioinformatics and typically represents a heavy computational burden. State-of-the-art approaches to speed up this task use hashing to identify short segments (k-mers) that are shared by pairs of reads, which can then be used to estimate alignment scores. However, when the number of reads is large, accurately estimating alignment scores for all pairs is still very costly. Moreover, in practice, one is only interested in identifying pairs of reads with large alignment scores. In this work, we propose a new approach to pairwise alignment estimation based on two key new ingredients. The first ingredient is to cast the problem of pairwise alignment estimation under a general framework of rank-one crowdsourcing models, where the workers' responses correspond to k-mer hash collisions. These models can be accurately solved via a spectral decomposition of the response matrix. The second ingredient is to utilise a multi-armed bandit algorithm to adaptively refine this spectral estimator only for read pairs that are likely to have large alignments. The resulting algorithm iteratively performs a spectral decomposition of the response matrix for adaptively chosen subsets of the read pairs.

Has companion code repository: https://github.com/TavorB/adaptiveSpectral

This page was built for publication: Adaptive Learning of Rank-One Models for Efficient Pairwise Sequence Alignment

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6353375)