DNA approach to scenery reconstruction

Heinrich Matzinger*, Angelica Pachon

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

2 Citations (Scopus)


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 languageEnglish
Pages (from-to)2455-2473
Number of pages19
JournalStochastic Processes and their Applications
Issue number11
Publication statusPublished - 1 Nov 2011
Externally publishedYes


Dive into the research topics of 'DNA approach to scenery reconstruction'. Together they form a unique fingerprint.

Cite this