A Cyclic Semi-Global Alignment Dynamic Programming Algorithm for Sequence-Based Detection of Protein Circular Permutations

A novel dynamic programming algorithm is introduced for circular permutation (CP) detection in proteins. The method reformulates CP detection as a single cyclic semi-global alignment of a query sequence against a duplicated target sequence, with zero terminal gap penalties and affine internal gap penalties, and runs in O(n2) time for sequences of comparable length — a quadratic improvement over the exact cubic implementation of Uliel et al. and the quartic scaling of naive breakpoint enumeration. Statistical significance is assessed with a composition-matched shuffle null and a margin-based test (Δ = Scyclic − Slinear) against synthetically homologous controls, complemented by paired t-tests, Cohen’s d, and ROC analysis. Performance was evaluated on 100 structurally validated pairs from the Circular Permutation Database (CPDB), on synthetic benchmarks that now include homologous non-CP and repeat-containing negative controls, and, under a released protocol, on the full CPDB release of 4,169 pairs. On synthetic data with >30% sequence identity, the algorithm achieved 100% sensitivity and 88% specificity (BLOSUM45, gap 15/2), a Matthews correlation coefficient of 0.938, and an ROC AUC of 0.98 against unrelated negatives. CPDB contains no validated negative pairs, so CPDB results are reported as detection recall, and the full release of 4,169 pairs was scanned with the corrected implementation: the permutation margin exceeds a calibrated homologous null for 98.3% of the 4,166 evaluable pairs (99.9% of the pairs above 30% identity). Across 30 validation pairs, native CP alignment scores (mean 5,253.0) were completely separated from 1,000 composition-matched shuffles per pair (pooled null mean −161.4, SD 47.9; paired t(29) = 54.31, p < 0.0001, Cohen’s d = 9.91). Corrected Z-scores against the shuffle null range from 85.0 to 130.3 (mean 113.0), and the margin statistic isolates the permutation signal proper: non-permuted homologs have Δ ≈ 0. The method provides an exact, reproducible, and computationally efficient solution for moderately conserved CP pairs (>30% identity), enabling large-scale genomic screening; for distantly related pairs (<30% identity), structure-based approaches remain necessary. A fixed absolute score threshold (1,000 for the benchmark length range) combined with a positive margin is recommended as the primary criterion, with length-normalized scores provided for general screening. The corrected open-source Python implementation (v2.0.0) is freely available.