DNA approach to scenery reconstruction |
| |
Authors: | Heinrich Matzinger Angelica Pachon Pinzon |
| |
Institution: | a School of Mathematics, Georgia Institute of Technology, Atlanta, GA 30332, United Statesb Centre for Discrete Mathematics and its Applications DIMAP, University of Warwick, Coventry CV4 7AL, United Kingdom |
| |
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. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|