FractTM")?>
### - A Fractional Programming Approach to efficient DNA Melting Temperature Calculation

M. Leber, L. Kaderali, A. Schönhuth, R. Schrader

**Motivation:** In a wide range of experimental techniques in
biology, there is a need for an efficient method to calculate the
melting temperature of pairings of two single DNA strands. Avoiding
crosshybridization when choosing primers for the polymerase chain
reaction or selecting probes for large-scale DNA assays are examples
where the exact determination of melting temperatures is of
fundamental importance. Beyond being exact, the method has to be
efficient, as these techniques often require the simultaneous
calculation of calculation of melting temperatures of up to millions
of possible pairings. The problem then is to simultaneously determine
the most stable alignment of two sequences, including potential loops
and bulges, and caluclate the corresponding melting temperature.

**Results:** As the melting temperature can be expressed as a fraction
in terms of enthalpy and entropy differences of the corresponding annealing
reaction, we propose a fractional programming algorithm, the Dinkelbach
algorithm, to solve the problem. To calculate the required differences of
enthalpy and entropy, the nearest neighbor model is applied. Using this
model, the substeps of the dinkelbach algorithm in our problem setting
turn out to be calculations of alignments which optimize an additive score
function. Thus, the usual dynamic programming techniques can be applied. The
result is a very efficient algorithm to determine exact melting temperatures
of two DNA strands, suitable for large scale applications such as primer or
probe design.

**FractTM** is a program to determine the melting temperature of two
DNA sequences using a nearest-neighbor model.

The version used here requires two DNA-sequences as input. The
program can be used with DNA-RNA and RNA-RNA duplexes if
the respective thermodynamic parameters are provided. Unpaired bases (bulges)
in the duplexes will be considered by the software.

Please insert your data in the following form.

Contact:")?>**Lars Kaderali**

kaderali@zpr.uni-koeln.de
Source Code")?>
The C++ source code is available on request from the authors.