Bounds for the DNA Minimum Alphabetic Similarity Distance Codes

摘要

There is a need to find generalized or universal tags for multiplex genome analysis. Custom-designed DNA arrays offer the possibility of simultaneously monitoring thousands of hybridization reactions. These arrays show great potential for many medical and scientific applications such as polymorphism analysis and genotyping. Relatively high costs are associated with the need to specifically design and synthesize problem specific arrays. Recently, an alternative approach was suggested that utilizes fixed, universal arrays. This approach presents an interesting design problem-the arrays should contain as many probes as possible, while minimizing experimental errors caused by cross-hybridization. We use a simple thermodynamic model to cast this design problem in a formal mathematical framework. We examine DNA sequences as elements of metric spaces and introduce the Minimum Alphabetic Similarity Distance M-distance as a means to this end. We derive Sphere-Packing bounds and Random on the metric and bounds on the rate of the DNA Distance Codes generated corresponding to the distance.