Date |
May 20, 2009 |
Speaker |
Assoc. Prof. Gabriel Valiente, Technical University of Cataloni, Spain |
Title |
Alignment of Trees and Directed Acyclic Graphs in Computational Biology
|
Abstract |
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. The alignment of
trees and directed acyclic graphs in computational biology will be
illustrated by the alignment of phylogenetic trees and networks.
|
|