DNA approach to scenery reconstruction
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.
Volume (Year): 121 (2011)
Issue (Month): 11 (November)
|Contact details of provider:|| Web page: http://www.elsevier.com/wps/find/journaldescription.cws_home/505572/description#description|
|Order Information:|| Postal: http://http://www.elsevier.com/wps/find/supportfaq.cws_home/regional|
Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.:
- Hart, Andrew & Matzinger, Heinrich, 2006. "Markers for error-corrupted observations," Stochastic Processes and their Applications, Elsevier, vol. 116(5), pages 807-829, May.
- Matzinger, Heinrich & Rolles, Silke W. W., 2003. "Reconstructing a piece of scenery with polynomially many observations," Stochastic Processes and their Applications, Elsevier, vol. 107(2), pages 289-300, October.
When requesting a correction, please mention this item's handle: RePEc:eee:spapps:v:121:y:2011:i:11:p:2455-2473. See general information about how to correct material in RePEc.
If references are entirely missing, you can add them using this form.