We present a method for privately publishing sparse vectors with communication and computation costs that scale linearly with the number of nonzero elements. The Poisson Private Representation (PPR) framework was introduced to compress any differentially private mechanism to achieve a communication cost of O(ϵ), where ϵ is the privacy budget. However, PPR and its variant, Chunk PPR, are not well suited for publishing sparse vectors under metric differential privacy: PPR incurs exponential computation cost, while Chunk PPR requires both execution and communication costs linear in the vector dimension. As a result, their guarantees are no stronger than those of non-compressed randomized response, which for a matrix with N users, n columns, and m nonzero elements, requires Ω(nN) communication—rendering it impractical for large-scale data.

The Shortest Common Superstring (SCS) problem asks for the shortest string that contains each of a given set of strings as a substring. Its reverse-complement variant, the Shortest Common Superstring problem with Reverse Complements (SCS-RC), naturally arises in bioinformatics applications, where for each input string, either the string itself or its reverse complement must appear as a substring of the superstring. The well-known MGREEDY algorithm for the standard SCS constructs a superstring by first computing an optimal cycle cover on the overlap graph and then concatenating the strings corresponding to the cycles, while its refined variant, TGREEDY, further improves the approximation ratio. Although the original 4- and 3-approximation bounds of these algorithms have been successively improved for the standard SCS, no such progress has been made for the reverse-complement setting. A previous study extended MGREEDY to SCS-RC with a 4-approximation guarantee and briefly suggested that extending TGREEDY to the reverse-complement setting could achieve a 3-approximation. In this work, we strengthen these results by proving that the extensions of MGREEDY and TGREEDY to the reverse-complement setting achieve 3.75- and 2.875-approximation ratios, respectively. Our analysis extends the classical proofs for the standard SCS to handle the bidirectional overlaps introduced by reverse complements. These results provide the first formal improvement of approximation guarantees for SCS-RC, with the 2.875-approximate algorithm currently representing the best known bound for this problem.

Identifying shared substructures in 3D protein models is essential for structural bioinformatics. This task can be modeled as a sequential Largest Common Point-set (LCP) problem under the bottleneck distance. We propose a new O(n^13 log n)-time exact algorithm for this problem, which improves upon the previous best-known complexity of O(n^14), where n is the maximum size of the two input structures. Since these theoretical bounds are practically too large, an O(n⁷ log n)-time approximation algorithm with solution-size guarantees has been proposed; however, it remains too time-consuming for practical applications. Thus, we also propose a new filtering technique to enhance the approximation algorithm without increasing the theoretical time complexity or losing the solution-size guarantees. Experiments with PDB data show that our technique achieves over a 24-fold speedup at n = 130. While the previous algorithm required 3.80 hours on average for n = 130 in our experiments, making it difficult to test larger structures, our algorithm can process n = 200 in only 2.33 hours on average.

The Shortest Common Superstring (SCS) problem is a fundamental task in sequence analysis. In genome assembly, however, the double-stranded nature of DNA implies that each fragment may occur either in its original orientation or as its reverse complement. This motivates the Shortest Common Superstring with Reverse Complements (SCS-RC) problem, which asks for a shortest string that contains, for each input string, either the string itself or its reverse complement as a substring. The previously best-known approximation ratio for SCS-RC was 23/8. In this paper, we present a new approximation algorithm achieving an improved ratio of 8/3. Our approach computes an optimal constrained cycle cover by reducing the problem, via a novel gadget construction, to a maximum-weight perfect matching in a general graph. We also investigate the computational hardness of SCS-RC. While the decision version is known to be NP-complete, no explicit inapproximability results were previously established. We show that the hardness of SCS carries over to SCS-RC through a polynomial-time reduction, implying that it is NP-hard to approximate SCS-RC within a factor better than 333/332. Notably, this hardness result holds even for the DNA alphabet.

With the growing volume of data in society, the need for privacy protection in data analysis also rises. In particular, private selection tasks, wherein the most important information is retrieved under differential privacy are emphasized in a wide range of contexts, including machine learning and medical statistical analysis. However, existing mechanisms use global sensitivity, which may add larger amount of perturbation than is necessary. Therefore, this study proposes a novel mechanism for differentially private selection using the concept of smooth sensitivity and presents theoretical proofs of strict privacy guarantees. Simultaneously, given that the current state-of-the-art algorithm using smooth sensitivity is still of limited use, and that the theoretical analysis of the basic properties of the noise distributions are not yet rigorous, we present fundamental theorems to improve upon them. Furthermore, new theorems are proposed for efficient noise generation. Experiments demonstrate that the proposed mechanism can provide higher accuracy than the existing global sensitivity-based methods. Finally, we show key directions for further theoretical development. Overall, this study can be an important foundational work for expanding the potential of smooth sensitivity in privacy-preserving data analysis. The Python implementation of our experiments and supplemental results are available at https://github.com/ay0408/Smooth-Private-Selection.

With the increasing amount of data in society, privacy concerns in data sharing have become widely recognized. Particularly, protecting personal attribute information is essential for a wide range of aims from crowdsourcing to realizing personalized medicine. Although various differentially private methods based on randomized response have been proposed for single attribute information or specific analysis purposes such as frequency estimation, there is a lack of studies on the mechanism for sharing individuals’ multiple categorical information itself. The existing randomized response for sharing multi-attribute data uses the Kronecker product to perturb each attribute information in turn according to the respective privacy level but achieves only a weak privacy level for the entire dataset. Therefore, in this study, we propose a privacy-optimized randomized response that guarantees the strongest privacy in sharing multi-attribute data. Furthermore, we present an efficient heuristic algorithm for constructing a near-optimal mechanism whose time complexity is ${\mathcal{O}}\left({{k^2}}\right)$, where k is the number of attributes. The experimental results demonstrate that both of our methods provide significantly stronger privacy guarantees for the entire dataset than the existing method. Overall, this study is an important step toward trustworthy sharing and analysis of multi-attribute data.

We introduce the novel Nearest Pattern Constrained String (NPCS) problem of finding a minimum set Q of character mutation, insertion, and deletion edit operations sufficient to modify a string x to contain all contiguous substrings in a pattern set P and no contiguous substrings in a forbidden pattern set F . Letting Σ be the alphabet of allowed characters, and letting η and ϒ be the longest string length and sum of all string lengths in P ∪ F , respectively, we show that NPCS is fixed-parameter tractable in | P | with time complexity O ( 2 | P | ⋅ ϒ ⋅ | Σ | ⋅ ( | P | + η ) ( | x | + 1 ) ) . Additionally, we consider a generalization of the NPCS problem in which we allow for constraints based on the membership of substrings in regular languages. In particular, we introduce a problem we denote String Editing under Substring in Language Constraints (StrEdit-SILC), where provided a wildcard-free string x ∈ Σ ⁎ , a finite set of regular languages R = { L 1 , L 2 , … } , and a regular language L F , the objective is to find a minimum cost set of mutation, insertion, and deletion edit operations Q that suffice to convert the input string x into a string x ′ ∈ Σ ⁎ , where no substring has membership in L F , and ∀ L i ∈ R , there exists a substring in L i . Here, letting Ψ and ϖ be the sum of all regular expression lengths and longest regular expression length for languages in R ∪ { L F } , respectively, and letting C m i d ∈ N be the maximum cost of an edit operation, we show that StrEdit-SILC is fixed-parameter tractable with respect to Ψ, having time complexity O ( 2 Ψ ⋅ | x | ⋅ ( ϖ ⋅ | Σ | + C m i d ) ) . However, we also show that StrEdit-SILC is MAX-SNP-hard and otherwise difficult to approximate under stringent constraints.

This work presents a mechanism to debias polynomial functions computed from locally differentially private data. Local differential privacy is a widely used privacy notion where users add Laplacian noise to their information before submitting it to a central server. That, however, causes bias when we calculate non-linear functions based on those noisy information. Our proposed recursive algorithm debiases these functions, with a calculation time of O(r n log n), where r is the polynomial degree and n is the number of users. We evaluate our method on the problems of k-star counting and variance estimation, comparing results with state-of-the-art algorithms. The results show that our method not only eliminates bias, but also provides at least 100 times more accuracy than previous works.

With the recent increase in the medical data and health awareness, the use of genomic data to promote personalized medicine has been widely considered. Simultaneously, privacy concerns have arisen with the publication of statistics obtained from large-scale genomic statistical analysis such as GWAS. All existing differentially private methods for GWAS statistics protect privacy by adding noise based on global sensitivity, considering the worst-case scenario of possible datasets. However, the amount of noise required in practical cases is considerably smaller, and these methods do not achieve the desired accuracy in private statistics. In this study, we propose a privacy-preserving method for publishing much more accurate statistics using smooth sensitivity, which generates tailored noise for each dataset. We first introduce a more rigorous theorem on the properties of the noise distribution than was known previously and propose a new ϵ-differentially private method for publishing GWAS statistics. We also provide theoretical proof of the privacy guarantee. Thereafter, we present novel theorems for computing the smooth sensitivity significantly faster than conventional approaches. This enables the application of smooth sensitivity to GWAS statistics, which would otherwise be impossible because of the exceedingly high computational complexity. Based on these theorems, we performed detailed analyses of key GWAS statistics and developed efficient algorithms to obtain their smooth sensitivities. Experimental results demonstrate that our proposed methods achieve at least 3 times higher accuracy than existing global sensitivity-based methods. Furthermore, the execution time is sufficiently short, and the accuracy increases when the dataset becomes larger, suggesting that our methods are suitable for the publication of statistics in large-scale analysis. Because our method is expected to be applicable to other general statistics, this study is an important step toward highly accurate statistical analysis using smooth sensitivity. The supplemental materials are available at https://github.com/ay0408/SS-based-Stats.

BACKGROUND: Microarray data have been widely utilized for cancer classification. The main characteristic of microarray data is "large p and small n" in that data contain a small number of subjects but a large number of genes. It may affect the validity of the classification. Thus, there is a pressing demand of techniques able to select genes relevant to cancer classification. RESULTS: This study proposed a novel feature (gene) selection method, Iso-GA, for cancer classification. Iso-GA hybrids the manifold learning algorithm, Isomap, in the genetic algorithm (GA) to account for the latent nonlinear structure of the gene expression in the microarray data. The Davies-Bouldin index is adopted to evaluate the candidate solutions in Isomap and to avoid the classifier dependency problem. Additionally, a probability-based framework is introduced to reduce the possibility of genes being randomly selected by GA. The performance of Iso-GA was evaluated on eight benchmark microarray datasets of cancers. Iso-GA outperformed other benchmarking gene selection methods, leading to good classification accuracy with fewer critical genes selected. CONCLUSIONS: The proposed Iso-GA method can effectively select fewer but critical genes from microarray data to achieve competitive classification performance.

Since the division of Korea, the two Korean languages have diverged significantly over the last 70 years. However, due to the lack of linguistic source of the North Korean language, there is no DPRK-based language model. Consequently, scholars rely on the Korean language model by utilizing South Korean linguistic data. In this paper, we first present a large-scale dataset for the North Korean language. We use the dataset to train a BERT-based language model, DPRK-BERT. Second, we annotate a subset of this dataset for the sentiment analysis task. Finally, we compare the performance of different language models for masked language modeling and sentiment analysis tasks.

As the amount of data containing human genome information increases, these data will be further utilized in medicine. However, if the statistics obtained from large-scale analyses are released unchanged, there is a risk of identifying individuals. Although there are several privacy-preserving techniques to release and utilize genomic statistics, most have the problem of poor accuracy at high privacy levels and do not provide correct results especially with an increased number of outputs. In addition, existing methods with relatively high accuracy are computationally intensive and hardly applicable to a large cohort such as those containing 106SNPs. In this paper, we propose innovative differentially private methods with both efficiency and high accuracy to release the top K significant SNPs based on genomic statistics data. First, we enhance the Fourier perturbation algorithm (FPA), which was proposed in the context of histogram publication, for use with genomic statistics. Then, we propose a new extended FPA with more accurate privacy guarantees and provide a proof that this method achieves ε-differential privacy. Furthermore, we present novel methods combining DFT with the Laplace and exponential mechanisms. These methods take only $\mathcal{O}(m{\text{log}}m)$ time for a dataset containing m SNPs. We also theoretically guarantee that the value of sensitivity for these methods is smaller than that for existing methods and therefore can provide more accurate outputs. In fact, our proposed algorithms can be conducted in less than 20 seconds even for a large cohort, and our experiments using real data show that our methods can achieve 1.5 to 8 times higher accuracy than state-of-the-art methods especially when K is large. Because retrieving multiple significant SNPs from large cohorts in genomic analysis is preferred, our proposed methods are remarkably advisable rather than existing methods. Supplementary materials and the Python implementation of our experiments are available at https://github.com/ay0408/DP-DFT.

Statistical analyses of datasets containing genomic information is essential for personalized medicine. However, when the statistics are released as they are, there is a risk of identifying individuals. In this study, we propose efficient a nd practical privacy-preserving methods using the concept of differential privacy for linkage analysis with a transmission disequilibrium test (TDT). We focus on the case of two affected children in one family, and present differentially private data sharing methods based on three statistics, which are the TDT statistic, haplotype-based statistic, and combined statistic of these two. First, we show the sensitivities of each statistic and present the algorithm using the Laplace mechanism. Then, for the exponential mechanism, we adopt the shortest Hamming distance score as the score function and propose exact and approximation algorithms to find the scores. In our experiments, we measure the run time of each algorithm to show that it is feasible even on a large dataset containing 106SNPs. Supplementary materials are available at https://github.com/ay0408/DP-linkage-analysis-TDT.

A set of k-mers is used in many bioinformatics tasks, and much work has been done on methods to efficiently represent or compress a single set of k-mers. However, methods for compressing multiple k-mer sets have been less studied in spite of their obvious benefits for researchers and genome-related database maintainers. This paper proposes an algorithm to compress multiple k-mer sets, which works by iteratively splitting SPSS (spectrum-preserving string sets). In experiments with 3292 k-mer sets constructed from E. coli whole-genome sequencing data and 2555 k-mer sets constructed from human RNA-Seq data, the proposed algorithm could reduce the compressed file sizes by 34.7% and 13.2% respectively compared to one of the state-of-the-art colored de Bruijn graph representations. Also, our method used less memory than the colored de Bruijn graph method. This paper also introduces various methods to make the compression algorithm efficient in terms of time and memory, one of which is a parallelizable small-weight SPSS construction algorithm.

Morphological information is important for many sequence labeling tasks in Natural Language Processing (NLP). Yet, existing approaches rely heavily on manual annotations or external software to capture this information. In this study, we propose using subword contextual embeddings for languages with rich morphology. Evaluated on Dependency Parsing (DEP) and Named Entity Recognition (NER) tasks, which are shown to benefit highly from morphological information, subword contextual embeddings consistently outperformed other approaches on all languages tested (Hungarian, Finnish, Czech and Turkish). Our proposed method enables achieving state-of-the-art results with little annotation requirements compared to the previous work. Besides, the novel network architecture we propose, coupled with a Bayesian hyperparameter optimization suite, achieved state-of-the-art results for both tasks for the Turkish language. Finally, we experimented with different multi-task learning architectures to analyze the effect of jointly learning the two tasks.

Wear leveling - a technology designed to balance the write counts among memory cells regardless of the requested accesses - is vital in prolonging the lifetime of certain computer memory devices, especially the type of next-generation non-volatile memory, known as phase change memory (PCM). Although researchers have been working extensively on wear leveling, almost all existing studies mainly focus on the practical aspects and lack rigorous mathematical analyses. The lack of theory is particularly problematic for security-critical applications. We address this issue by revisiting wear leveling from a theoretical perspective. First, we completely determine the problem parameter regime for which Security Refresh - one of the most well-known existing wear leveling schemes for PCM - works effectively by providing a positive result and a matching negative result. In particular, Security Refresh is not competitive for the practically relevant regime of large-scale memory. Then, we propose a novel scheme that achieves better lifetime, time/space overhead, and wear-free space for the relevant regime not covered by Security Refresh. Unlike existing studies, we give rigorous theoretical lifetime analyses, which is necessary to assess and control the security risk.

BACKGROUND: Nanopore sequencing is a rapidly developing third-generation sequencing technology, which can generate long nucleotide reads of molecules within a portable device in real-time. Through detecting the change of ion currency signals during a DNA/RNA fragment's pass through a nanopore, genotypes are determined. Currently, the accuracy of nanopore basecalling has a higher error rate than the basecalling of short-read sequencing. Through utilizing deep neural networks, the-state-of-the art nanopore basecallers achieve basecalling accuracy in a range from 85% to 95%. RESULT: In this work, we proposed a novel basecalling approach from a perspective of instance segmentation. Different from previous approaches of doing typical sequence labeling, we formulated the basecalling problem as a multi-label segmentation task. Meanwhile, we proposed a refined U-net model which we call UR-net that can model sequential dependencies for a one-dimensional segmentation task. The experiment results show that the proposed basecaller URnano achieves competitive results on the in-species data, compared to the recently proposed CTC-featured basecallers. CONCLUSION: Our results show that formulating the basecalling problem as a one-dimensional segmentation task is a promising approach, which does basecalling and segmentation jointly.

As online storage services become increasingly common, it is important that users' private information is protected from database access pattern analyses. Oblivious RAM (ORAM) is a cryptographic primitive that enables users to perform arbitrary database accesses without revealing any information about the access pattern to the server. Previous ORAM studies focused mostly on reducing the access overhead. Consequently, the access overhead of the state-of-the-art ORAM constructions are almost at practical levels in certain application scenarios such as secure processors. However, we assume that the server space usage could become a new important issue in the coming big-data era. To enable large-scale computation in security-aware settings, it is necessary to rethink the ORAM server space cost using big-data standards. In this paper, we introduce "succinctness" as a theoretically tractable and practically relevant criterion of the ORAM server space efficiency in the big-data era. We, then, propose two succinct ORAM constructions that also exhibit state-of-the-art performance in terms of the bandwidth blowup and the user space. We also give non-asymptotic analyses and simulation results which indicate that the proposed ORAM constructions are practically effective.

We developed a convolution neural networks (CNN) and ensemble learning based method, called Malphite, to predict protein secondary structures. Maphite has three sub-models: the 1st CNN, PSI-PRED and the 2nd CNN. The 1st CNN and PSI-PRED are used to predict the initial secondary structure based on the position specific scoring matrix generated from PSIBLAST. The 2nd CNN performs ensemble learning by combining the prediction result of the 1st CNN and PSI-PRED and generate the final predictions. Malphite achieved a Q3 score of 82.3% and 82.6% for independently built dataset of 400 and 538 proteins respectively, and 82.6% ten-fold-cross validated accuracy for a dataset of 3000 proteins. In addition, Malphite accomplished a remarkable Q3 score of 83.6% for 122 targets from CASP10 (Critical Assessment of protein Structure Prediction), surpassing any secondary structure prediction technique to date. For all four datasets, Malphite consistently makes 2% more accurate prediction than PSI-PRED, which is a significantly step towards the estimated upper limit of protein secondary structure prediction accuracy of 90%.

Detection of controlling regions/driver nodes of the cortical networks helps the networks dynamics reach a desired state. Controllability of the complex networks can be accomplished through minimizing two quantities related to the eigenvalues of the extended adjacency matrix. The identification problem of the driver nodes can be solved as a Constrained Optimization Problem which unifies these two quantities into one framework. The cat cortical network is taken as an example of a directed weighted complex network. In this paper, the Constrained Dynamic Differential Evolution (CDDE) algorithm is generalized to produce the Generalized Constrained Dynamic Differential Evolution (GCDDE) algorithm. The GCDDE uses the exploitation probability Pe to determine whether the crossover rate CR takes random large values from the range [0.5, 1] to produce different levels of exploration ability or takes random small values from the range [0, 0.5] to produce different levels of exploitation ability. Through the value of Pe, GCCDE can attain the tradeoff between exploration and exploitation with multiformity. Then, the algorithms GCDDE and CDDE are applied to determine the controlling regions of the cortical networks. The results illustrate that GCDDE outperforms four state-of-the-art Constrained Optimization Evolutionary Algorithms and also approaches of the control theory and graph theory. Using GCDDE, the identification problem of driver nodes is investigated in a macroscopic manner. It is found that the controlling regions have a high in-degree and a low out-degree. It is important to mention that when the number of driver nodes increases, the GCDDE can find feasible optimal solutions that make the cat cortical network more controllable.

The papers in this special section were presented at the 2014 International Conference on Genome Informatics (GIW).

In genome assembly graphs, motifs such as tips, bubbles, and cross links are studied in order to find sequencing errors and to understand the nature of the genome. Superbubble, a complex generalization of bubbles, was recently proposed as an important subgraph class for analyzing assembly graphs. At present, a quadratic time algorithm is known. This paper gives an O(m log m)-time algorithm to solve this problem for a graph with m edges.

Protein structure analysis is one of the most important research issues in the post-genomic era, and faster and more accurate index data structures for such 3-D structures are highly desired for research on proteins. This article proposes a new data structure for indexing protein 3-D structures. For strings, there are many efficient indexing structures such as suffix trees, but it has been considered very difficult to design such sophisticated data structures against 3-D structures like proteins. Our index structure is based on the suffix tree and is called the geometric suffix tree. By using the geometric suffix tree for a set of protein structures, we can exactly search for all of their substructures whose RMSDs (root mean square deviations) or URMSDs (unit-vector root mean square deviations) to a given query 3-D structure are not larger than a given bound. Though there are O ( N 2 ) substructures in a structure of size N , our data structure requires only O ( N ) space for indexing all the substructures. We propose an O ( N 2 ) construction algorithm for it, while a naive algorithm would require O ( N 3 ) time to construct it. Moreover we propose an efficient search algorithm. Experiments show that we can search for similar structures much faster than previous algorithms if the RMSD threshold is not larger than 1Å. The experiments also show that the construction time of the geometric suffix tree is practically almost linear to the size of the database, when applied to a protein structure database.

Analysis of conformational changes is one of the keys to the understanding of protein functions and interactions. For the analysis, we often compare two protein structures, taking flexible regions like hinge regions into consideration. The Root Mean Square Deviation (RMSD) is the most popular measure for comparing two protein structures, but it is only for rigid structures without hinge regions. In this paper, we propose a new measure called RMSD considering hinges (RMSDh) and its variant RMSDh(k) for comparing two flexible proteins with hinge regions. We also propose novel efficient algorithms for computing them, which can detect the hinge positions at the same time. The RMSDh is suitable for cases where there is one small hinge region in each of the two target structures. The new algorithm for computing the RMSDh runs in linear time, which is the same as the time complexity for computing the RMSD and is faster than any of previous algorithms for hinge detection. The RMSDh(k) is designed for comparing structures with more than one hinge region. The RMSDh(k) measure considers at most k small hinge region, i.e., the RMSDh(k) value should be small if the two structures are similar except for at most k hinge regions. To compute the value, we propose an O(kn2)-time and O(n)-space algorithm based on a new dynamic programming technique. With the same computational time and space, we can enumerate the predicted hinge positions. We also test our algorithms against actual flexible protein structures, and show that the hinge positions can be correctly detected by our algorithms.

MOTIVATION: Clustering sequences of a full-length cDNA library into alternative splice form candidates is a very important problem. RESULTS: We developed a new efficient algorithm to cluster sequences of a full-length cDNA library into alternative splice form candidates. Current clustering algorithms for cDNAs tend to produce too many clusters containing incorrect splice form candidates. Our algorithm is based on a spliced sequence alignment algorithm that considers splice sites. The spliced sequence alignment algorithm is a variant of an ordinary dynamic programming algorithm, which requires O(nm) time for checking a pair of sequences where n and m are the lengths of the two sequences. Since the time bound is too large to perform all-pair comparison for a large set of sequences, we developed new techniques to reduce the computation time without affecting the accuracy of the output clusters. Our algorithm was applied to 21 076 mouse cDNA sequences of the FANTOM 1.10 database to examine its performance and accuracy. In these experiments, we achieved about 2-12-fold speedup against a method using only a traditional hash-based technique. Moreover, without using any information of the mouse genome sequence data or any gene data in public databases, we succeeded in listing 87-89% of all the clusters that biologists have annotated manually. AVAILABILITY: We provide a web service for cDNA clustering located at https://access.obigrid.org/ibm/cluspa/, for which registration for the OBIGrid (http://www.obigrid.org) is required.

The multiple sequence alignment problem is very applicable and important in various fields in molecular biology.But the optimal alignment, based on the scoring criterion is not always the biologically most significant alignment.We here demonstrate two flexible and efficient approaches to solve this problem, together with computational results for largescale problems.One approach is to provide many suboptimal

No abstract available.