Adaptive Learning of Rank-One Models for Efficient Pairwise Sequence Alignment
This work addresses a critical bottleneck in bioinformatics for researchers handling large-scale DNA sequencing data, though it appears incremental as it builds on existing hashing and spectral methods.
The authors tackled the computational burden of pairwise DNA sequence alignment by proposing a new approach that combines rank-one crowdsourcing models with adaptive multi-armed bandit algorithms, resulting in efficient estimation of alignment scores for large datasets.
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.