Efficient privacy-preserving variable-length substring match for genome sequence

Yoshiki Nakagawa, Satsuya Ohata, Kana Shimizu*


研究成果: Article査読


The development of a privacy-preserving technology is important for accelerating genome data sharing. This study proposes an algorithm that securely searches a variable-length substring match between a query and a database sequence. Our concept hinges on a technique that efficiently applies FM-index for a secret-sharing scheme. More precisely, we developed an algorithm that can achieve a secure table lookup in such a way that V[V[… V[p] …]] is computed for a given depth of recursion where p is an initial position, and V is a vector. We used the secure table lookup for vectors created based on FM-index. The notable feature of the secure table lookup is that time, communication, and round complexities are not dependent on the table length N, after the query input. Therefore, a substring match by reference to the FM-index-based table can also be conducted independently against the database length, and the entire search time is dramatically improved compared to previous approaches. We conducted an experiment using a human genome 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 non-indexed database search protocol under the realistic computation/network environment.

ジャーナルAlgorithms for Molecular Biology
出版ステータスPublished - 2022 12月

ASJC Scopus subject areas

  • 構造生物学
  • 分子生物学
  • 計算理論と計算数学
  • 応用数学


「Efficient privacy-preserving variable-length substring match for genome sequence」の研究トピックを掘り下げます。これらがまとまってユニークなフィンガープリントを構成します。