{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,2]],"date-time":"2026-06-02T22:14:21Z","timestamp":1780438461352,"version":"3.54.1"},"reference-count":30,"publisher":"Oxford University Press (OUP)","issue":"11","license":[{"start":{"date-parts":[[2016,10,28]],"date-time":"2016-10-28T00:00:00Z","timestamp":1477612800000},"content-version":"vor","delay-in-days":240,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016,6,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>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.<\/jats:p>\n                  <jats:p>Approach: We propose a novel approach that combines efficient string data structures such as the Burrows\u2013Wheeler 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\u2013Wheeler 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.<\/jats:p>\n                  <jats:p>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 \u2248 4.6\u2009s and \u2248 10.8\u2009s 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.<\/jats:p>\n                  <jats:p>Availability and implementation: \u00a0https:\/\/github.com\/iskana\/PBWT-sec and https:\/\/github.com\/ratschlab\/PBWT-sec.<\/jats:p>\n                  <jats:p>Contacts: \u00a0shimizu-kana@aist.go.jp or Gunnar.Ratsch@ratschlab.org<\/jats:p>\n                  <jats:p>Supplementary information: \u00a0Supplementary data are available at Bioinformatics online.<\/jats:p>","DOI":"10.1093\/bioinformatics\/btw050","type":"journal-article","created":{"date-parts":[[2016,3,3]],"date-time":"2016-03-03T21:13:45Z","timestamp":1457039625000},"page":"1652-1661","source":"Crossref","is-referenced-by-count":55,"title":["Efficient privacy-preserving string search and an application in genomics"],"prefix":"10.1093","volume":"32","author":[{"given":"Kana","family":"Shimizu","sequence":"first","affiliation":[{"name":"1Biotechnology Research Institute for Drug Discovery, National Institute of Advanced Industrial Science and Technology, Tokyo 135-0064, Japan,"},{"name":"2Computational Biology, Memorial Sloan Kettering Cancer Center, New York, NY 1275 York, USA,"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Koji","family":"Nuida","sequence":"additional","affiliation":[{"name":"3Information Technology Research Institute, National Institute of Advanced Industrial Science and Technology, Tokyo 135-0064, Japan and"},{"name":"4Japan Science and Technology Agency (JST) PRESTO Researcher, Tokyo, Japan"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Gunnar","family":"R\u00e4tsch","sequence":"additional","affiliation":[{"name":"2Computational Biology, Memorial Sloan Kettering Cancer Center, New York, NY 1275 York, USA,"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"286","published-online":{"date-parts":[[2016,3,2]]},"reference":[{"key":"2023020112292721400_btw050-B1","doi-asserted-by":"crossref","first-page":"403","DOI":"10.1016\/S0022-2836(05)80360-2","article-title":"Basic local alignment search tool","volume":"215","author":"Altschul","year":"1990","journal-title":"J. Mol. Biol"},{"key":"2023020112292721400_btw050-B2","author":"Ayday","year":"2013"},{"key":"2023020112292721400_btw050-B3","author":"Baldi","year":"2011"},{"key":"2023020112292721400_btw050-B4","author":"Blanton","year":"2010"},{"key":"2023020112292721400_btw050-B5","first-page":"203","article-title":"Privacy-preserving matching of DNA profiles","volume":"2008","author":"Bruekers","year":"2008","journal-title":"IACR Cryptol. ePrint Arch"},{"key":"2023020112292721400_btw050-B7","author":"Cristofaro","year":"2013"},{"key":"2023020112292721400_btw050-B8","doi-asserted-by":"crossref","first-page":"1266","DOI":"10.1093\/bioinformatics\/btu014","article-title":"Efficient haplotype matching and storage using the positional Burrows\u2013Wheeler transform (PBWT)","volume":"30","author":"Durbin","year":"2014","journal-title":"Bioinformatics"},{"key":"2023020112292721400_btw050-B9","doi-asserted-by":"crossref","first-page":"469","DOI":"10.1109\/TIT.1985.1057074","article-title":"A public key cryptosystem and a signature scheme based on discrete logarithms","volume":"31","author":"ElGamal","year":"1985","journal-title":"IEEE Trans. Inf. Theory"},{"key":"2023020112292721400_btw050-B10","doi-asserted-by":"crossref","first-page":"409","DOI":"10.1038\/nrg3723","article-title":"Routes for breaching and protecting genetic privacy","volume":"15","author":"Erlich","year":"2014","journal-title":"Nat. Rev. Genet"},{"key":"2023020112292721400_btw050-B11","author":"Freedman","year":"2005"},{"key":"2023020112292721400_btw050-B12","doi-asserted-by":"crossref","first-page":"270","DOI":"10.1016\/0022-0000(84)90070-9","article-title":"Probabilistic encryption","volume":"28","author":"Goldwasser","year":"1984","journal-title":"J. Comput. Syst. Sci"},{"key":"2023020112292721400_btw050-B13","doi-asserted-by":"crossref","DOI":"10.1101\/gr.153346.112","article-title":"Identifying genetic relatives without compromising privacy","author":"He","year":"2014","journal-title":"Genome Res"},{"key":"2023020112292721400_btw050-B14","author":"Jacobson","year":"1988"},{"key":"2023020112292721400_btw050-B15","author":"Jha","year":"2008"},{"key":"2023020112292721400_btw050-B16","first-page":"656","article-title":"BLAT \u2013 the BLAST-Like Alignment Tool","volume":"12","author":"Kent","year":"2002","journal-title":"Genome Res"},{"key":"2023020112292721400_btw050-B17","doi-asserted-by":"crossref","first-page":"R25.","DOI":"10.1186\/gb-2009-10-3-r25","article-title":"Ultrafast and memory-efficient alignment of short DNA sequences to the human genome","volume":"10","author":"Langmead","year":"2009","journal-title":"Genome Biol"},{"key":"2023020112292721400_btw050-B18","doi-asserted-by":"crossref","first-page":"1754","DOI":"10.1093\/bioinformatics\/btp324","article-title":"Fast and accurate short read alignment with Burrows\u2013Wheeler transform","volume":"25","author":"Li","year":"2009","journal-title":"Bioinformatics"},{"key":"2023020112292721400_btw050-B19","doi-asserted-by":"crossref","first-page":"473","DOI":"10.1093\/bib\/bbq015","article-title":"A survey of sequence alignment algorithms for next-generation sequencing","volume":"11","author":"Li","year":"2010","journal-title":"Briefings Bioinf"},{"key":"2023020112292721400_btw050-B20","doi-asserted-by":"crossref","first-page":"1966","DOI":"10.1093\/bioinformatics\/btp336","article-title":"Soap2: an improved ultrafast tool for short read alignment","volume":"25","author":"Li","year":"2009","journal-title":"Bioinformatics"},{"key":"2023020112292721400_btw050-B21","author":"Lipmaa","year":"2005"},{"key":"2023020112292721400_btw050-B22","author":"Lipmaa","year":"2008"},{"key":"2023020112292721400_btw050-B23","author":"Naganuma","year":"2012"},{"key":"2023020112292721400_btw050-B24","author":"Paillier","year":"1999"},{"key":"2023020112292721400_btw050-B25","author":"Rabin","year":"1981"},{"key":"2023020112292721400_btw050-B26","doi-asserted-by":"crossref","first-page":"392","DOI":"10.1038\/35072029","article-title":"Protecting genetic privacy","volume":"2","author":"Roche","year":"2001","journal-title":"Nat. Rev. Genet"},{"key":"2023020112292721400_btw050-B27","doi-asserted-by":"crossref","first-page":"1156","DOI":"10.1587\/transfun.E96.A.1156","article-title":"Methods for restricting message space in public-key encryption","volume":"96-A","author":"Sakai","year":"2013","journal-title":"IEICE Trans"},{"key":"2023020112292721400_btw050-B28","doi-asserted-by":"crossref","first-page":"631","DOI":"10.1016\/j.ajhg.2015.09.010","article-title":"Privacy risks from genomic data-sharing beacons","volume":"97","author":"Shringarpure","year":"2015","journal-title":"Am. J. Hum. Genet"},{"key":"2023020112292721400_btw050-B29","doi-asserted-by":"crossref","first-page":"56","DOI":"10.1038\/nature11632","article-title":"An integrated map of genetic variation from 1,092 human genomes","volume":"491","author":"The 1000 Genomes Project Consortium","year":"2012","journal-title":"Nature"},{"key":"2023020112292721400_btw050-B30","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-319-12229-8","volume-title":"Homomorphic Encryption and Applications","author":"Yi","year":"2014"},{"key":"2023020112292721400_btw050-B31","author":"Zhang","year":"2013"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/32\/11\/1652\/49019541\/bioinformatics_32_11_1652.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/32\/11\/1652\/49019541\/bioinformatics_32_11_1652.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,1]],"date-time":"2023-02-01T17:33:35Z","timestamp":1675272815000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/32\/11\/1652\/1742915"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,3,2]]},"references-count":30,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2016,6,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btw050","relation":{"has-preprint":[{"id-type":"doi","id":"10.1101\/018267","asserted-by":"object"}]},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2016,6,1]]},"published":{"date-parts":[[2016,3,2]]}}}