April 27, Monday
14:00 – 16:00
Alignment of Trees and Directed Acyclic Graphs
Computer Science seminar
Lecturer : Gabriel Valiente
Location : 37/202
Host : Michal Ziv-Ukelson
It is well known that the string edit distance and the alignment of strings coincide, while the alignment of trees differs from the tree edit distance. In this talk, we recall various constraints on directed acyclic graphs that allow for a unique (up to isomorphism) representation, called the path multiplicity representation, and present a new method for the alignment of trees and directed acyclic graphs that exploits the path multiplicity representation to produce a meaningful optimal alignment in polynomial time.