MOTIVATION: Integrated analysis across biological databases is becoming increasingly important in life science research, leading many public databases to adopt Semantic Web technologies, also known as knowledge graphs. However, biological data possesses inherently complex and diverse structures, which makes the resulting Resource Description Framework (RDF) schemas intricate and difficult for non-expert users to master, preventing them from translating natural language questions into correct SPARQL queries. Although recent large language model (LLM)-based approaches show potential for automatic SPARQL query generation, they often suffer from structural hallucinations and require large-scale training data to capture schema-specific structures. In this study, we propose a novel framework that avoids hallucinations and requires no training data by combining LLM-based word extraction with a schema-based SPARQL query builder. RESULTS: The LLM extracts variables and parameters from the user's question based on a predefined schema, and the query builder generates a syntactically correct SPARQL query accordingly. By providing a predefined schema in prompts, our method eliminates the need for training data. Experimental results on UniProt, Rhea, and Bgee demonstrate that our method outperforms baseline LLM-based methods using fine-tuning and prompt-tuning in terms of the similarity between search results obtained from generated and expert-written queries. Furthermore, we developed a proof-of-concept chatbot system that enables users to query RDF databases via natural language input, demonstrating the practical utility of our approach in improving access to biological data resources. AVAILABILITY AND IMPLEMENTATION: Experimental environment: https://github.com/scott2121/sparql_query_generator (DOI: https://doi.org/10.5281/zenodo.18539213). Chatbot: https://github.com/scott2121/sparql_query_chatbot (DOI: https://doi.org/10.5281/zenodo.18539225).

Many privacy-preserving data analysis tasks based on multi-party computation require oblivious retrieval of data elements for downstream use. As database sizes grow, this retrieval step becomes a dominant bottleneck, highlighting the need for more efficient oblivious access (OA) primitives that retrieve a database entry without revealing the accessed position. A common approach uses distributed point functions (DPFs), which reduce communication but still incur local computation that scales linearly with the database size. Early termination (ET) optimization reduces local computation, but applying it yields only Boolean shares that require costly conversion for arithmetic use. This incompatibility between ET and arithmetic outputs makes it difficult for OA to scale efficiently on large databases. We introduce RingOA, the first three-party OA protocol that supports ET while directly producing arithmetic shares. Our method eliminates the need for share conversion and preserves the computational benefits of ET. RingOA achieves a 13.1x to 15.7x improvement in runtime on databases exceeding one billion entries compared to a state-of-the-art OA protocol. Building on RingOA, we construct an oblivious rank query, a core primitive underlying many structured-data analyses. We develop two practical applications: a fully oblivious full-text search protocol for pattern matching over secret-shared string datasets, and a fully oblivious range-search protocol supporting statistical queries over secret-shared numerical sequences. Experiments on real large-scale genomic datasets show that these applications achieve practical performance, demonstrating the utility of our OA protocol and its applications.

Finding a similar substring that commonly appears in query and database sequences is an essential task for genome data analysis. This study proposes a secure two-party variable-length string search protocol based on secret sharing. The unique feature of our protocol is that time, communication, and round complexities are not dependent on the database length N, after the query input. This property brings dramatic performance improvements in search time, since N is usually quite large in an actual genome database, and the same database is repeatedly used for many queries. Our concept hinges on a technique that efficiently applies the compressed full-text index (FOCS 2000) for a secret-sharing scheme. We conducted an experiment using a human genomic sequence with the length of 10 million as the database and a query with the length of 100 and found that the query response time of our protocol was at least three orders of magnitude faster than a well-designed baseline protocol under the realistic computation/network environment.

In this paper, we propose a playful tool to predict protein-protein docking. The tool uses human bodies to explore better protein-protein docking, where it offers natural interactions to dock protein molecules in a flexible way and playful interactions through two users' cooperative body movements. We present the design and implementation of the proposed tool and show potential opportunities and pitfalls of the current tool.

Biomedical data often includes personal information, and the technology is demanded that enables the searching of such sensitive data while protecting privacy. We consider a case in which a server has a text database and a user searches the database to find substring matches. The user wants to conceal his/her query and the server wants to conceal the database except for the search results. The previous approach for this problem is based on a linear-time algorithm in terms of alphabet size $\mathbf{|\Sigma |}$|Σ|, and it cannot search on the database of large alphabet such as biomedical documents. We present a novel algorithm that can search a string in logarithmic time of $\mathbf{|\Sigma |}$|Σ|. In our algorithm, named secure wavelet matrix (sWM), we use an additively homomorphic encryption to build an efficient data structure called a wavelet matrix. In an experiment using a simulated string of length 10,000 whose alphabet size ranges from 4 to 1024, the run time of the sWM was up to around two orders of magnitude faster than that of the previous method. sWM enables the searching of a private database efficiently and thus it will facilitate utilizing sensitive biomedical information.

We construct an efficient two-level homomorphic public-key encryption in prime-order bilinear groups. Such a scheme supports polynomially many homomorphic additions and one multiplication over encrypted data, similar to the cryptosystem of Boneh, Goh, and Nissim (BGN, presented at TCC 2005), which was constructed in composite-order bilinear groups. Prior to our work, the state-of-the-art for two-level homomorphic public-key encryption is the Freeman scheme (presented at Eurocrypt 2010), which is indeed the prime-order realization of the BGN scheme. Our proposed scheme significantly improves efficiency for almost all the aspects of the Freeman scheme, while retains the same ciphertext sizes. Our scheme is surprisingly simple as it is indeed (a concatenation of two copies of) the ElGamal encryption "in the exponent'' resided in an asymmetric bilinear groups.

We present a new secure integer division protocol with private divisor. Our protocol is based loosely on the Bogdanov et al. (Int. J. Inf. Secur.'12) protocol, which securely computes the classical Goldschmidt's division algorithm. While the Bogdanov et al. scheme was designed specifically to work only on a 3-out-of-3 secret sharing scheme, our scheme works on a 2-out-of-2 secret sharing scheme. This has an advantage since the latter setting is more widely used in the literature of secure computation, and our protocol can thus be used as an efficient building block in this setting. We implement our protocol in Python and provide its benchmark. As a main application of our division protocol, we implement a secure protocol for privacy-preserving chi-squared tests on genomic data. This demonstrates that the proposed protocol is suitable for the statistical analysis on sensitive data.

Many applications of machine learning, for example in health care, would benefit from methods that can guarantee privacy of data subjects. Differential privacy (DP) has become established as a standard for protecting learning results. The standard DP algorithms require a single trusted party to have access to the entire data, which is a clear weakness, or add prohibitive amounts of noise. We consider DP Bayesian learning in a distributed setting, where each party only holds a single sample or a few samples of the data. We propose a learning strategy based on a secure multi-party sum function for aggregating summaries from data holders and the Gaussian mechanism for DP. Our method builds on an asymptotically optimal and practically efficient DP Bayesian inference with rapidly diminishing extra cost.

Privacy-preserving string search is a crucial task for analyzing genomics-driven big data. In this work, we propose a cryptographic protocol that uses Fully Homomorphic Encryption (FHE) to enable a client to search on a genome sequence database without leaking his/her query to the server. Though FHE supports both addition and multiplication over encrypted data, random noise inside ciphertexts grows with every arithmetic operation especially multiplication, which results in incorrect decryption when the noise amount exceeds its threshold called level. There are two approaches to avoid the incorrect decryption: one is setting the sufficient level that assures correct decryption within the limited number of operations, and the other is resetting the noise by the method called bootstrapping. It is important to find an optimal balance between overhead caused by the level and overhead caused by the bootstrapping, since using higher level deteriorates the performance of all the arithmetic operations, while the more number of bootstrappings causes more expensive overhead. In this study, we propose an efficient approach to minimize the number of bootstrappings while reducing the level as much as possible. Our experimental result shows that it runs at most 10 times faster than a naïve approach.

MOTIVATION: Personal genomes carry inherent privacy risks and protecting privacy poses major social and technological challenges. We consider the case where a user searches for genetic information (e.g. an allele) on a server that stores a large genomic database and aims to receive allele-associated information. The user would like to keep the query and result private and the server the database. APPROACH: We propose a novel approach that combines efficient string data structures such as the Burrows-Wheeler transform with cryptographic techniques based on additive homomorphic encryption. We assume that the sequence data is searchable in efficient iterative query operations over a large indexed dictionary, for instance, from large genome collections and employing the (positional) Burrows-Wheeler transform. We use a technique called oblivious transfer that is based on additive homomorphic encryption to conceal the sequence query and the genomic region of interest in positional queries. RESULTS: We designed and implemented an efficient algorithm for searching sequences of SNPs in large genome databases. During search, the user can only identify the longest match while the server does not learn which sequence of SNPs the user queried. In an experiment based on 2184 aligned haploid genomes from the 1000 Genomes Project, our algorithm was able to perform typical queries within [Formula: see text] 4.6 s and [Formula: see text] 10.8 s for client and server side, respectively, on laptop computers. The presented algorithm is at least one order of magnitude faster than an exhaustive baseline algorithm. AVAILABILITY AND IMPLEMENTATION: https://github.com/iskana/PBWT-sec and https://github.com/ratschlab/PBWT-sec CONTACTS: [email protected] or [email protected] SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

BACKGROUND: Searching for similar compounds in a database is the most important process for in-silico drug screening. Since a query compound is an important starting point for the new drug, a query holder, who is afraid of the query being monitored by the database server, usually downloads all the records in the database and uses them in a closed network. However, a serious dilemma arises when the database holder also wants to output no information except for the search results, and such a dilemma prevents the use of many important data resources. RESULTS: In order to overcome this dilemma, we developed a novel cryptographic protocol that enables database searching while keeping both the query holder's privacy and database holder's privacy. Generally, the application of cryptographic techniques to practical problems is difficult because versatile techniques are computationally expensive while computationally inexpensive techniques can perform only trivial computation tasks. In this study, our protocol is successfully built only from an additive-homomorphic cryptosystem, which allows only addition performed on encrypted values but is computationally efficient compared with versatile techniques such as general purpose multi-party computation. In an experiment searching ChEMBL, which consists of more than 1,200,000 compounds, the proposed method was 36,900 times faster in CPU time and 12,000 times as efficient in communication size compared with general purpose multi-party computation. CONCLUSION: We proposed a novel privacy-preserving protocol for searching chemical compound databases. The proposed method, easily scaling for large-scale databases, may help to accelerate drug discovery research by making full use of unused but valuable data that includes sensitive information.

MOTIVATION: Chromosome rearrangement events are triggered by atypical breaking and rejoining of DNA molecules, which are observed in many cancer-related diseases. The detection of rearrangement is typically done by using short reads generated by next-generation sequencing (NGS) and combining the reads with knowledge of a reference genome. Because structural variations and genomes differ from one person to another, intermediate comparison via a reference genome may lead to loss of information. RESULTS: In this article, we propose a reference-free method for detecting clusters of breakpoints from the chromosomal rearrangements. This is done by directly comparing a set of NGS normal reads with another set that may be rearranged. Our method SlideSort-BPR (breakpoint reads) is based on a fast algorithm for all-against-all comparisons of short reads and theoretical analyses of the number of neighboring reads. When applied to a dataset with a sequencing depth of 100×, it finds ∼ 88% of the breakpoints correctly with no false-positive reads. Moreover, evaluation on a real prostate cancer dataset shows that the proposed method predicts more fusion transcripts correctly than previous approaches, and yet produces fewer false-positive reads. To our knowledge, this is the first method to detect breakpoint reads without using a reference genome. AVAILABILITY AND IMPLEMENTATION: The source code of SlideSort-BPR can be freely downloaded from https://code.google.com/p/slidesort-bpr/.

MOTIVATION: Recent progress in DNA sequencing technologies calls for fast and accurate algorithms that can evaluate sequence similarity for a huge amount of short reads. Searching similar pairs from a string pool is a fundamental process of de novo genome assembly, genome-wide alignment and other important analyses. RESULTS: In this study, we designed and implemented an exact algorithm SlideSort that finds all similar pairs from a string pool in terms of edit distance. Using an efficient pattern growth algorithm, SlideSort discovers chains of common k-mers to narrow down the search. Compared to existing methods based on single k-mers, our method is more effective in reducing the number of edit distance calculations. In comparison to backtracking methods such as BWA, our method is much faster in finding remote matches, scaling easily to tens of millions of sequences. Our software has an additional function of single link clustering, which is useful in summarizing short reads for further processing. AVAILABILITY: Executable binary files and C++ libraries are available at http://www.cbrc.jp/~shimizu/slidesort/ for Linux and Windows.

MOTIVATION: Recent experimental and theoretical studies have revealed several proteins containing sequence segments that are unfolded under physiological conditions. These segments are called disordered regions. They are actively investigated because of their possible involvement in various biological processes, such as cell signaling, transcriptional and translational regulation. Additionally, disordered regions can represent a major obstacle to high-throughput proteome analysis and often need to be removed from experimental targets. The accurate prediction of long disordered regions is thus expected to provide annotations that are useful for a wide range of applications. RESULTS: We developed Prediction Of Order and Disorder by machine LEarning (POODLE-L; L stands for long), the Support Vector Machines (SVMs) based method for predicting long disordered regions using 10 kinds of simple physico-chemical properties of amino acid. POODLE-L assembles the output of 10 two-level SVM predictors into a final prediction of disordered regions. The performance of POODLE-L for predicting long disordered regions, which exhibited a Matthew's correlation coefficient of 0.658, was the highest when compared with eight well-established publicly available disordered region predictors. AVAILABILITY: POODLE-L is freely available at http://mbs.cbrc.jp/poodle/poodle-l.html. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

UNLABELLED: Protein disorder is characterized by a lack of a stable 3D structure, and is considered to be involved in a number of important protein functions such as regulatory and signalling events. We developed a web application, the POODLE-S, which predicts the disordered region from amino acid sequences by using physicochemical features and reduced amino acid set of a position-specific scoring matrix. AVAILABILITY: POODLE-S is available from http://mbs.cbrc.jp/poodle/poodle-s.html and can be used by both academic and commercial users.

BACKGROUND: Predicting intrinsically disordered proteins is important in structural biology because they are thought to carry out various cellular functions even though they have no stable three-dimensional structure. We know the structures of far more ordered proteins than disordered proteins. The structural distribution of proteins in nature can therefore be inferred to differ from that of proteins whose structures have been determined experimentally. We know many more protein sequences than we do protein structures, and many of the known sequences can be expected to be those of disordered proteins. Thus it would be efficient to use the information of structure-unknown proteins in order to avoid training data sparseness. We propose a novel method for predicting which proteins are mostly disordered by using spectral graph transducer and training with a huge amount of structure-unknown sequences as well as structure-known sequences. RESULTS: When the proposed method was evaluated on data that included 82 disordered proteins and 526 ordered proteins, its sensitivity was 0.723 and its specificity was 0.977. It resulted in a Matthews correlation coefficient 0.202 points higher than that obtained using FoldIndex, 0.221 points higher than that obtained using the method based on plotting hydrophobicity against the number of contacts and 0.07 points higher than that obtained using support vector machines (SVMs). To examine robustness against training data sparseness, we investigated the correlation between two results obtained when the method was trained on different datasets and tested on the same dataset. The correlation coefficient for the proposed method is 0.14 higher than that for the method using SVMs. When the proposed SGT-based method was compared with four per-residue predictors (VL3, GlobPlot, DISOPRED2 and IUPred (long)), its sensitivity was 0.834 for disordered proteins, which is 0.052-0.523 higher than that of the per-residue predictors, and its specificity was 0.991 for ordered proteins, which is 0.036-0.153 higher than that of the per-residue predictors. The proposed method was also evaluated on data that included 417 partially disordered proteins. It predicted the frequency of disordered proteins to be 1.95% for the proteins with 5%-10% disordered sequences, 1.46% for the proteins with 10%-20% disordered sequences and 16.57% for proteins with 20%-40% disordered sequences. CONCLUSION: The proposed method, which utilizes the information of structure-unknown data, predicts disordered proteins more accurately than other methods and is less affected by training data sparseness.