Established techniques for global gene expression profiling, such as microarrays, face fundamental sensitivity constraints. Due to greatly increasing interest in examining minute samples from micro-dissected tissues, including single cells, unorthodox approaches, including molecular nanotechnologies, are being explored in this application. Here, we examine the use of single molecule, ordered restriction mapping, combined with AFM, to measure gene transcription levels from very low abundance samples. We frame the problem mathematically, using coding theory, and present an analysis of the critical error sources that may serve as a guide to designing future studies. We follow with experiments detailing the construction of high density, single molecule, ordered restriction maps from plasmids and from cDNA molecules, using two different enzymes, a result not previously reported. We discuss these results in the context of our calculations.