Abstract
The basic reconstruction problem lead with the general task of retrieving a scenery from observations made by a random walker. A critical factor associated with the problem is reconstructing the scenery in polynomial time. In this article, we propose a novel technique based on the modern DNA sequencing method for reconstructing a 3-color scenery of length n. The idea is first to reconstruct small pieces of length order log n and then assembled them together to form the required piece. We show that this reconstruction and assembly for a finite piece of a 3-color scenery takes polynomial amount of time.
Original language | English |
---|---|
Pages (from-to) | 2455-2473 |
Number of pages | 19 |
Journal | Stochastic Processes and their Applications |
Volume | 121 |
Issue number | 11 |
DOIs | |
Publication status | Published - 1 Nov 2011 |
Externally published | Yes |