ACPL: a root-free polar ordering for cyclic single-cell trajectories

Abstract

Trajectory inference on cyclic biological processes has a specific geometric failure mode. Graph constructions that minimise Euclidean cost route across the interior of a closed loop rather than around it, placing a backward edge at the G2M to G1 closure, the most consequential transition in the cell cycle. We describe a construction that removes this possibility by ordering cells along the angular coordinate of a planar embedding before any graph is built, and admitting edges only in the direction of increasing smoothed arc length. The resulting directed graph is acyclic by construction, is invariant to the choice of starting cell, and is built in $O(N \log N)$ time. Angular ordering of cell-cycle data is established practice and is not claimed here; the contribution is the directed-graph construction and its evaluation. Across four public datasets, scored by an origin-free rank statistic necessary because ACPL takes no starting cluster while its baselines are given one, it recovers cyclic order more accurately than Monocle-style minimum spanning trees and Slingshot run on their native inputs, consistently across ten embedding seeds, with paired bootstrap intervals excluding zero on two datasets and no comparison favouring a baseline. It is exceeded by tricycle, a reference-based method, on two of three datasets tested, and recovers no significant signal on a yeast series where tricycle cannot run at all. The construction cannot determine the rotational direction of the recovered cycle, so independence from a starting cluster is a trade rather than an advantage. This article supersedes the earlier ACPL preprint, engrXiv 10.31224/7087, whose evaluation contained errors; they are itemised in Section 6.