DNA approach to scenery reconstruction
Matzinger, Heinrich and Pinzon, Angelica Pachon. (2011) DNA approach to scenery reconstruction. Stochastic Processes and their Applications, Vol.121 (No.11). pp. 2455-2473. ISSN 0304-4149Full text not available from this repository.
Official URL: http://dx.doi.org/10.1016/j.spa.2011.04.010
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 a 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. (C) 2011 Published by Elsevier B.V.
|Item Type:||Journal Article|
|Subjects:||Q Science > QA Mathematics|
|Divisions:||Faculty of Science > Mathematics|
|Journal or Publication Title:||Stochastic Processes and their Applications|
|Publisher:||Elsevier Science BV|
|Number of Pages:||19|
|Page Range:||pp. 2455-2473|
|Access rights to Published version:||Restricted or Subscription Access|
Actions (login required)