A fractional programming approach to efficient DNA melting temperature calculation
A fractional programming approach to efficient DNA melting temperature calculation
复制标题
DOI：
10.1093/bioinformatics/bti379
复制
发表时间：
2005-05-15
期刊：
影响因子：
5.8
通讯作者：
Schrader, R
中科院分区：
文献类型：
--
作者：
Leber, M;Kaderali, L;Schrader, R
动机：在生物学的许多实验技术中，需要一种有效的方法来计算两条DNA单链配对的解链温度。在选择聚合酶链反应的引物或选择大规模DNA测定的探针时避免交叉杂交是精确测定解链温度很重要的例子。除了精确之外，该方法还必须高效，因为这些技术通常需要同时计算多达数百万种可能配对的熔化温度。该问题是同时确定两个序列的最稳定的对齐，包括潜在的环和凸起，并计算相应的熔解temperature.Results：由于熔解温度可以表示为一个分数的焓和熵差的退火反应，我们建议使用分数规划算法，Dinkelbach算法，来解决这个问题。为了计算所需的焓差和熵差，应用最近邻模型。使用这个模型，在我们的问题设置中的Dinkelbach算法的子步骤变成优化加性得分函数的比对计算。因此，可以应用通常的动态规划技术。其结果是一个有效的算法来确定两个DNA链的解链温度，适合于大规模的应用，如引物或探针设计。
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.