Beam search decoder for enhancing sequence decoding speed in single-molecule peptide sequencing data

Abstract

Next-generation single-molecule protein sequencing technologies have the potential to accelerate biomedical research significantly. These technologies offer sensitivity and scalability for proteomic analysis. One auspicious method is fluorosequencing, which involves: cutting naturalized proteins into peptides, attaching fluorophores to specific amino acids, and observing variations in light intensity as one amino acid is removed at a time. The original peptide is classified from the sequence of light-intensity reads, and proteins can subsequently be recognized with this information. The amino acid step removal is achieved by attaching the peptides to a wall on the C-terminal and using a process called Edman Degradation to remove an amino acid from the N-Terminal. Even though a framework (Whatprot) has been proposed for the peptide classification task, processing times remain restrictive due to the massively parallel data acquisicion system. In this paper, we propose a new beam search decoder with a novel state formulation that obtains much lower processing times with slightly higher accuracies than Whatprot. Furthermore, we explore how our novel state formulation may lead to even faster decoders in the future. Author summaryProteomic analyses are often carried on with mass spectrometry, but this method cannot identify low-abundance proteins. Single-molecule protein sequencing methods can overcome this issue, and fluorosequencing is one of these technologies. Fluorosequencing has attracted interest from investors, as evidenced by the recent funding of Erisyon, a company developing this technology. This technique contains a challenging classification task: determining the original peptide sequence from light-intensity observations obtained after several Edman cycles. A classifier based on a combination of k Nearest Neighbors (kNN) with Hidden Markov Models (HMM) had been shown to have close-to-optimal accuracy with tractable complexity. We propose in this paper a new algorithm that not only improves accuracy compared to state-of-the-art methods but also reduces computation time.