More Like this

1. Designing microplastic-binding peptides with a variational quantum circuit–based hybrid quantum-classical approach

   https://doi.org/10.1126/sciadv.adq8492  

   Vendrell, Raul Conchello; Ajagekar, Akshay; Bergman, Michael T; Hall, Carol K; You, Fengqi (December 2024, Science Advances)

   De novo peptide design exhibits great potential in materials engineering, particularly for the use of plastic-binding peptides to help remediate microplastic pollution. There are no known peptide binders for many plastics—a gap that can be filled with de novo design. Current computational methods for peptide design exhibit limitations in sampling and scaling that could be addressed with quantum computing. Hybrid quantum-classical methods can leverage complementary strengths of near-term quantum algorithms and classical techniques for complex tasks like peptide design. This work introduces a hybrid quantum-classical generative framework for designing plastic-binding peptides combining variational quantum circuits with a variational autoencoder network. We demonstrate the framework’s effectiveness in generating peptide candidates, evaluate its efficiency for property-oriented design, and validate the candidates with molecular dynamics simulations. This quantum computing–based approach could accelerate the development of biomolecular tools for environmental and biomedical applications while advancing the study of biomolecular systems through quantum technologies. 

   more » « less
2. Robust Algorithms for TSP and Steiner Tree

   https://doi.org/10.4230/LIPIcs.WABI.2020.17  

   Ganesh, Arun; Maggs, Bruce; Panigrahi, Debmalya (January 2020, Leibniz international proceedings in informatics)

   Czumaj, Arturr; Dawar, Anuj; Merelli, Emanuela (Ed.)

   Robust optimization is a widely studied area in operations research, where the algorithm takes as input a range of values and outputs a single solution that performs well for the entire range. Specifically, a robust algorithm aims to minimize regret, defined as the maximum difference between the solution’s cost and that of an optimal solution in hindsight once the input has been realized. For graph problems in P, such as shortest path and minimum spanning tree, robust polynomial-time algorithms that obtain a constant approximation on regret are known. In this paper, we study robust algorithms for minimizing regret in NP-hard graph optimization problems, and give constant approximations on regret for the classical traveling salesman and Steiner tree problems. 

   more » « less
3. Robust Algorithms for TSP and Steiner Tree

   https://doi.org/10.1145/3570957  

   Ganesh, Arun; Maggs, Bruce M; Panigrahi, Debmalya (April 2023, ACM Transactions on Algorithms)

   Robust optimization is a widely studied area in operations research, where the algorithm takes as input a range of values and outputs a single solution that performs well for the entire range. Specifically, a robust algorithm aims to minimizeregret, defined as the maximum difference between the solution’s cost and that of an optimal solution in hindsight once the input has been realized. For graph problems inP, such as shortest path and minimum spanning tree, robust polynomial-time algorithms that obtain a constant approximation on regret are known. In this paper, we study robust algorithms for minimizing regret inNP-hard graph optimization problems, and give constant approximations on regret for the classical traveling salesman and Steiner tree problems. 

   more » « less
4. On de novo Bridging Paired-end RNA-seq Data

   https://doi.org/10.1145/3584371.3612987  

   Li, Xiang; Shao, Mingfu (September 2023, Proceedings of the 14th ACM International Conference on Bioinformatics, Computational Biology, and Health Informatics)

   The high-throughput short-reads RNA-seq protocols often produce paired-end reads, with the middle portion of the fragments being unsequenced. We explore if the full-length fragments can be com- putationally reconstructed from the sequenced two ends in the absence of the reference genome—a problem here we refer to as de novo bridging. Solving this problem provides longer, more infor- mative RNA-seq reads, and benefits downstream RNA-seq analysis such as transcript assembly, expression quantification, and splic- ing differential analysis. However, de novo bridging is a challeng- ing and complicated task owing to alternative splicing, transcript noises, and sequencing errors. It remains unclear if the data pro- vides sufficient information for accurate bridging, let alone efficient algorithms that determine the true bridges. Methods have been proposed to bridge paired-end reads in the presence of reference genome (called reference-based bridging), but the algorithms are far away from scaling for de novo bridging as the underlying com- pacted de Bruijn graph (cdBG) used in the latter task often contains millions of vertices and edges. We designed a new truncated Dijk- stra’s algorithm for this problem, and proposed a novel algorithm that reuses the shortest path tree to avoid running the truncated Di- jkstra’s algorithm from scratch for all vertices for further speeding up. These innovative techniques result in scalable algorithms that can bridge all paired-end reads in a cdBG with millions of vertices. Our experiments showed that paired-end RNA-seq reads can be accurately bridged to a large extent. The resulting tool is freely available at https://github.com/Shao-Group/rnabridge-denovo. 

   more » « less
5. Accurate de novo peptide sequencing using fully convolutional neural networks

   https://doi.org/10.1038/s41467-023-43010-x  

   Liu, Kaiyuan; Ye, Yuzhen; Li, Sujun; Tang, Haixu (December 2023, Nature Communications)

   Abstract De novo peptide sequencing, which does not rely on a comprehensive target sequence database, provides us with a way to identify novel peptides from tandem mass spectra. However, current de novo sequencing algorithms suffer from low accuracy and coverage, which hinders their application in proteomics. In this paper, we presentPepNet, a fully convolutional neural network for high accuracy de novo peptide sequencing. PepNet takes an MS/MS spectrum (represented as a high-dimensional vector) as input, and outputs the optimal peptide sequence along with its confidence score. The PepNet model is trained using a total of 3 million high-energy collisional dissociation MS/MS spectra from multiple human peptide spectral libraries. Evaluation results show that PepNet significantly outperforms current best-performing de novo sequencing algorithms (e.g. PointNovo and DeepNovo) in both peptide-level accuracy and positional-level accuracy. PepNet can sequence a large fraction of spectra that were not identified by database search engines, and thus could be used as a complementary tool to database search engines for peptide identification in proteomics. In addition, PepNet runs around 3x and 7x faster than PointNovo and DeepNovo on GPUs, respectively, thus being more suitable for the analysis of large-scale proteomics data. 

   more » « less