From: Martin Tompa (tompa@cs.washington.edu)
Date: Tue Mar 30 2004 - 14:21:00 PST
There is a signup page if you'd like to meet with Sagi, at http://reserve.cs.washington.edu/visitor/week.php?year=2004&month=04&day=06&room=592 .
> -----Original Message-----
> From: theory-group-bounces@cs.washington.edu
> [mailto:theory-group-bounces@cs.washington.edu]On Behalf Of
> Martin Tompa
> Sent: Monday, March 22, 2004 11:32 AM
> To: compbio-seminars; cse590cb; theory-group
> Cc: Joe Felsenstein (E-mail); Scott Dakins; Sagi Snir (E-mail)
> Subject: Snir, 4/6, 1:30, on a problem derived from
> evolutionary biology
>
>
> 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
>
_______________________________________________
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 : Tue Mar 30 2004 - 14:21:13 PST