Bioinformatics Advance Access originally published online on March 15, 2005
Bioinformatics 2005 21(10):2375-2382; doi:10.1093/bioinformatics/bti379
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
A fractional programming approach to efficient DNA melting temperature calculation
1Institute for Biochemistry, University of Cologne Zülpicher Straße 47, Köln, D-50674, Germany
2Center for Applied Computer Sciences, University of Cologne Weyertal 80, Köln, D-50931, Germany
*To whom correspondence should be addressed.
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 cross-hybridization 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 important. Beyond being exact, the method has to be efficient, as these techniques often require the simultaneous calculation of melting temperatures of up to millions of possible pairings. The problem is to simultaneously determine the most stable alignment of two sequences, including potential loops and bulges, and calculate 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 to use 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 an efficient algorithm to determine melting temperatures of two DNA strands, suitable for large-scale applications such as primer or probe design.
Availability: The software is available for academic purposes from the authors. A web interface is provided at http://www.zaik.uni-koeln.de/bioinformatik/fptm.html.
Contact: kaderali{at}zpr.uni-koeln.de
CiteULike 
Connotea 
Del.icio.us What's this?
This article has been cited by other articles:
|
|
 |
|
  T. Mann, R. Humbert, M. Dorschner, J. Stamatoyannopoulos, and W. S. Noble A thermodynamic approach to PCR primer design Nucleic Acids Res., July 1, 2009; 37(13): e95 - e95. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
J. Duitama, D. M. Kumar, E. Hemphill, M. Khan, I. I. Mandoiu, and C. E. Nelson PrimerHunter: a primer design tool for PCR-based virus subtype identification Nucleic Acids Res., May 1, 2009; 37(8): 2483 - 2492. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
J. D. Gans and M. Wolinsky Improved assay-dependent searching of nucleic acid sequence databases Nucleic Acids Res., July 1, 2008; 36(12): e74 - e74. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 W. Tembe, N. Zavaljevski, E. Bode, C. Chase, J. Geyer, L. Wasieloski, G. Benson, and J. Reifman Oligonucleotide fingerprint identification for microarray-based pathogen diagnostic assays Bioinformatics, January 1, 2007; 23(1): 5 - 13. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
H. H. Nour-Eldin, B. G. Hansen, M. H. H. Norholm, J. K. Jensen, and B. A. Halkier Advancing uracil-excision based cloning towards an ideal technique for cloning PCR fragments Nucleic Acids Res., October 6, 2006; 34(18): e122 - e122. [Abstract] [Full Text] [PDF]
|
|