- 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.