Symbolwise MAP for Multiple Deletion Channels

Abstract

We consider the problem of reconstructing a sequence from fixed number of deleted versions of itself (also called traces). The problem is motivated from recent developments in de novo DNA sequencing technologies. The main contribution of this work is to provide a polynomial time algorithm for symbolwise MAP decoding with multiple traces. The algorithm leverages a dynamic program on the edit graph. We also develop a heuristic with reduced time complexity using similar ideas and provide preliminary numerical evaluations.