Extension de la distance de modification de l'arbre ordonné aux dags

Question

Le calcul de la distance d'édition (séquence la plus courte des opérations d'édition) sur les arbres ordonnés est un problème bien étudié avec de nombreux algorithmes connus (par exemple Zhang & Shasha, Rted). Il existe également une littérature considérable sur la distance de modification pour le graphique général (par exemple, Cette revue). Je suis cependant intéressé par un cas mixte qui a surgi dans nos demandes de renseignements sur les structures d'ARN en biologie informatique: comment calculer la distance de modification entre les graphiques acycliques dirigés (DAG) avec des enfants ordonnés, c'est-à-dire un DAG où chaque nœud impose une commande totale à son sortant bords. Il semble y avoir plusieurs façons de définir les opérations de modification sur un tel "DAG ordonné", mais en première approximation, je me fiche des opérations de modification primitives. Je n'ai pas pu trouver de littérature sur ce problème.

Existe-t-il un algorithme connu pour modifier la distance sur les Dags ordonnés (ou des graphiques plus généraux avec des bords sortants ordonnés)? Ou certains des algorithmes de distance de modification des arbres connus peuvent-ils être facilement étendus pour couvrir les Dags?

Notez que je ne peux pas m'en remettre aux algorithmes pour la distance de modification du graphique général car ceux (afaik) ne tiennent pas compte des bords sortants.