Abstract
In the post-genomic era, large-scale personal DNA sequences are produced and collected for genetic medical diagnoses and new drug discovery, which, however, simultaneously poses serious challenges to the protection of personal genomic privacy. Existing genomic privacy-protection methods are either time-consuming or with low accuracy. To tackle these problems, this paper proposes a sequence similarity-based obfuscation method, namely IterMegaBLAST, for fast and reliable protection of personal genomic privacy. Specifically, given a randomly selected sequence from a dataset of DNA sequences, we first use MegaBLAST to find its most similar sequence from the dataset. These two aligned sequences form a cluster, for which an obfuscated sequence was generated via a DNA generalization lattice scheme. These procedures are iteratively performed until all of the sequences in the dataset are clustered and their obfuscated sequences are generated. Experimental results on two benchmark datasets demonstrate that under the same degree of anonymity, IterMegaBLAST significantly outperforms existing state-of-the-art approaches in terms of both utility accuracy and time complexity.
Introduction
The rise of personalized medicine has made the sharing of genomic data essential for scientific progress. However, DNA is a unique identifier that can reveal sensitive information about an individual's identity, ancestry, and health risks. Traditional privacy methods often fail to balance security, computational efficiency, and data utility. Cryptographic methods are slow, and simple de-identification is insufficient as the sequence itself can act as a fingerprint. This research introduces IterMegaBLAST, a method designed to achieve $k$-anonymity in genomic datasets while preserving high data utility and significantly reducing processing time.
Methodology: IterMegaBLAST
The core of the IterMegaBLAST approach is an iterative clustering and obfuscation workflow. The goal is to group similar sequences together to minimize the amount of generalization required to achieve anonymity.
1. Clustering with MegaBLAST
Unlike traditional alignment tools that are computationally expensive, IterMegaBLAST utilizes MegaBLAST, a high-speed greedy algorithm optimized for finding highly similar sequences. The algorithm selects a random sequence and identifies its closest match (homolog) within the dataset. These pairs form the initial clusters.
2. DNA Generalization Lattice
Once clusters are formed, the sequences are obfuscated using a generalization lattice. If two sequences in a cluster differ at a specific nucleotide position, they are replaced with a more general IUPAC code. For example, if one sequence has 'A' and the other has 'T', they are generalized to 'W' (representing a weak bond). If the difference is too great, the position is generalized to 'N' (any nucleotide).
By grouping the most similar sequences first, the method ensures that the resulting obfuscated data retains as much detail as possible, maximizing its utility for researchers.
Experimental Evaluation
The method was tested on two human DNA benchmarks:
- Dataset I: 56 sequences from the melanocortin gene promoter region (average length 6.6 kb).
- Dataset II: 372 sequences from the human mitochondrion control region (average length 0.5 kb).
Results and Performance
IterMegaBLAST was compared against several state-of-the-art methods, including DNALA and MWM. The results showed that IterMegaBLAST consistently maintained lower information loss (average distance) compared to its peers, particularly for the longer sequences in Dataset I.
The most striking advantage of IterMegaBLAST is its speed. As shown in the table below, it processed Dataset I in just 112 seconds, whereas the MWM-based methods required over 7,000 seconds—a speedup of approximately 60 to 80 times.
Conclusion
IterMegaBLAST offers a scalable and effective solution for genomic privacy. By leveraging fast sequence alignment and an intelligent generalization scheme, it overcomes the limitations of previous methods that were either too slow or too destructive to data utility. Future work will focus on reducing the impact of randomness in cluster selection and exploring multiple sequence alignment (MSA) to further refine accuracy.
Summary updated