Z-Hunt-DP: accelerating thermodynamic Z-DNA prediction with dynamic programming

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.30x10^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.