Z-Hunt-DP: accelerating thermodynamic Z-DNA prediction with dynamic programming
Listed in
This article is not in any list yet, why not save it to one of your lists.Abstract
Z-DNA is a left-handed DNA conformation implicated in gene regulation and chromatin dynamics. Because it is usually less thermodynamically favorable than canonical B-DNA under physiological conditions, computational tools are needed to identify sequences likely to adopt the Z conformation. Legacy Z-Hunt uses a dinucleotide thermodynamic model, but searches every anti/syn assignment in a window, causing its conformation search to grow exponentially with window size. We present Z-Hunt-DP, an exact dynamic programming reformulation that preserves the original thermodynamic objective while reducing this search from O (2 d ) to O ( d ) for a window of d dinucleotide positions. On benchmark windows, Z-Hunt-DP matched the brute-force minimum energy within numerical tolerance and achieved a 3.30 × 10 5 speedup at 20 dinucleotides. In an interval-localization benchmark on public human loci with experimentally mapped Z-DNA, it recovered the clipped reference interval in all 24 cases and was the most stable localizer under midpoint-core and expanded-panel analyses. Since the comparison set mixes thermodynamic, heuristic, and learned models, these cross-tool results are interpreted as localization comparisons rather than direct thermodynamic score tests. The source code and benchmark materials are available at https://github.com/Aljumaily/Z-Hunt-DP .
Author summary
DNA can form structures other than its familiar right-handed double helix. One alternative, Z-DNA, is left-handed and may influence how genes are regulated, but identifying it across long DNA sequences remains computationally demanding. Existing Z-Hunt software estimates Z-DNA propensity from experimentally derived energy values. Its central calculation tests every possible local DNA conformation, so its run time rises very quickly as the sequence window grows. We developed Z-Hunt-DP, which solves the same thermodynamic problem by reusing the best partial solutions at each position. This yields the same optimal energy as exhaustive search but requires far less computation. We confirmed exact agreement with brute-force calculations and found large speed gains on increasing window sizes. We also tested whether predicted regions align with public human loci where Z-DNA has been experimentally mapped. Z-Hunt-DP consistently located the center of those loci more reliably than the other tested tools. The open-source implementation makes this established thermodynamic model practical for reproducible genome-scale analysis and for prioritizing compact experimental validation targets.
