Crynodeb
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.
Iaith wreiddiol | Saesneg |
---|---|
Tudalennau (o-i) | 2455-2473 |
Nifer y tudalennau | 19 |
Cyfnodolyn | Stochastic Processes and their Applications |
Cyfrol | 121 |
Rhif cyhoeddi | 11 |
Dynodwyr Gwrthrych Digidol (DOIs) | |
Statws | Cyhoeddwyd - 1 Tach 2011 |
Cyhoeddwyd yn allanol | Ie |