NegSPQ: Similar Patient Query Based on Negative Representation of Genomic Data

With the development of genome sequencing technology, genomic data have been widely collected and used in real-world scenarios, such as genomic medicine and similar patient query (SPQ) cases, based on similarity comparisons of genomic sequences. However, genomic data are unique for every person and contain a large amount of sensitive information involving personal privacy. Therefore, determining how to protect privacy while utilizing genomic data has become a key issue. In this paper, we mainly investigate the privacy protection of SPQs, and we propose five algorithms (NDB-ED, NDB-Band, NDB-Block, NDB-SIS and NDB-SDS) based on a promising technique called negative representation of information (NRI). The proposed algorithms use five kinds of similarity comparison approaches widely applied in SPQs and convert all genomic sequences into negative databases (NDBs, among the most important NRI forms) for privacy protection. When performing an SPQ, NDB-ED approximates the edit distance between the sketches (the statistics of NDBs) of two genomic sequences to evaluate the dissimilarity. Banded edit distance and block-wise edit distance are two effective approximate edit distance algorithms, which can greatly reduce the time complexity. NDB-Band and NDB-Block are used to estimate the banded edit distance and the block-wise edit distance between the sketches of NDB pairs, respectively, to further improve query efficiency and reduce communication overhead. Besides, private genome set intersection size (SIS) and set difference size (SDS) can also be used instead of edit distance to evaluate the dissimilarity between genomic pairs during SPQs. NDB-SIS and NDB-SDS estimate the SIS and SDS between the sketches, for similarity comparison. The experimental results demonstrate that the proposed algorithms can achieve promising results in terms of accuracy and efficiency (Our best algorithm improves accuracy by at least 10% and query time is at least 700 times faster than existing algorithms during SPQs).