DNA codeword design: theory and applications

ICS Forum talk:

            DNA codeword design: theory and applications

                        Prof. Max H. Garzon
                       University of Memphis

Abstract:

Finding large sets of single DNA strands that do not crosshybridize to
themselves or to their complements is an important problem in DNA
computing, self-assembly, DNA memories and phylogenetic analyses,
because of their error correction and prevention properties.  The
problem is in itself NP-complete, even in very simplified versions
using any single reasonable measure that approximates the Gibbs
energy, thus practically excluding the possibility of finding any
efficient procedure to find maximal sets efficiently.  After a quick
survey of advances in this area in the last few years, we focus on a
novel combintorial/geometric framework to analyze this problem.

In this framework, codeword design is reduced to finding large sets of
strands maximally separated in DNA spaces and therefore the size of
such sets depends on the geometry of these DNA spaces.  We present a
new general technique to embed DNA spaces in Euclidean spaces and
thus, among others, reduce the word design problem to the well known
sphere packing problem in information theory.  The embedding sheds
some insights into the geometry of DNA spaces by enabling a
quantitative analysis via well established approximations of the Gibbs
energy, namely the nearest neighbor model of duplex formation.  The
main tool is an efficiently computable combinatorial approximation
which is also a mathematical metric.  As illustration, we briefly show
results of two applications, one to to produce provably nearly optimal
codeword sets (modulo the goodness of the Gibbs energy approximation)
and a new methodology for phylogenetic analyses in Biology.