License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.WABI.2021.2
URN: urn:nbn:de:0030-drops-143552
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14355/
Go to the corresponding LIPIcs Volume Portal

Nakagawa, Yoshiki ; Ohata, Satsuya ; Shimizu, Kana

Efficient Privacy-Preserving Variable-Length Substring Match for Genome Sequence

pdf-format:
LIPIcs-WABI-2021-2.pdf (1 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{nakagawa_et_al:LIPIcs.WABI.2021.2,
  author =	{Nakagawa, Yoshiki and Ohata, Satsuya and Shimizu, Kana},
  title =	{{Efficient Privacy-Preserving Variable-Length Substring Match for Genome Sequence}},
  booktitle =	{21st International Workshop on Algorithms in Bioinformatics (WABI 2021)},
  pages =	{2:1--2:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-200-6},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{201},
  editor =	{Carbone, Alessandra and El-Kebir, Mohammed},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/14355},
  URN =		{urn:nbn:de:0030-drops-143552},
  doi =		{10.4230/LIPIcs.WABI.2021.2},
  annote =	{Keywords: Private Genome Sequence Search, Secure Multiparty Computation, Secret Sharing, FM-index, Suffix Tree, Maximal Exact Match}
}

Keywords: Private Genome Sequence Search, Secure Multiparty Computation, Secret Sharing, FM-index, Suffix Tree, Maximal Exact Match
Collection: 21st International Workshop on Algorithms in Bioinformatics (WABI 2021)
Issue Date: 2021
Date of publication: 22.07.2021

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI