From: Martin Tompa (tompa@cs.washington.edu)
Date: Mon Mar 22 2004 - 11:32:20 PST
Please join us for a special seminar on a problem derived from evolutionary biology.
Date: Tuesday April 6th, 2004
Time: 1:30-2:30 pm
Room: CSE 691 (Gates Commons) (map: http://www.washington.edu/home/maps/southcentral.html?80,70,860,720)
Speaker: Sagi Snir, Technion
Title : Convex Recoloring of Strings and Trees
Abstract : A coloring of a tree is convex if the vertices that
pertain to any color induce a connected subtree; a partial coloring
(which assigns colors to some of the vertices) is convex if it can be
completed to a convex (total) coloring. Convex (partial) colorings
of trees are closely related to areas such as phylogenetics,
linguistics, etc. (a brief description of these relations will be
given in the talk).
When a coloring of a tree is not convex, it is desirable to know "how far"
it is from a convex one. Few common measures for this are based on the
parsimony score, which is the number of edges whose endpoints have
different colors. These measures suffer from the inability to cope with
partial coloring and do not estimate the distance to some convex coloring.
In this talk we define and study another natural measure for this
distance: the minimal number of vertices which need to be recolored to
make the coloring convex. This can be viewed as minimizing the number of
"exceptional vertices" w.r.t. to a convex coloring. We show that finding
this distance is NP-hard even for strings. In the positive side we present
few algorithms for optimal convex recoloring of strings and of trees that
are practical in real life. Finally, we present efficient approximation
algorithms for the problem.
Joint work with Shlomo Moran
_______________________________________________
Theory-group mailing list
Theory-group@cs.washington.edu
http://mailman.cs.washington.edu/mailman/listinfo/theory-group
This archive was generated by hypermail 2.1.6 : Mon Mar 22 2004 - 11:32:47 PST