6
$\begingroup$

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.

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
1
$\begingroup$

So after some thinking and digging around, I know believe (no rigorous proof) that edit distance between ordered DAGs is NP hard (in fact even Max-SNP hard) and thus no efficient algorithm is likely. The informal reasoning follows:

  1. Edit distance between RNA structures with pseudoknots is Max-SNP hard and the reduction to Max-Cut works even if we ignore the RNA sequence (Ma, Wang & Zhang, 2002: Computing similarity between RNA structures)
  2. One can represent an RNA structure with pseudoknots as a DAG with ordered children and labelled edges by extending the tree representation from Zhang & Shasha 1989: Nodes still represent base pairs and unpaired nucleotides, "normal" edges represent the "is contained in" relationship and new type of edges to represent a "contains only first nucleotide of a base-pair" relationship let us represent crossing base pairs.
  3. An algorithm for edit distance on labelled DAGs would therefore likely give an algorithm for Max-Cut which is Max-SNP hard. This obviously depends on what edit operations are allowed, but it seems to work for any sensible set of edit operations I came up with.
Improve this answer
$\endgroup$
4
  • $\begingroup$ Hey @Martin, do you have more updates on this? $\endgroup$
    – mhn_namak
    Commented Jul 22, 2019 at 22:11
  • $\begingroup$ @mhn_namak What updates are you seeking? My conclusion is that the problem is NP hard and I still believe this conclusion. $\endgroup$
    – Martin Modrák
    Commented Aug 6, 2019 at 5:41
  • $\begingroup$ either an algorithm/paper that solves this problem or even better a code package :). $\endgroup$
    – mhn_namak
    Commented Aug 8, 2019 at 19:22
  • 1
    $\begingroup$ @mhn_namak Then no, I don't have this. My buest guess is that since it is NP-hard you might as well just directly search the space generated by edit operations. Even simple algs (A*/iterative deepening/branch and bound/MCTS) might be close to best possible option. $\endgroup$
    – Martin Modrák
    Commented Aug 8, 2019 at 19:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.