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.
Govinda Kamath (Microsoft Research)
Tavor Baharav (Stanford University)
I am a second year PhD student in Electrical Engineering at Stanford University working with Professor David Tse, recently on developing fast (near linear time) randomized algorithms using techniques from multi-armed bandits. I am grateful to be supported by the NSF Graduate Research Fellowship and the Stanford Graduate Fellowship (SGF). I graduated from UC Berkeley in May 2018 where I studied Electrical Engineering and Computer Science. In my time there, I was fortunate to get the chance to work with Professor Kannan Ramchandran on coding theory and its applications to distributed computing. My current research focus is on constructing algorithms that adapt to problem instance difficulty, and more broadly in randomized algorithms, machine learning, multi-armed bandits, and their applications in engineering and computational biology problems.
Ilan Shomorony (University of Illinois at Urbana Champaign)
More from the Same Authors
2020 Poster: BanditPAM: Almost Linear Time k-Medoids Clustering via Multi-Armed Bandits »
Mo Tiwari · Martin Zhang · James J Mayclin · Sebastian Thrun · Chris Piech · Ilan Shomorony
2019 Poster: Ultra Fast Medoid Identification via Correlated Sequential Halving »
Tavor Baharav · David Tse