Homomorphic Computation of Local Alignment

In this paper we present a homomorphic computation algorithm that finds an optimal local alignment of a pair of encrypted sequences, based on the Smith-Waterman recurrence. Our algorithm also includes an efficient method of finding the location of an optimal local alignment, in order to avoid costly conditional branching in the backtracking. To reduce computation time, we use two level parallel computations: one for filling the entries of the dynamic programming recurrence, and the other for implementing the circuits. To the best of our knowledge, this is the first attempt to compute an optimal local alignment of homomorphically encrypted sequences. With the efficient location retrieval, parallel computations, and a proper HE scheme, our implementation shows good performances in the experiment so as to be useful in practice.