Computing edit distance (shortest sequence of edit operations) on ordered trees is a well studied problem with many known algorithms (e.g. Zhang & Shasha, RTED). There is also considerable literature on edit distance for general graph (e.g., this review). I am however interested in a mixed case that has arisen in our inquiries into RNA structures in computational biology: how to compute edit distance between directed acyclic graphs (DAGs) with ordered children, i.e. a DAG where each node imposes a total ordering on its outgoing edges. There seem to be multiple ways to define edit operations on such "ordered DAG" but as a first approximation, I don't care about which edit operations are primitive. I was unable to find any literature on this problem.
Is there a known algorithm for edit distance on ordered DAGs (or more general graphs with ordered outgoing edges)? Or can some of the known tree edit distance algorithms be easily extended to cover DAGs?
Note that I cannot defer to algorithms for general graph edit distance as those (AFAIK) don't take order of outgoing edges into account.