A two-party fuzzy private set intersection (PSI) protocol between Alice and Bob with input sets A and B allows Alice to learn nothing more than the points of Bob that are ''δ-close'' to its points in some metric space dist . More formally, Alice learns only the set {b | dist (a,b) ≤ δ, a ∈ A, b ∈ B} for a predefined threshold δ and distance metric dist, while Bob learns nothing about Alice's set. Fuzzy PSI is a valuable privacy tool in scenarios where private set intersection needs to be computed over imprecise or measurement-based data, such as GPS coordinates or healthcare data. Previous approaches to fuzzy PSI rely on asymmetric cryptographic primitives, generic two-party computation (2PC) techniques like garbled circuits, or function secret sharing methods, all of which are computationally intensive and lead to poor concrete efficiency. This work introduces a new modular framework for fuzzy PSI, primarily built on efficient symmetric key primitives. Our framework reduces the design of efficient fuzzy PSI to a novel variant of oblivious transfer (OT), which we term distance-aware random OT (da-ROT). This variant enables the sender to obtain two random strings (r0, r1), while the receiver obtains one of these values rb, depending on whether the receiver's input keyword a and the sender's input keyword b are close in some metric space i.e., dist (a,b) ≤ δ. The da-ROT can be viewed as a natural extension of traditional OT, where the condition (choice bit) is known to the receiver. We propose efficient constructions for da-ROT based on standard OT techniques tailored for small domains, supporting distance metrics such as the Chebyshev norm, the Euclidean norm, and the Manhattan norm. By integrating these da-ROT constructions, our fuzzy PSI framework achieves up to a 14× reduction in communication cost and up to a 54× reduction in computation cost compared to previous state-of-the-art protocols, across input set sizes ranging from 28 to 216. Additionally, we extend our framework to compute fuzzy PSI cardinality and fuzzy join from traditional PSI-related functionalities. All proposed protocols are secure in the semi-honest model.

Multiple sequence alignment (MSA) is one of the best studied problems in bioinformatics because of the broad set of genomics, proteomics, and evolutionary analyses that rely on it. Yet the problem is NP-hard and existing heuristics are imperfect. Reinforcement learning (RL) techniques have emerged recently as a potential solution to a wide diversity of computational problems, but have yet to be applied to MSA. In this paper, we describe RLALIGN, a method to solve the MSA problem using RL. RLALIGN is based on Asynchronous Advantage Actor Critic (A3C), a cutting-edge RL framework. Due to the absence of a goal state, however, it required several important modifications. RLALIGN can be trained to accurately align moderate-length sequences, and various heuristics allow it to scale to longer sequences. The accuracy of the alignments produced is on par with, and often better than those of well established alignment algorithms. Overall, our work demonstrates the potential of RL approaches for complex combinatorial problems such as MSA. RLALIGN will prove useful for realignment tasks, where portions of a larger alignment need to be optimized. Unlike classical algorithms, RLALIGN is incognizant to the nature of the scoring scheme, leading to easy generalization to a variety of problem variants.

Whole-genome multiple alignments are widely used in genomics and evolution, and yet their accuracy is imperfect, due in part to the computational complexity of the task at hand. Identifying portions of these alignments that are likely to be incorrect would allow researchers to either work on improving them or flagging them for exclusion from downstream analyses. We introduce MSA-ED, a machine learning tool for the detection of errors in whole-genome multiple alignments. MSA-ED uses random forests or artificial neural networks to identify and classify several types of alignment errors. It is trained on labeled data obtained by using an evolution simulator to generate fake orthologous sequences and their correct alignment, and comparing it to the alignment produced by Multiz, a popular whole-genome aligner. Key to the success of MSA-ED is the engineering of several types of evolutionarily-inspired features that boost prediction accuracy. MSA-ED is shown to be able to detect certain types of errors with good accuracy. It is then applied to actual genomic alignments to identify putative alignment errors. Availability: https://github.com/jaspal1329/MSA-ED